## 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:

• Both subtrees of the i:th node are binary heaps (or empty trees)
• A[i] can be less than one or both of the children. Thus, the heap order property may be violated.

Algorithm 2: Max-Heapify(A, i)

lLeft-child-index(i)
rRight-child-index(i)
if l < heap-size[A] and A[l] > A[i] then
greatestl
else
greatesti
end if
if r < heap-size[A] and A[r] > A[greatest] then
greatestr
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.