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

3. MinHeap vs. MaxHeap

MaxHeap: For each i > 1:

            A[PARENT(i)]  ≥ A[i]

• The element with the largest priority is at the root node
• The element with the smallest priority is in a leaf node

MinHeap For each i > 1:

            A[PARENT(i)]  ≤ A[i]

• The element with the smallest priority is at the root node
• The element with the greatest priority is in a leaf node

---

Previous Chapter: Array Representation of Binary Heap Next Chapter: Insert

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