二进制堆索引

Question

在 Wayne 和 Sedgewick 的算法课程中，提出了以下问题：

"Suppose that an array a[] is a max-heap that contains the distinct integer keys 1,2,…,N with N≥7. The key N must be in a[1] and the key N−1 must be in either a[2] or a[3]. Where must the key N−2 be?"

正确答案是“2、3、4、5、6 或 7”。我预计它应该是“2 或 3”，因为 N-2 应该在二进制堆的第二层而不是第三层......有人可以澄清一下吗？提前致谢

Answer 1

在最大堆中，两个最大的项目是根项目和它的 children 中较大的一个。第三大要么是根的child，要么是第二大的child。考虑这两个堆，其中 A 是最大的项目，G 是最小的：

      A                   A
   B     C             B     D
  D E   F G           C G   F E

第一、第三大是根的两个children中较小的一个。在第二堆中，第三项是第二大项的child。无论堆如何排列，第三项要么是根的child，要么是第二大的child。

所以在你描述的情况下，第三大项可以在除根以外的任何位置。

二进制堆索引

Binary heap indexing

algorithm

heap