CODEWITHSUNDEEP
javadata-structuresmaxheapmin-heap
ArkhamWarfare
ArkhamWarfare

Reputation: 121

searching for the maximum value in a min heap

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.

Upvotes: 3

Views: 2200

Answers (3)

ribbit
ribbit

Reputation: 1283

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.

Upvotes: 1

Blazar
Blazar

Reputation: 21

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.

Upvotes: 2

displayName
displayName

Reputation: 14379

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,

Upvotes: 1

Related Questions