searching for the maximum value in a min heap

user_8651642 0
Viewed 1579

Im new to heaps, and trying to understand how heaps work. How do you find out the maximum value in a min heap? i understand that the minimum value could be found by looking for the root, but what about the max value in a min heap? not looking for code, more for theory and for my understanding.

min-heap heap max data-structures java
3 Answers

Its very easy to point out the maximum value in a min-heap if its illustrated. In a min-heap, the maximum value will always be located near the bottom section of the tree, due to the rules of the min-heap. Where the parent node is a smaller value than that of its children. Therefore its very important to remember that the maximum value will not have any children because of this.

Lets say you are given a min-heap.

          2 

     3        7 

  6    4   10   15 

12 14 9 8

In this min-heap just by looking its very obvious that 15 is the maximum value, since you only have to look at elements 12, 14, 9, 8, 15 that have no children and are in a min-heap.

user_87355510

This is just a trick and maybe a little longer than what you need, but if your heap contains numbers you could do this:

  • Negate the numbers from the original heap
  • Run a Min-Heapify on those. This will cause the smallest number (bigger when negated again) to rise up to the root.
user_75735460

The purpose of min-heap is to let you find the minimum element in O(1) time (followed by O(Log n) of heapifying the rest of the heap). Finding both min and max in O(1) is possible, but by using augmented data structures only.

However, if you insist on finding the max element in a min-heap, you can do that by extracting all the elements of the min-heap. The last element extracted from that min-heap would be the max element. The time taken to get he max element would be upper bounded by O(n*Log n). This time complexity is easily derivable - simply Log n summed total n times,

user_18357690
Related