CODEWITHSUNDEEP
algorithmpositionmaxheap
Alexy Grabov
Alexy Grabov

Reputation: 151

Find the position of the k-largest element in max-heap

Doing some algorithms homework here :(

I need to come up with an equation to find all the possible positions in the max-heap array, where a given k-th element might be.

i.e. the largest element (k=1) is at position n=1.
The second largest element (k=2) can be at positions n=2\3.
Element k=3 can also be in positions n=2\3.
...
The 6th largest element (k=6) can be in positions n=4 up to n=7.
etc.

Didn't really come up with a solid calculation.

Any input would be appreciated.

Upvotes: 1

Views: 2574

Answers (2)

Jim Mischel
Jim Mischel

Reputation: 134125

A heap of n items has a height (call it h) of log2(n), rounded up. Assuming a full min heap, the kth item can be pretty much anywhere, subject to the following restrictions.

  1. The first item (k == 1) must be at the root.
  2. The largest item (k == n) must be on the leaf level.
  3. The kth node cannot be at a level greater than k.
  4. The kth node cannot be at a level smaller than (h-log2(n-k)+1).

Consider a full heap with 7 levels. The heap itself has 127 nodes. Each of the nodes at the 2nd level is a full heap of 63 nodes. So each of the items at the second level must have below it 62 values that are smaller. The 96th smallest item cannot possibly be at the second level, because there aren't 62 larger values to fill out its tree.

Those rules can help you bracket a sequential search, but it doesn't do you a whole lot of good. That 96th smallest item in the 7-level heap can be as far up as level 3, and as far down as level 7. There are only three positions that node can't possibly be in.

If you're working with a max heap, change "smallest" above to "largest."

Upvotes: 2

Prune
Prune

Reputation: 77900

The 6th-largest element can be much farther out. The extreme case is where the first six elements are the root and a series of right-children. Each child is at node 2n+1, where n is the parent's node. The sequence of indices for the right-most sequence is 1, 3, 7, 15, 31, 63 (a.k.a. 2^6-1). Other, smaller values fill in the left side of each branch.

The earliest position is if that same value happened to be the left-child of the root, while all of the others went to the right branch: it appears in location 2. Again, smaller values appear as needed.

So, the range of possible values is from 2 to 2^n-1. Your remaining problem is to determine which of the remaining locations can contain that 6th-largest element.

Draw a tree of the proper depth -- better yet, do this only 4 levels deep, and work with the 4th-largest element. Say, use 99, 98, 98, 96, and then the "other" values can be 1 through 11. Is there anywhere on this tree you can put 96 that you cannot arrange the other numbers to form a legal tree?

Expand the tree one more level. Now where are the holes in which you cannot put 96?

Does that get you un-stuck?

Upvotes: 2

Related Questions