Indian Computing Olympiad

Heaps

Max-heaps and min-heaps

The heaps we have considered are called min-heaps, because the minimum value is at the root. If we reverse the second heap condition—that is, we write

• 2'. The value at each node is greater than or equal to that of its parents.

we will get the largest value at the top of the heap. This is called a max-heap. We can define find-max, insert, delete-max and update for max-heaps along the same lines as we did for min-heaps.