Initial conditions:
Algorithm 2: MaxHeapify(A, i)
We revise the heap order property by 'shifting down' the node
i
to its correct position by swapping it with its
greatest child if and only if one exists that is greater than the
i:th node itself. First, we compare A[i]
to its
left child, and the greater of these two is compared with the right
child. This is repeated by calling recursively the algorithm again if
the swap was needed. Otherwise, the algorithm ends, and the heap order
property is satisfied (if the initial conditions were satisfied as
required). This routine can be utilized in many heap algorithms. We
start by looking at the following DeleteMax algorithm.
Exercise: Removing the largest element
MaxHeap is represented both as an array and binary tree. Before doing the exercise, study the following code example, and implement operations Leftchildindex(i) and Rightchildindex(i) for this particular heap. Perform DeleteMax, three times, and after each deletion, restore heap property.
For each record stored into heap you can see a key that corresponds to the
priority. Delete button will remove a key. In addition, by drag & dropping a key on top of another one, you can swap the records.
Algorithm 3 HeapExtractMax(A)

This document was last updated 13.8.2009. Please send your comments to Mikko Laakso, Ari Korhonen, and Ville Karavirta.