Heap Sort & Priority Queues Advanced
In this chapter, we'll explore heaps—a powerful tree-based data structure that enables efficient sorting and priority management. Heaps form the foundation of priority queues, are used in Dijkstra's shortest path algorithm, and power the Heap Sort algorithm we'll master today.
Unlike the sorting algorithms we've seen so far, Heap Sort guarantees O(n log n) performance in all cases while using only O(1) auxiliary space. We'll build heap data structures from scratch, understand how they maintain their special properties, and apply them to real-world problems like task scheduling and finding top K elements.
What You'll Learn
Estimated time: 90 minutes
By the end of this chapter, you will:
- Build a binary heap data structure from scratch and understand heap properties (max-heap and min-heap)
- Implement heapify operations (sift-up and sift-down) for maintaining heap invariants
- Master Heap Sort algorithm achieving O(n log n) time with O(1) space complexity
- Understand priority queues and their real-world applications (task scheduling, Dijkstra's algorithm)
- Implement advanced heap operations (decrease-key, increase-key) for algorithm optimization
- Build a streaming median finder using two heaps for O(log n) insertions
- Master merge K sorted arrays using heap for O(n log k) time complexity
- Compare Heap Sort with other O(n log n) algorithms and learn trade-offs
- Understand when to use PHP's SplHeap vs custom implementations
Prerequisites
Before starting this chapter, ensure you have:
- ✓ Understanding of trees and binary tree structures (basic tree concepts needed)
- ✓ Understanding of Big O notation from Chapter 01 (60 mins if not done)
- ✓ Completion of Chapters 05-07 on sorting algorithms (180 mins if not done)
- Estimated Time: ~90 minutes
Quick Checklist
Complete these hands-on tasks as you work through the chapter:
- [ ] Implement binary heap structure with array representation
- [ ] Write heapify-up (sift-up) and heapify-down (sift-down) operations
- [ ] Build a max-heap from an unsorted array
- [ ] Implement Heap Sort by building heap and extracting elements
- [ ] Create a Priority Queue class with insert, extract-max, and peek operations
- [ ] Implement decrease-key and increase-key operations for heap updates
- [ ] Build streaming median finder using two heaps (max heap + min heap)
- [ ] Implement merge K sorted arrays using min heap
- [ ] Benchmark Heap Sort vs Quick Sort and Merge Sort
- [ ] Compare custom heap with PHP's SplHeap and SplPriorityQueue
- [ ] (Optional) Implement min-heap and use it for finding k smallest elements
What Is a Heap?
A heap is a complete binary tree that satisfies the heap property:
- Max Heap: Parent node ≥ all children
- Min Heap: Parent node ≤ all children
Example Max Heap:
90
/ \
80 70
/ \ /
60 50 40Key characteristics:
- Complete binary tree (filled left to right, level by level)
- Parent-child relationship determines structure
- Root is always maximum (max heap) or minimum (min heap)
Heap Invariants (Formal Definition)
A heap maintains two critical invariants:
Shape Invariant: The tree is a complete binary tree
- All levels are filled except possibly the last
- Last level is filled left to right
- Height: ⌊log₂(n)⌋
Heap Property Invariant:
- Max Heap: For every node i:
heap[parent(i)] ≥ heap[i] - Min Heap: For every node i:
heap[parent(i)] ≤ heap[i]
- Max Heap: For every node i:
Mathematical Proof of Heap Property:
For a max heap with n elements:
- Base case: Single node (n=1) trivially satisfies heap property
- Inductive step: Assume heap property holds for heaps of size k
- When inserting element at position k+1:
- If
heap[k+1] > heap[parent(k+1)], swap and bubble up - After swap, heap property maintained for subtree rooted at parent
- By induction, heap property holds for all nodes
- If
Why This Matters:
- Guarantees root is always max/min
- Enables O(log n) insert/extract operations
- Foundation for O(n log n) heap sort
Visual Step-by-Step: Building Max Heap from [4, 10, 3, 5, 1]
Initial array: [4, 10, 3, 5, 1]
Step 1: Start as tree (not a heap yet)
4
/ \
10 3
/ \
5 1
Step 2: Heapify from last non-leaf (index 1, value 10)
Compare 10 with children (5, 1): 10 > both ✓
No change needed
Step 3: Heapify root (index 0, value 4)
Compare 4 with children (10, 3): 10 > 4
Swap 4 and 10:
10
/ \
4 3
/ \
5 1
Continue heapify at index 1 (value 4):
Compare 4 with children (5, 1): 5 > 4
Swap 4 and 5:
10
/ \
5 3
/ \
4 1
Final Max Heap: [10, 5, 3, 4, 1] ✓Animation Concept: Imagine building a pyramid where each brick (parent) must be heavier than its supporting bricks (children). If a lighter brick is on top, it sinks down by swapping with the heavier brick below until the pyramid is stable.
Array Representation
Heaps are efficiently stored in arrays using index arithmetic:
Array: [90, 80, 70, 60, 50, 40]
Tree representation:
90 (index 0)
/ \
80 70
/ \ /
60 50 40Index formulas (0-based indexing):
- Parent of node at index i:
(i - 1) / 2 - Left child of node at index i:
2 * i + 1 - Right child of node at index i:
2 * i + 2
php
# filename: heap-index-formulas.php
<?php
class Heap
{
private array $heap = [];
private function parent(int $i): int
{
return (int)(($i - 1) / 2);
}
private function leftChild(int $i): int
{
return 2 * $i + 1;
}
private function rightChild(int $i): int
{
return 2 * i + 2;
}
}Building a Max Heap
The Heapify Operation
Heapify maintains the heap property by "bubbling down" a node:
php
# filename: max-heap.php
<?php
declare(strict_types=1);
class MaxHeap
{
private array $heap = [];
// O(log n) - bubble down from index i
private function heapify(int $i, int $heapSize): void
{
$left = 2 * $i + 1;
$right = 2 * $i + 2;
$largest = $i;
// Find largest among node, left child, right child
if ($left < $heapSize && $this->heap[$left] > $this->heap[$largest]) {
$largest = $left;
}
if ($right < $heapSize && $this->heap[$right] > $this->heap[$largest]) {
$largest = $right;
}
// If largest is not current node, swap and continue heapifying
if ($largest !== $i) {
[$this->heap[$i], $this->heap[$largest]] =
[$this->heap[$largest], $this->heap[$i]];
$this->heapify($largest, $heapSize);
}
}
// Build heap from array - O(n)
public function buildHeap(array $arr): void
{
$this->heap = $arr;
$n = count($this->heap);
// Start from last non-leaf node and heapify all
for ($i = (int)(($n / 2) - 1); $i >= 0; $i--) {
$this->heapify($i, $n);
}
}
public function getHeap(): array
{
return $this->heap;
}
}
// Usage
$heap = new MaxHeap();
$heap->buildHeap([4, 10, 3, 5, 1]);
print_r($heap->getHeap()); // [10, 5, 3, 4, 1]Iterative Heapify (Alternative Implementation)
For very large heaps, iterative heapify avoids potential stack overflow from recursion:
php
# filename: iterative-heapify.php
<?php
declare(strict_types=1);
class MaxHeapIterative
{
private array $heap = [];
// Iterative heapify - O(log n), avoids recursion stack
private function heapifyIterative(int $i, int $heapSize): void
{
while (true) {
$left = 2 * $i + 1;
$right = 2 * $i + 2;
$largest = $i;
// Find largest among node and its children
if ($left < $heapSize && $this->heap[$left] > $this->heap[$largest]) {
$largest = $left;
}
if ($right < $heapSize && $this->heap[$right] > $this->heap[$largest]) {
$largest = $right;
}
// If heap property satisfied, stop
if ($largest === $i) {
break;
}
// Swap and continue down the tree
[$this->heap[$i], $this->heap[$largest]] =
[$this->heap[$largest], $this->heap[$i]];
$i = $largest;
}
}
public function buildHeap(array $arr): void
{
$this->heap = $arr;
$n = count($this->heap);
for ($i = (int)(($n / 2) - 1); $i >= 0; $i--) {
$this->heapifyIterative($i, $n);
}
}
public function getHeap(): array
{
return $this->heap;
}
}
// Usage
$heap = new MaxHeapIterative();
$heap->buildHeap([4, 10, 3, 5, 1]);
print_r($heap->getHeap()); // [10, 5, 3, 4, 1]When to Use Iterative vs Recursive:
| Approach | Pros | Cons | Use When |
|---|---|---|---|
| Recursive | Cleaner code, easier to understand | Stack overflow risk for very large heaps | Learning, small-medium heaps |
| Iterative | No stack overflow, constant space | Slightly more complex | Production code, very large heaps |
Common Issues:
- Error: "Undefined array key" — Check heap size bounds before accessing children indices
- Wrong heap output — Make sure you start heapifying from the last non-leaf node:
(n/2) - 1 - Infinite recursion — Ensure heapify stops when
$largest === $i(heap property satisfied)
Visualizing Heapify
php
# filename: heapify-visualized.php
<?php
declare(strict_types=1);
function heapifyVisualized(array &$arr, int $i, int $heapSize, int $depth = 0): void
{
$indent = str_repeat(' ', $depth);
echo $indent . "Heapify node at index $i (value: {$arr[$i]})\n";
$left = 2 * $i + 1;
$right = 2 * $i + 2;
$largest = $i;
if ($left < $heapSize && $arr[$left] > $arr[$largest]) {
$largest = $left;
}
if ($right < $heapSize && $arr[$right] > $arr[$largest]) {
$largest = $right;
}
if ($largest !== $i) {
echo $indent . " Swap {$arr[$i]} and {$arr[$largest]}\n";
[$arr[$i], $arr[$largest]] = [$arr[$largest], $arr[$i]];
echo $indent . " Array now: [" . implode(', ', $arr) . "]\n";
heapifyVisualized($arr, $largest, $heapSize, $depth + 1);
} else {
echo $indent . " Heap property satisfied\n";
}
}Heap Visualization Helper
A utility function to visualize heap structure as a tree:
php
# filename: heap-visualizer.php
<?php
declare(strict_types=1);
function visualizeHeap(array $heap, string $title = "Heap Structure"): void
{
echo "\n" . str_repeat("=", 50) . "\n";
echo $title . "\n";
echo str_repeat("=", 50) . "\n";
echo "Array: [" . implode(', ', $heap) . "]\n\n";
if (empty($heap)) {
echo "(empty)\n";
return;
}
$n = count($heap);
$height = (int)floor(log($n, 2)) + 1;
$maxWidth = pow(2, $height - 1) * 4;
// Print tree level by level
$index = 0;
for ($level = 0; $level < $height && $index < $n; $level++) {
$nodesInLevel = min(pow(2, $level), $n - $index);
$spacing = (int)($maxWidth / ($nodesInLevel + 1));
$indent = (int)($spacing / 2);
echo str_repeat(' ', $indent);
for ($i = 0; $i < $nodesInLevel && $index < $n; $i++) {
printf("%4d", $heap[$index]);
echo str_repeat(' ', $spacing - 4);
$index++;
}
echo "\n";
// Print connecting lines
if ($level < $height - 1 && $index < $n) {
$nextLevelNodes = min(pow(2, $level + 1), $n - $index);
$nextSpacing = (int)($maxWidth / ($nextLevelNodes + 1));
$nextIndent = (int)($nextSpacing / 2);
echo str_repeat(' ', $nextIndent);
for ($i = 0; $i < $nextLevelNodes && $index < $n; $i++) {
echo ($i % 2 === 0 ? '/' : '\\');
echo str_repeat(' ', $nextSpacing - 1);
}
echo "\n";
}
}
echo "\n";
}
// Usage
$heap = [90, 80, 70, 60, 50, 40, 30];
visualizeHeap($heap, "Max Heap Example");
// Output:
// ==================================================
// Max Heap Example
// ==================================================
// Array: [90, 80, 70, 60, 50, 40, 30]
//
// 90
// / \
// 80 70
// / \ / \
// 60 50 40 30Simplified ASCII Visualization:
php
function printHeapSimple(array $heap): void
{
$n = count($heap);
if ($n === 0) {
echo "(empty heap)\n";
return;
}
echo "Heap as tree:\n";
echo " " . $heap[0] . "\n";
if ($n > 1) {
echo " / \\\n";
echo " " . ($heap[1] ?? '') . " " . ($heap[2] ?? '') . "\n";
}
if ($n > 3) {
echo " / \\ / \\\n";
for ($i = 3; $i < min(7, $n); $i++) {
echo " " . ($heap[$i] ?? '') . " ";
}
echo "\n";
}
echo "\nArray indices:\n";
for ($i = 0; $i < $n; $i++) {
echo "Index $i: {$heap[$i]}\n";
}
}Heap Sort Algorithm
Heap sort uses a max heap to sort in ascending order:
- Build a max heap from the array
- Repeatedly extract maximum (root) and rebuild heap
php
# filename: heap-sort.php
<?php
declare(strict_types=1);
function heapSort(array $arr): array
{
$n = count($arr);
// Step 1: Build max heap
for ($i = (int)(($n / 2) - 1); $i >= 0; $i--) {
heapify($arr, $i, $n);
}
// Step 2: Extract elements one by one
for ($i = $n - 1; $i > 0; $i--) {
// Move current root (max) to end
[$arr[0], $arr[$i]] = [$arr[$i], $arr[0]];
// Heapify the reduced heap
heapify($arr, 0, $i);
}
return $arr;
}
function heapify(array &$arr, int $i, int $heapSize): void
{
$left = 2 * $i + 1;
$right = 2 * $i + 2;
$largest = $i;
if ($left < $heapSize && $arr[$left] > $arr[$largest]) {
$largest = $left;
}
if ($right < $heapSize && $arr[$right] > $arr[$largest]) {
$largest = $right;
}
if ($largest !== $i) {
[$arr[$i], $arr[$largest]] = [$arr[$largest], $arr[$i]];
heapify($arr, $largest, $heapSize);
}
}
// Test
$numbers = [12, 11, 13, 5, 6, 7];
print_r(heapSort($numbers));
// Output: [5, 6, 7, 11, 12, 13]Complexity Analysis
| Scenario | Time Complexity | Space Complexity | Why? |
|---|---|---|---|
| Best case | O(n log n) | O(1) | Always builds heap and extracts |
| Average case | O(n log n) | O(1) | Same work regardless of input |
| Worst case | O(n log n) | O(1) | Guaranteed performance |
| Stable | No | - | Equal elements may be reordered |
Detailed Time Complexity Breakdown:
Build Heap Phase: O(n)
Level 0 (leaves): n/2 nodes × 0 moves = 0 Level 1: n/4 nodes × 1 move = n/4 Level 2: n/8 nodes × 2 moves = n/4 Level 3: n/16 nodes × 3 moves = 3n/16 ... Total: n/4 + n/4 + 3n/16 + ... ≈ nExtract and Heapify Phase: O(n log n)
- n extractions
- Each extraction: O(log n) heapify
- Total: n × log n
Overall: O(n) + O(n log n) = O(n log n)
Visual Breakdown (8 elements):
Build Heap: O(8) work
[4, 10, 3, 5, 1, 8, 2, 6]
↓
[10, 6, 8, 5, 1, 3, 2, 4] (max heap)
Extract 8 times: O(8 log 8) = O(8 × 3) = 24 comparisons
Extract 10 → heapify (3 levels)
Extract 8 → heapify (3 levels)
Extract 6 → heapify (2 levels)
...
Total: 24 comparisons
Total: 8 + 24 = 32 operations = O(n log n)Why O(n) to Build Heap?
Intuitive answer: Seems like O(n log n) since we heapify n/2 nodes...
Mathematical proof:
- Most nodes are at the bottom (height 0): n/2 nodes, 0 work each
- Second level (height 1): n/4 nodes, 1 swap max each
- Third level (height 2): n/8 nodes, 2 swaps max each
- Continue to root...
Total work:
T(n) = Σ(h × n/2^(h+1)) for h = 0 to log n
= n × Σ(h/2^(h+1))
= n × (1/2 + 2/4 + 3/8 + 4/16 + ...)
= n × 1 (converges to 1)
= O(n)Space Complexity:
- O(1) auxiliary space: Sorts in place
- No extra arrays: Unlike merge sort
- No recursion stack: Iterative heapify
- Only temp variables: For swapping
Why Not Stable?
php
// Example showing instability
$arr = [4a, 4b, 2, 3];
// Build max heap: [4a, 4b, 2, 3] or [4b, 4a, 2, 3]
// After sorting: [2, 3, 4b, 4a] ← 4b comes before 4a!
// Original order not preservedHeap Operations Complexity Summary
Quick reference table for all heap operations:
| Operation | Time Complexity | Space Complexity | Description |
|---|---|---|---|
| Build Heap | O(n) | O(1) | Convert unsorted array to heap |
| Insert | O(log n) | O(1) | Add element and bubble up |
| Extract Max/Min | O(log n) | O(1) | Remove root and heapify |
| Peek | O(1) | O(1) | Get root without removing |
| Decrease Key | O(log n) | O(1) | Update element and heapify down |
| Increase Key | O(log n) | O(1) | Update element and bubble up |
| Delete | O(log n) | O(1) | Remove arbitrary element |
| Search | O(n) | O(1) | Find element (no optimization) |
| Heap Sort | O(n log n) | O(1) | Sort by building heap and extracting |
Key Insights:
- Build heap is O(n), not O(n log n) - most nodes are at bottom levels
- All modifications (insert, extract, update) are O(log n) - tree height
- Peek is O(1) - root is always accessible
- Search is O(n) - heaps don't support efficient search (use hash table if needed)
When Each Operation Matters:
- Insert + Extract: Priority queues, task scheduling
- Decrease/Increase Key: Dijkstra's algorithm, Prim's MST
- Build Heap: Heap sort, initializing priority queue from array
- Peek: Checking top priority without removing
Priority Queue
A priority queue is a data structure where elements are processed by priority, not insertion order.
Max Priority Queue Implementation
php
# filename: priority-queue.php
<?php
declare(strict_types=1);
class PriorityQueue
{
private array $heap = [];
// Insert element - O(log n)
public function insert(int $value): void
{
// Add to end
$this->heap[] = $value;
// Bubble up
$this->bubbleUp(count($this->heap) - 1);
}
// Extract maximum - O(log n)
public function extractMax(): ?int
{
if (empty($this->heap)) {
return null;
}
$max = $this->heap[0];
// Move last element to root
$this->heap[0] = array_pop($this->heap);
// Bubble down
if (!empty($this->heap)) {
$this->heapify(0);
}
return $max;
}
// Peek at maximum - O(1)
public function peek(): ?int
{
return $this->heap[0] ?? null;
}
// Get size - O(1)
public function size(): int
{
return count($this->heap);
}
// Check if empty - O(1)
public function isEmpty(): bool
{
return empty($this->heap);
}
private function bubbleUp(int $i): void
{
while ($i > 0) {
$parent = (int)(($i - 1) / 2);
if ($this->heap[$i] <= $this->heap[$parent]) {
break;
}
[$this->heap[$i], $this->heap[$parent]] =
[$this->heap[$parent], $this->heap[$i]];
$i = $parent;
}
}
private function heapify(int $i): void
{
$n = count($this->heap);
$left = 2 * $i + 1;
$right = 2 * $i + 2;
$largest = $i;
if ($left < $n && $this->heap[$left] > $this->heap[$largest]) {
$largest = $left;
}
if ($right < $n && $this->heap[$right] > $this->heap[$largest]) {
$largest = $right;
}
if ($largest !== $i) {
[$this->heap[$i], $this->heap[$largest]] =
[$this->heap[$largest], $this->heap[$i]];
$this->heapify($largest);
}
}
public function display(): void
{
echo "[" . implode(', ', $this->heap) . "]\n";
}
}
// Usage
$pq = new PriorityQueue();
$pq->insert(10);
$pq->insert(5);
$pq->insert(20);
$pq->insert(1);
echo "Max: " . $pq->extractMax() . "\n"; // 20
echo "Max: " . $pq->extractMax() . "\n"; // 10
echo "Max: " . $pq->extractMax() . "\n"; // 5Common Issues:
- extractMax returns null unexpectedly — Check if heap is empty before extraction
- Heap property violated after insert — Ensure bubbleUp is called after adding new element
- Wrong element extracted — Verify you're swapping root with last element and heapifying down
Min Priority Queue
Simply invert the comparisons:
php
# filename: min-priority-queue.php
<?php
declare(strict_types=1);
class MinPriorityQueue
{
private array $heap = [];
public function insert(int $value): void
{
$this->heap[] = $value;
$this->bubbleUp(count($this->heap) - 1);
}
public function extractMin(): ?int
{
if (empty($this->heap)) {
return null;
}
$min = $this->heap[0];
$this->heap[0] = array_pop($this->heap);
if (!empty($this->heap)) {
$this->heapify(0);
}
return $min;
}
// Get size - O(1)
public function size(): int
{
return count($this->heap);
}
// Check if empty - O(1)
public function isEmpty(): bool
{
return empty($this->heap);
}
private function bubbleUp(int $i): void
{
while ($i > 0) {
$parent = (int)(($i - 1) / 2);
// Min heap: child < parent
if ($this->heap[$i] >= $this->heap[$parent]) {
break;
}
[$this->heap[$i], $this->heap[$parent]] =
[$this->heap[$parent], $this->heap[$i]];
$i = $parent;
}
}
private function heapify(int $i): void
{
$n = count($this->heap);
$left = 2 * $i + 1;
$right = 2 * $i + 2;
$smallest = $i;
// Min heap: find smallest
if ($left < $n && $this->heap[$left] < $this->heap[$smallest]) {
$smallest = $left;
}
if ($right < $n && $this->heap[$right] < $this->heap[$smallest]) {
$smallest = $right;
}
if ($smallest !== $i) {
[$this->heap[$i], $this->heap[$smallest]] =
[$this->heap[$smallest], $this->heap[$i]];
$this->heapify($smallest);
}
}
}Priority Queue with Objects
php
# filename: task-queue.php
<?php
declare(strict_types=1);
class Task
{
public function __construct(
public string $name,
public int $priority
) {}
}
class TaskQueue
{
private array $heap = [];
public function insert(Task $task): void
{
$this->heap[] = $task;
$this->bubbleUp(count($this->heap) - 1);
}
public function extractHighestPriority(): ?Task
{
if (empty($this->heap)) {
return null;
}
$task = $this->heap[0];
$this->heap[0] = array_pop($this->heap);
if (!empty($this->heap)) {
$this->heapify(0);
}
return $task;
}
public function isEmpty(): bool
{
return empty($this->heap);
}
private function bubbleUp(int $i): void
{
while ($i > 0) {
$parent = (int)(($i - 1) / 2);
if ($this->heap[$i]->priority <= $this->heap[$parent]->priority) {
break;
}
[$this->heap[$i], $this->heap[$parent]] =
[$this->heap[$parent], $this->heap[$i]];
$i = $parent;
}
}
private function heapify(int $i): void
{
$n = count($this->heap);
$left = 2 * $i + 1;
$right = 2 * $i + 2;
$largest = $i;
if ($left < $n && $this->heap[$left]->priority > $this->heap[$largest]->priority) {
$largest = $left;
}
if ($right < $n && $this->heap[$right]->priority > $this->heap[$largest]->priority) {
$largest = $right;
}
if ($largest !== $i) {
[$this->heap[$i], $this->heap[$largest]] =
[$this->heap[$largest], $this->heap[$i]];
$this->heapify($largest);
}
}
}
// Usage
$queue = new TaskQueue();
$queue->insert(new Task('Low priority task', 1));
$queue->insert(new Task('High priority task', 10));
$queue->insert(new Task('Medium priority task', 5));
$task = $queue->extractHighestPriority();
echo "{$task->name} (priority: {$task->priority})\n";
// Output: High priority task (priority: 10)Real-World Applications
1. Job Scheduling System
php
# filename: job-scheduler.php
<?php
declare(strict_types=1);
class Job
{
public function __construct(
public string $id,
public int $priority,
public callable $task
) {}
}
class JobScheduler
{
private TaskQueue $queue;
public function __construct()
{
$this->queue = new TaskQueue();
}
public function scheduleJob(string $id, int $priority, callable $task): void
{
$job = new Job($id, $priority, $task);
$this->queue->insert($job);
echo "Scheduled job $id with priority $priority\n";
}
public function processNextJob(): void
{
$job = $this->queue->extractHighestPriority();
if ($job === null) {
echo "No jobs in queue\n";
return;
}
echo "Processing job {$job->id}...\n";
($job->task)();
echo "Job {$job->id} completed\n";
}
public function processAll(): void
{
while (!$this->queue->isEmpty()) {
$this->processNextJob();
}
}
}
// Usage
$scheduler = new JobScheduler();
$scheduler->scheduleJob('email', 5, fn() => print("Sending email\n"));
$scheduler->scheduleJob('backup', 10, fn() => print("Running backup\n"));
$scheduler->scheduleJob('cleanup', 1, fn() => print("Cleaning up\n"));
$scheduler->processAll();
// Output:
// Processing job backup... (highest priority)
// Processing job email...
// Processing job cleanup...2. Finding Top K Elements
php
# filename: find-top-k.php
<?php
declare(strict_types=1);
function findTopK(array $nums, int $k): array
{
$minHeap = new MinPriorityQueue();
foreach ($nums as $num) {
$minHeap->insert($num);
// Keep only k largest elements
// Remove smallest when heap exceeds size k
if ($minHeap->size() > $k) {
$minHeap->extractMin();
}
}
// Extract all elements (they're the k largest)
$result = [];
while (!$minHeap->isEmpty()) {
$result[] = $minHeap->extractMin();
}
return array_reverse($result);
}
$numbers = [3, 2, 1, 5, 6, 4];
print_r(findTopK($numbers, 2)); // [5, 6]3. Merge K Sorted Arrays
php
# filename: merge-k-sorted-arrays.php
<?php
declare(strict_types=1);
function mergeKSortedArrays(array $arrays): array
{
$minHeap = new MinPriorityQueue();
$result = [];
// Add first element from each array
$pointers = array_fill(0, count($arrays), 0);
foreach ($arrays as $i => $arr) {
if (!empty($arr)) {
$minHeap->insert(['value' => $arr[0], 'arrayIndex' => $i]);
}
}
// Extract min and add next element from same array
while (!$minHeap->isEmpty()) {
$min = $minHeap->extractMin();
$result[] = $min['value'];
$arrayIndex = $min['arrayIndex'];
$pointers[$arrayIndex]++;
if ($pointers[$arrayIndex] < count($arrays[$arrayIndex])) {
$minHeap->insert([
'value' => $arrays[$arrayIndex][$pointers[$arrayIndex]],
'arrayIndex' => $arrayIndex
]);
}
}
return $result;
}Edge Cases and Special Scenarios
Edge Case 1: Empty or Single Element
php
heapSort([]); // Returns: []
heapSort([42]); // Returns: [42]
// No heap building neededEdge Case 2: Two Elements
php
heapSort([5, 2]); // Returns: [2, 5]
// Build heap: [5, 2] (already max heap)
// Extract: swap and heapifyEdge Case 3: Already Sorted Array
php
$sorted = [1, 2, 3, 4, 5];
// Still O(n log n) - no shortcuts!
// Build heap: [5, 4, 3, 1, 2]
// Extract all: [1, 2, 3, 4, 5]Edge Case 4: Reverse Sorted Array
php
$reversed = [5, 4, 3, 2, 1];
// Also O(n log n) - same work
// Already a max heap!
// Just need to extractEdge Case 5: All Equal Elements
php
$equal = [5, 5, 5, 5, 5];
// O(n log n) - no optimizations
// Build heap: all elements stay in place
// Extract: swap and heapify (minimal work)Edge Case 6: Nearly Sorted Array
php
$nearly = [1, 2, 3, 10, 5, 6, 7, 8, 9];
// O(n log n) - not adaptive
// No benefit from partial orderingHeap Sort vs Other Sorting Algorithms
Comprehensive Comparison
| Feature | Heap Sort | Quick Sort | Merge Sort | Insertion Sort |
|---|---|---|---|---|
| Best time | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Average time | O(n log n) | O(n log n) | O(n log n) | O(n²) |
| Worst time | O(n log n) | O(n²) | O(n log n) | O(n²) |
| Space | O(1) | O(log n) | O(n) | O(1) |
| Stable | No | No | Yes | Yes |
| In-place | Yes | Yes | No | Yes |
| Cache locality | Poor | Excellent | Good | Excellent |
| Adaptive | No | Yes* | No | Yes |
| Practical speed | Slower | Fastest | Fast | Fast (small n) |
*With optimizations
Performance Benchmarks
Test: Various array sizes with random data
| Array Size | Heap Sort | Quick Sort | Merge Sort | Winner |
|---|---|---|---|---|
| 100 | 0.08ms | 0.05ms | 0.08ms | Quick |
| 1,000 | 1.2ms | 0.6ms | 1.2ms | Quick |
| 10,000 | 18ms | 8ms | 15ms | Quick |
| 100,000 | 250ms | 95ms | 180ms | Quick |
| 1,000,000 | 3.2s | 1.1s | 2.1s | Quick |
Key Observations:
- Heap sort: 2-3x slower than optimized quick sort
- Cache performance: Main bottleneck for heap sort
- Guaranteed O(n log n): Same as merge sort
- Memory efficient: Better than merge sort (O(1) vs O(n))
Why Heap Sort is Slower in Practice
Poor Cache Locality:
- Heapify jumps around the array
- Parent-child indices are far apart
- Many cache misses
More Comparisons:
- Every extraction requires log n comparisons
- Quick sort has fewer comparisons on average
Branch Prediction:
- Heap operations harder to predict
- Modern CPUs optimize sequential access better
Cache Miss Example:
php
// Accessing parent and children
$arr[0] // Root: cache line 0
$arr[1] // Left: cache line 0 (good!)
$arr[2] // Right: cache line 0 (good!)
$arr[10] // Child: cache line 2 (cache miss!)
$arr[21] // Grandchild: cache line 5 (cache miss!)
// Many jumps = many cache missesWhen to Use Each
Use Heap Sort When:
- ✅ Need guaranteed O(n log n) (no worst case)
- ✅ Memory is very limited (O(1) space)
- ✅ Finding top K elements efficiently
- ✅ Implementing priority queues
- ✅ Don't need stability
- ✅ Predictable performance required
Use Quick Sort When:
- ✅ Need fastest average case
- ✅ Cache performance matters
- ✅ General-purpose sorting
- ✅ Working with random data
Use Merge Sort When:
- ✅ Need stability
- ✅ Have extra memory (O(n) OK)
- ✅ Sorting linked lists
- ✅ External sorting
Use Insertion Sort When:
- ✅ Array size < 50
- ✅ Data nearly sorted
- ✅ Simplicity matters
Advanced Heap Operations
Decrease-Key and Increase-Key
These operations are crucial for optimizing algorithms like Dijkstra's shortest path. They allow updating an element's priority efficiently.
php
# filename: heap-with-key-operations.php
<?php
declare(strict_types=1);
class MaxHeapWithKeyOps
{
private array $heap = [];
public function insert(int $value): int
{
$this->heap[] = $value;
$index = count($this->heap) - 1;
$this->bubbleUp($index);
return $index;
}
// Increase key (for max heap) - O(log n)
public function increaseKey(int $index, int $newValue): void
{
if ($index < 0 || $index >= count($this->heap)) {
throw new InvalidArgumentException("Index out of bounds");
}
if ($newValue < $this->heap[$index]) {
throw new InvalidArgumentException("New value must be greater than current");
}
$this->heap[$index] = $newValue;
$this->bubbleUp($index);
}
// Decrease key (for max heap) - O(log n)
public function decreaseKey(int $index, int $newValue): void
{
if ($index < 0 || $index >= count($this->heap)) {
throw new InvalidArgumentException("Index out of bounds");
}
if ($newValue > $this->heap[$index]) {
throw new InvalidArgumentException("New value must be less than current");
}
$this->heap[$index] = $newValue;
$this->heapify($index);
}
// Delete specific element - O(log n)
public function delete(int $index): void
{
if ($index < 0 || $index >= count($this->heap)) {
throw new InvalidArgumentException("Index out of bounds");
}
// Replace with max value, bubble up, then extract
$this->heap[$index] = PHP_INT_MAX;
$this->bubbleUp($index);
$this->extractMax();
}
public function extractMax(): ?int
{
if (empty($this->heap)) {
return null;
}
$max = $this->heap[0];
$this->heap[0] = array_pop($this->heap);
if (!empty($this->heap)) {
$this->heapify(0);
}
return $max;
}
private function bubbleUp(int $i): void
{
while ($i > 0) {
$parent = (int)(($i - 1) / 2);
if ($this->heap[$i] <= $this->heap[$parent]) {
break;
}
[$this->heap[$i], $this->heap[$parent]] =
[$this->heap[$parent], $this->heap[$i]];
$i = $parent;
}
}
private function heapify(int $i): void
{
$n = count($this->heap);
$left = 2 * $i + 1;
$right = 2 * $i + 2;
$largest = $i;
if ($left < $n && $this->heap[$left] > $this->heap[$largest]) {
$largest = $left;
}
if ($right < $n && $this->heap[$right] > $this->heap[$largest]) {
$largest = $right;
}
if ($largest !== $i) {
[$this->heap[$i], $this->heap[$largest]] =
[$this->heap[$largest], $this->heap[$i]];
$this->heapify($largest);
}
}
public function display(): array
{
return $this->heap;
}
}
// Usage
$heap = new MaxHeapWithKeyOps();
$idx0 = $heap->insert(10);
$idx1 = $heap->insert(20);
$idx2 = $heap->insert(15);
$idx3 = $heap->insert(30);
echo "Initial heap: " . implode(', ', $heap->display()) . "\n";
// [30, 20, 15, 10]
$heap->increaseKey(3, 35); // Increase 10 to 35
echo "After increasing key at index 3: " . implode(', ', $heap->display()) . "\n";
// [35, 30, 15, 20]
$heap->decreaseKey(0, 5); // Decrease 35 to 5
echo "After decreasing key at index 0: " . implode(', ', $heap->display()) . "\n";
// [30, 20, 15, 5]Why These Matter:
- Dijkstra's Algorithm: Update distances as shorter paths are found
- Prim's MST: Decrease keys when finding minimum spanning tree
- Task Scheduling: Change task priorities dynamically
- A Search*: Update path costs during exploration
Streaming Median with Two Heaps
One of the most elegant heap applications: maintaining the median of a stream of numbers in O(log n) time per insertion.
php
# filename: streaming-median.php
<?php
declare(strict_types=1);
class MedianFinder
{
private SplMaxHeap $lowerHalf; // Max heap for smaller numbers
private SplMinHeap $upperHalf; // Min heap for larger numbers
public function __construct()
{
$this->lowerHalf = new SplMaxHeap();
$this->upperHalf = new SplMinHeap();
}
// Add number - O(log n)
public function addNum(int $num): void
{
// Add to appropriate heap
if ($this->lowerHalf->isEmpty() || $num <= $this->lowerHalf->top()) {
$this->lowerHalf->insert($num);
} else {
$this->upperHalf->insert($num);
}
// Balance heaps (size difference should be at most 1)
if ($this->lowerHalf->count() > $this->upperHalf->count() + 1) {
$this->upperHalf->insert($this->lowerHalf->extract());
} elseif ($this->upperHalf->count() > $this->lowerHalf->count()) {
$this->lowerHalf->insert($this->upperHalf->extract());
}
}
// Find median - O(1)
public function findMedian(): float
{
if ($this->lowerHalf->isEmpty() && $this->upperHalf->isEmpty()) {
throw new RuntimeException("No numbers added");
}
// If odd count, median is top of larger heap (lowerHalf)
if ($this->lowerHalf->count() > $this->upperHalf->count()) {
return (float)$this->lowerHalf->top();
}
// If even count, median is average of both tops
return ($this->lowerHalf->top() + $this->upperHalf->top()) / 2;
}
public function visualize(): void
{
echo "Lower half (max heap): [";
$lower = [];
foreach ($this->lowerHalf as $val) {
$lower[] = $val;
}
echo implode(', ', $lower) . "]\n";
echo "Upper half (min heap): [";
$upper = [];
foreach ($this->upperHalf as $val) {
$upper[] = $val;
}
echo implode(', ', $upper) . "]\n";
}
}
// Usage: Running median
$finder = new MedianFinder();
$numbers = [5, 15, 1, 3, 10, 20, 2];
foreach ($numbers as $num) {
$finder->addNum($num);
echo "After adding $num: median = " . $finder->findMedian() . "\n";
}
// Output:
// After adding 5: median = 5
// After adding 15: median = 10
// After adding 1: median = 5
// After adding 3: median = 4
// After adding 10: median = 5
// After adding 20: median = 7.5
// After adding 2: median = 5How It Works:
- Lower half (max heap): Contains smaller half of numbers, largest on top
- Upper half (min heap): Contains larger half of numbers, smallest on top
- Median: Either top of lower heap (odd count) or average of both tops (even count)
- Balancing: Keep heap sizes equal or differ by 1
Applications:
- Real-time statistics in monitoring systems
- Network traffic analysis
- Database query optimization
- Financial market analysis (moving median)
Merge K Sorted Arrays
A classic problem demonstrating heap efficiency for multi-way merging.
php
# filename: merge-k-sorted-arrays.php
<?php
declare(strict_types=1);
class ArrayElement
{
public function __construct(
public int $value,
public int $arrayIndex,
public int $elementIndex
) {}
}
class MinHeapForMerge extends SplMinHeap
{
protected function compare(mixed $a, mixed $b): int
{
// $a and $b are ArrayElement objects
return $b->value <=> $a->value; // Min heap: smaller values have higher priority
}
}
function mergeKSortedArrays(array $arrays): array
{
$heap = new MinHeapForMerge();
$result = [];
// Add first element from each array to heap
foreach ($arrays as $i => $array) {
if (!empty($array)) {
$heap->insert(new ArrayElement($array[0], $i, 0));
}
}
// Extract min and add next element from same array
while (!$heap->isEmpty()) {
$element = $heap->extract();
$result[] = $element->value;
// If there's a next element in the same array, add it
$nextIndex = $element->elementIndex + 1;
if ($nextIndex < count($arrays[$element->arrayIndex])) {
$heap->insert(new ArrayElement(
$arrays[$element->arrayIndex][$nextIndex],
$element->arrayIndex,
$nextIndex
));
}
}
return $result;
}
// Test
$arrays = [
[1, 4, 7, 10],
[2, 5, 8, 11],
[3, 6, 9, 12],
[0, 13, 14, 15]
];
$merged = mergeKSortedArrays($arrays);
echo "Merged: [" . implode(', ', $merged) . "]\n";
// Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]Complexity Analysis:
- Time: O(n log k) where n = total elements, k = number of arrays
- Space: O(k) for the heap
- Why heap?: Beats naive O(nk) by only comparing k elements at a time
Applications:
- External sorting (merge sorted chunks)
- Database query results merging
- Distributed system data aggregation
- Log file merging from multiple sources
PHP's Built-in SplHeap vs Custom Implementation
PHP provides native heap implementations. Here's when to use each:
php
# filename: spl-heap-comparison.php
<?php
declare(strict_types=1);
// PHP's SplMaxHeap - ready to use
$splHeap = new SplMaxHeap();
$splHeap->insert(10);
$splHeap->insert(30);
$splHeap->insert(20);
echo "SplMaxHeap top: " . $splHeap->top() . "\n"; // 30
// Custom heap with objects
class Task
{
public function __construct(
public string $name,
public int $priority
) {}
}
class TaskHeap extends SplHeap
{
// Compare priorities (higher priority = higher in heap)
protected function compare(mixed $a, mixed $b): int
{
return $a->priority <=> $b->priority;
}
}
$taskHeap = new TaskHeap();
$taskHeap->insert(new Task('Low priority', 1));
$taskHeap->insert(new Task('High priority', 10));
$taskHeap->insert(new Task('Medium priority', 5));
$highest = $taskHeap->extract();
echo "Highest priority task: {$highest->name} (priority: {$highest->priority})\n";
// Output: Highest priority task: High priority (priority: 10)
// SplPriorityQueue - even more convenient
$pq = new SplPriorityQueue();
$pq->insert('Task A', 5);
$pq->insert('Task B', 10);
$pq->insert('Task C', 3);
echo "Highest priority: " . $pq->extract() . "\n"; // Task BWhen to Use Each:
| Feature | Custom Heap | SplHeap | SplPriorityQueue |
|---|---|---|---|
| Learning | ✅ Best | ⚠️ Good | ❌ Abstracted |
| Control | ✅ Full | ✅ Full | ⚠️ Limited |
| Simplicity | ❌ Complex | ⚠️ Medium | ✅ Simple |
| Production | ⚠️ Only if needed | ✅ Recommended | ✅ Recommended |
| Performance | ⚠️ Comparable | ✅ Optimized | ✅ Optimized |
| Type Safety | ✅ Full control | ✅ With extends | ⚠️ Mixed types |
Recommendation:
- Learning: Build custom heaps to understand concepts
- Production: Use
SplHeaporSplPriorityQueuefor reliability and performance - Complex needs: Extend
SplHeapwith custom compare logic
Practice Exercises
Exercise 1: Kth Largest Element
Goal: Use a min heap to efficiently find the kth largest element
Find the kth largest element in an unsorted array:
Requirements:
- Use a min heap of size k
- Insert elements and maintain only k largest
- Return the root (smallest of k largest = kth largest overall)
php
# filename: exercise-kth-largest.php
<?php
declare(strict_types=1);
function findKthLargest(array $nums, int $k): int
{
// Your code here (use min heap of size k)
}
echo findKthLargest([3, 2, 1, 5, 6, 4], 2); // Should output: 5Validation: Test with different k values and array sizes
Exercise 2: Running Median
Goal: Maintain two heaps to efficiently calculate median after each insertion
Calculate median after each element insertion:
Requirements:
- Use max heap for lower half of numbers
- Use min heap for upper half of numbers
- Keep heaps balanced (size difference ≤ 1)
- Median is root of larger heap, or average of both roots if equal size
php
# filename: exercise-running-median.php
<?php
declare(strict_types=1);
class MedianFinder
{
// Use two heaps: max heap for lower half, min heap for upper half
public function addNum(int $num): void
{
// Your code here
}
public function findMedian(): float
{
// Your code here
}
}
// Test
$finder = new MedianFinder();
$finder->addNum(1);
echo $finder->findMedian() . "\n"; // 1.0
$finder->addNum(2);
echo $finder->findMedian() . "\n"; // 1.5
$finder->addNum(3);
echo $finder->findMedian() . "\n"; // 2.0Validation: Verify median calculation after each insertion
Exercise 3: Reorganize String
Goal: Use priority queue to rearrange characters avoiding adjacent duplicates
Rearrange string so no two adjacent characters are the same:
Requirements:
- Count character frequencies
- Use max heap to prioritize most frequent characters
- Alternate characters, avoiding placing same character consecutively
- Return empty string if reorganization is impossible
php
# filename: exercise-reorganize-string.php
<?php
declare(strict_types=1);
function reorganizeString(string $s): string
{
// Your code here (use max heap for character frequencies)
}
echo reorganizeString('aab'); // Should output: 'aba' or 'baa'
echo reorganizeString('aaab'); // Should output: '' (impossible)Validation: Test with various string patterns and edge cases
Key Takeaways
- Heap is a complete binary tree with heap property
- Heap sort is O(n log n) for all cases, in-place
- Build heap is O(n), not O(n log n)
- Priority queue enables efficient priority-based processing
- Not cache-friendly compared to quick sort
- Not stable - equal elements may be reordered
- Excellent for top K problems and job scheduling
Wrap-up
Congratulations! You've mastered one of the most elegant and versatile data structures in computer science. You now understand:
- ✓ How heaps maintain their special parent-child relationship property
- ✓ Why building a heap from an array is O(n), not O(n log n)
- ✓ How Heap Sort achieves guaranteed O(n log n) time with O(1) space
- ✓ How priority queues enable efficient task scheduling and prioritization
- ✓ Advanced heap operations: decrease-key and increase-key for algorithm optimization
- ✓ The elegant two-heap pattern for streaming median calculation
- ✓ How heaps power efficient K-way merging in O(n log k) time
- ✓ When to choose Heap Sort over Quick Sort or Merge Sort
- ✓ How to implement both max heaps and min heaps for different use cases
- ✓ When to use PHP's SplHeap/SplPriorityQueue vs custom implementations
Heaps are everywhere in real-world systems: Operating system schedulers use priority queues to manage processes, database query optimizers use heaps for merge operations, and graph algorithms like Dijkstra's shortest path rely on heaps for efficiency. You've gained a foundational tool used throughout computer science.
What You've Achieved
You can now implement complete heap data structures from scratch, understand the trade-offs between different O(n log n) sorting algorithms, and apply heaps to solve practical problems like finding top K elements or scheduling tasks by priority. This knowledge prepares you for advanced algorithms in graphs, streams, and system design.
Next Steps
In Chapter 09, we'll compare all the sorting algorithms we've learned, benchmark them head-to-head, and create a decision framework for choosing the right algorithm for your specific use case.
Further Reading
To deepen your understanding of heaps and their applications:
- PHP: SplHeap Class — PHP's built-in heap implementation
- PHP: SplPriorityQueue Class — Native priority queue data structure
- Heap Data Structure (Wikipedia) — Comprehensive overview with variants
- Priority Queue Applications — Real-world use cases from operating systems to AI
- Heapsort Analysis (Khan Academy) — Interactive visualization and proof of O(n) build heap complexity
💻 Code Samples
All code examples from this chapter are available in the GitHub repository:
Files included:
01-heap-sort.php— Heap sort algorithm with visualization and performance analysis02-priority-queue.php— Max heap-based priority queue for task scheduling and prioritization03-heap-with-key-operations.php— Decrease-key and increase-key operations for advanced algorithms04-streaming-median.php— Two-heap pattern for maintaining running median05-merge-k-sorted-arrays.php— Efficient K-way merge using min heap06-spl-heap-comparison.php— PHP's SplHeap vs custom implementationsREADME.md— Complete documentation and usage guide
Clone the repository to run the examples locally:
bash
git clone https://github.com/dalehurley/codewithphp.git
cd codewithphp/code/php-algorithms/chapter-08
php 01-heap-sort.phpContinue to Chapter 09: Comparing Sorting Algorithms.