CODEWITHSUNDEEP
data-structuresbinary-heap
Barak Mi
Barak Mi

Reputation: 51

Range of second largest key in min - heap

I need to find the second largest element in a min - heap array.

Well I realized it may be one of the leaves of the tree or a parent of a leaf. I concluded that the Range of those nodes are - [floor(n/4) + 1 , n]. But still it i can build some trees which dont match with this formula.

Thanks for help!

Upvotes: 2

Views: 733

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 134005

My comment didn't take into account the possible existence of duplicate items in the heap. If duplicate items are possible, then the second-largest node can be any node in the heap, except the last node.

Absent duplicate items, then the next-to-largest node is either at the leaf level, or it's a node on the level just above the leaf level, and it will have at most one child. It could have no children.

The first node that could be the next-to-last is at 2^(h-2) + 1, where h is the height of the tree. By convention, a tree with only a root node has a height of 0, so given this heap:

        0
     /     \
    1       2
   / \     / \
  3   4   5   6

The tree has a height of 2. The first node that could be the second largest is at 2^(2-2)+1, or 1.

The range of nodes that could contain the next-to-last value is, then [2^(h-2) + 1, n-1].

The above assumes that the root of your heap is at index 0 in your array. If the root is at index 1, you have to adjust accordingly.

Upvotes: 1

Related Questions