CITS2200 - Lecture 18

← Back to Home

CITS2200 - Lecture 17
Heaps - Slides

Heaps

• A heap is a complete binary tree
  • Every level must be filled out except the bottom level
  • Min heaps $-$ every parent is smaller than its children
    • This is known as a heap-order property
    • The root contains the smallest value
• Keys are stored as the nodes
• Perfect for priority queues -> most efficient sort method

---

Insertion and Upheap

Adding a key has three steps:

1. Insert at the next available lead
2. Store the key there
3. Upheap $-$ bubble the key up until heap-order is restored

Upheap terminates when k ≥ parent(k) or k reaches the root

• At most $\log n$ swaps → $O(\log n)$

Removal and Downheap

remove_min() always removes the root, to avoid breaking tree:

1. Copy the last node’s key to the root
2. Remove the last node
3. Downheap $-$ sink the new root key down until heap-order is restored

---

Array-Based Heap

• Can represent a heap with n keys with n size array
  • add corresponds to inserting at rank n + 1
  • remove_min corresponds to removing at rank n

Node at index i	Left child	Right child	Parent
Formula	2i + 1	2i + 2	(i-1) // 2
This is what makes heap-sort in-place possible

• No extra memory needed for pointers or references

Heap Sort

With a heap-based priority queue, sorting n elements takes:

• n × add calls → $n\times O(\log n)$
• n × remove_min calls → $n\times O(\log n)$
• Total: $O(n\log n)$

---

Merging Two Heaps

• We are given two heaps and a key k
• Create new heap with k as root and two heaps as subtrees
• Perform downheap to restore heap-order property

Bottom-up Heap Construction

• If you insert n elements one by one -> $O(n\log n)$ to build heap
• Bottom-up construction builds heap in $O(n)$ time
  • Merges pairs of small heaps across $\log n$ phases

In phase $i$, heap pairs with $2^i-1$ keys merge into heaps with $2^{i+1}-1$ keys

1. Pair nodes and assign parent

   

2. Use downheap to restore heap-order

   

3. Repeat steps 1&2 until root node reached

Bottom-up vs One-by-One

Inserting n elements one-by-one → $O(n\log n)$ to build
Bottom-up construction → $O(n)$ to build
Either way, heap-sort itself is $O(n\log n)$ total

---

CITS2200 - Lecture 19