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

5. DeleteMax

In general:

1. Replace the root node with the last element in the heap

2. Remove the last element

3. Swap (i.e. heapify) the new root with its child until the correct position has found (See MAX-HEAPIFY)

Removing the smallest element from MinHeap

Store the old root r of the tree into a temporary variable, and replace the root node with the last element in the heap (that is removed from the end of the heap and the size of the heap is decreased). After this, revise the heap order property by 'sifting' the new root node p to its correct position by shifting it with its smaller child. This is repeated until the heap order property is satisfied, i.e., there is no child that has a lower priority than p. Finally, return the preserved old root r.

Removing the largest element from MaxHeap

In MaxHeap, the algorithm works just like above, but the new root going down is swapped with its largest child. We continue to study this algorithm in more details in the next Chapter, see MAX-HEAPIFY algorithm.

---

Previous Chapter: Insert Next Chapter Preserving the Heap Order Property

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