Priority Queues and Binary Heap

  1. Introduction
  2. Array Representation of Binary Heap
  3. MinHeap vs. MaxHeap
  4. Insert
  5. DeleteMax
  6. Preserving the Heap Order Property
  7. BuildHeap
  8. HeapSort
  9. Analysis

6. Preserving the Heap Order Property (MaxHeap)

Initial conditions:


Algorithm 2: Max-Heapify(A, i)

l ← Left-child-index(i)
r ← Right-child-index(i)
if l < heap-size[A] and A[l] > A[i] then
greatest ← l
else
greatest ← i
end if
if r < heap-size[A] and A[r] > A[greatest] then
greatest ← r
end if
if greatest ≠ i then
Swap(A[i],A[greatest])
Max-Heapify(A, greatest)
end if

Basic idea of the algorithm

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 Left-child-index(i) and Right-child-index(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 Heap-Extract-Max(A)

max ← A[0]
A[0] ← A[heap-size[A]-1]
heap-size[A] ← heap-size[A] - 1
Max-Heapify(A, 0)
return max


Algorithm 2 Max-Heapify(A, i)

l ← Left-child-index(i)
r ← Right-child-index(i)
if l < heap-size[A] and A[l] > A[i] then
greatest ← l
else
greatest ← i
end if
if r < heap-size[A] and A[r] > A[greatest] then
greatest ← r
end if
if greatest ≠ i then
Swap(A[i],A[greatest])
Max-Heapify(A, greatest)
end if



Previous Chapter: DeleteMax Next Chapter: BuildHeap

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