CODEWITHSUNDEEP
algorithmheap
sammy
sammy

Reputation: 867

Binary heap indexing

In the algorithms course by Wayne and Sedgewick, the following question is asked:

"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?"

The right answer is "2, 3, 4, 5, 6, or 7". I expected that it should have been "2 or 3", because N-2 should be on the second level of the binary heap rather than the third... Could someone clarify this, please? Thanks in advance

Upvotes: 2

Views: 395

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 133995

In a max heap, the two largest items are the root item and the larger of its children. The third largest is either a child of the root, or a child of the second largest. Consider these two heaps, where A is the largest item, and G is the smallest:

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

In the first, the third largest is the smaller of the root's two children. In the second heap, the third item is a child of the second largest item. Regardless of how you arrange the heap, the third item will either be a child of the root, or a child of the second largest.

So in the situation you describe, the third largest item can be at any position except the root.

Upvotes: 3

Related Questions