在Wayne和Sedgewick的算法课程中，我们提出了以下问题：
“假设数组a[]是一个最大堆，其中包含n≥7的不同整数键1,2，…，n。键n必须在a[1]中，键n-1必须在a[2]或a[3]中。钥匙N-2必须在哪里？”
正确答案是“2、3、4、5、6或7”我希望它应该是“2或3”，因为n-2应该在二进制堆的第二层，而不是第三层……有人能澄清一下吗？提前谢谢
最佳答案
在最大堆中，最大的两个项是根项及其较大的子项第三大的要么是根的子级，要么是第二大的子级考虑这两个堆，其中A是最大的项，G是最小的项：
A A
B C B D
D E F G C G F E
在第一个中，第三个最大的是根的两个孩子中较小的一个。在第二个堆中，第三个项是第二大项的子项。不管您如何排列堆，第三个项要么是根的子项，要么是第二个最大的子项。
所以在您描述的情况下，第三大项可以位于除根以外的任何位置。