Tree Structures Lesson 9

Heaps & Priority Systems

intermediate ⏱️ 45 minutes 🌍 Task scheduling in operating systems, event simulations, shortest path algorithms (Dijkstra's)

Heaps & Priority Systems

We’ve explored various data structures, from linear arrays and linked lists to hierarchical binary search trees. Now, we’ll introduce Heaps, a special type of binary tree that combines the best aspects of arrays (compact storage) and trees (hierarchical relationships) to efficiently manage elements based on their priority. Heaps are the backbone of priority queues and critical for many algorithms in priority-based systems.

Min-Heap Representation

A complete binary tree with the heap property, typically stored in an array.

Array View:

0
1
2
3
4
5
2
3
5
8
4
15

Root at index 0. Children: `2i+1`, `2i+2`. Parent: `(i-1)/2`.

↔️

Tree View

Tree View:

2 3 5 8 4 15

**Heap Property (Min-Heap):** Root is smallest, and every parent is smaller than its children.

🏔️ What is a Heap?

A Heap is a specialized tree-based data structure that satisfies the heap property. In most implementations, a heap is a binary tree that is also a complete binary tree.

Heap Properties:

  1. Heap Property: For every node N in the heap:
    • In a Max-Heap: The value of N is greater than or equal to the values of its children. The largest element is always at the root.
    • In a Min-Heap: The value of N is less than or equal to the values of its children. The smallest element is always at the root.
  2. Complete Binary Tree Property: All levels of the tree are fully filled, except possibly the last level, which is filled from left to right. This property ensures that a heap can be efficiently represented using an array.

Heap as an Array: Because of the complete binary tree property, a heap can be efficiently stored in a simple array:

  • If a node is at index i:
    • Its parent is at index (i - 1) / 2 (integer division).
    • Its left child is at index 2 * i + 1.
    • Its right child is at index 2 * i + 2.
  • The root is always at index 0.

Analogy: Imagine a company hierarchy where the CEO is always the ‘highest priority’ (Max-Heap) or ‘lowest cost’ (Min-Heap) employee, and managers below them have lower (or higher) priority than their own subordinates. You can quickly see the top boss, but finding a specific employee might take a few steps down the chain.

🏗️ Heap Operations

The primary operations for a heap involve maintaining the heap property after an insertion or deletion.

1. Insert (Push)

To insert a new element:

  1. Add the new element to the next available position in the array (the end of the heap, maintaining completeness).
  2. “Heapify Up” (or “Percolate Up” / “Bubble Up”): Compare the new element with its parent. If it violates the heap property (e.g., in a min-heap, child < parent), swap them. Repeat this process recursively until the heap property is restored or the root is reached.

2. Extract Min/Max (Pop)

To remove the highest (or lowest) priority element (always at the root):

  1. Replace the root with the last element in the heap array.
  2. Remove the last element from the array (which was the old root, now stored in a temp variable).
  3. “Heapify Down” (or “Percolate Down” / “Bubble Down”): Compare the new root with its children. If it violates the heap property (e.g., in a min-heap, root > a child), swap it with the smaller (for min-heap) or larger (for max-heap) child. Repeat this process recursively until the heap property is restored or a leaf node is reached.

3. Peek (Get Min/Max)

Simply return the element at the root (index 0) of the heap array. This is an O(1) operation.

Min-Heap Implementation (Array-based)

        
          
#include <stdio.h>
#include <stdlib.h>

#define MAX_HEAP_SIZE 100 // Example fixed size for array

typedef struct {
  int arr[MAX_HEAP_SIZE];
  int size;
} MinHeap;

// Helper: Swap two elements
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

// Helper: Get parent, left, right child indices
int parent(int i) { return (i - 1) / 2; }
int left_child(int i) { return (2 * i + 1); }
int right_child(int i) { return (2 * i + 2); }

// Helper: Heapify Up (restore heap property upwards after insertion)
void heapify_up(MinHeap *heap, int i) {
  while (i != 0 && heap->arr[parent(i)] > heap->arr[i]) {
      swap(&heap->arr[i], &heap->arr[parent(i)]);
      i = parent(i);
  }
}

// Helper: Heapify Down (restore heap property downwards after deletion/extract)
void heapify_down(MinHeap *heap, int i) {
  int l = left_child(i);
  int r = right_child(i);
  int smallest = i;

  if (l < heap->size && heap->arr[l] < heap->arr[i])
      smallest = l;
  if (r < heap->size && heap->arr[r] < heap->arr[smallest])
      smallest = r;

  if (smallest != i) {
      swap(&heap->arr[i], &heap->arr[smallest]);
      heapify_down(heap, smallest);
  }
}

// Initialize heap
void init_min_heap(MinHeap *heap) {
  heap->size = 0;
}

// Insert an element (O(log N))
void insert_min_heap(MinHeap *heap, int val) {
  if (heap->size == MAX_HEAP_SIZE) {
      printf("Error: Heap is full!\n");
      return;
  }
  heap->size++;
  int i = heap->size - 1;
  heap->arr[i] = val;
  heapify_up(heap, i);
}

// Extract minimum element (O(log N))
int extract_min_heap(MinHeap *heap) {
  if (heap->size <= 0) {
      printf("Error: Heap is empty!\n");
      return -1; // Or throw error
  }
  if (heap->size == 1) {
      heap->size--;
      return heap->arr[0];
  }

  int root = heap->arr[0];
  heap->arr[0] = heap->arr[heap->size - 1]; // Move last element to root
  heap->size--;
  heapify_down(heap, 0); // Restore heap property from root
  return root;
}

// Peek minimum element (O(1))
int peek_min_heap(MinHeap *heap) {
  if (heap->size <= 0) {
      printf("Error: Heap is empty for peek!\n");
      return -1;
  }
  return heap->arr[0];
}

// Main for demonstration
int main() {
  MinHeap heap;
  init_min_heap(&heap);

  insert_min_heap(&heap, 3);
  insert_min_heap(&heap, 2);
  insert_min_heap(&heap, 15);
  insert_min_heap(&heap, 5);
  insert_min_heap(&heap, 4);
  insert_min_heap(&heap, 45);

  printf("Min-Heap Peek: %d\n", peek_min_heap(&heap)); // Expected: 2

  printf("Extracting minimum: %d\n", extract_min_heap(&heap)); // 2
  printf("Min-Heap Peek after extract: %d\n", peek_min_heap(&heap)); // Expected: 3

  printf("Extracting minimum: %d\n", extract_min_heap(&heap)); // 3
  printf("Extracting minimum: %d\n", extract_min_heap(&heap)); // 4
  printf("Extracting minimum: %d\n", extract_min_heap(&heap)); // 5

  return 0;
}
        
      

        
          
# Python's 'heapq' module implements a min-heap
import heapq

class MinHeap:
  def __init__(self):
      self._heap = [] # Internal list to store heap elements

  def is_empty(self):
      return len(self._heap) == 0

  def insert(self, item): # O(log N)
      heapq.heappush(self._heap, item)

  def extract_min(self): # O(log N)
      if self.is_empty():
          raise IndexError("extract_min from empty heap")
      return heapq.heappop(self._heap)

  def peek_min(self): # O(1)
      if self.is_empty():
          raise IndexError("peek_min from empty heap")
      return self._heap[0]

  def size(self):
      return len(self._heap)

# Main for demonstration
heap = MinHeap()
heap.insert(3)
heap.insert(2)
heap.insert(15)
heap.insert(5)
heap.insert(4)
heap.insert(45)

print(f"Min-Heap Peek: {heap.peek_min()}") # Expected: 2

print(f"Extracting minimum: {heap.extract_min()}") # 2
print(f"Min-Heap Peek after extract: {heap.peek_min()}") # Expected: 3

print(f"Extracting minimum: {heap.extract_min()}") # 3
print(f"Extracting minimum: {heap.extract_min()}") # 4
print(f"Extracting minimum: {heap.extract_min()}") # 5

        
      

        
          
// JavaScript doesn't have a built-in heap. This is a conceptual implementation.
// For real applications, use a library or a robust custom class.

class MinHeap {
  constructor() {
      this._heap = []; // Array to store heap elements
  }

  _getParentIndex(i) { return Math.floor((i - 1) / 2); }
  _getLeftChildIndex(i) { return 2 * i + 1; }
  _getRightChildIndex(i) { return 2 * i + 2; }

  _hasParent(i) { return this._getParentIndex(i) >= 0; }
  _hasLeftChild(i) { return this._getLeftChildIndex(i) < this._heap.length; }
  _hasRightChild(i) { return this._getRightChildIndex(i) < this._heap.length; }

  _getParent(i) { return this._heap[this._getParentIndex(i)]; }
  _getLeftChild(i) { return this._heap[this._getLeftChildIndex(i)]; }
  _getRightChild(i) { return this._heap[this._getRightChildIndex(i)]; }

  _swap(i, j) {
      [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];
  }

  isEmpty() { return this._heap.length === 0; }
  size() { return this._heap.length; }

  insert(item) { // O(log N)
      this._heap.push(item);
      this._heapifyUp();
  }

  peekMin() { // O(1)
      if (this.isEmpty()) throw new Error("Heap is empty");
      return this._heap[0];
  }

  extractMin() { // O(log N)
      if (this.isEmpty()) throw new Error("Heap is empty");
      if (this._heap.length === 1) return this._heap.pop();

      const item = this._heap[0];
      this._heap[0] = this._heap.pop(); // Move last element to root
      this._heapifyDown();
      return item;
  }

  _heapifyUp() {
      let index = this._heap.length - 1;
      while (this._hasParent(index) && this._getParent(index) > this._heap[index]) {
          this._swap(this._getParentIndex(index), index);
          index = this._getParentIndex(index);
      }
  }

  _heapifyDown() {
      let index = 0;
      while (this._hasLeftChild(index)) {
          let smallerChildIndex = this._getLeftChildIndex(index);
          if (this._hasRightChild(index) && this._getRightChild(index) < this._getLeftChild(index)) {
              smallerChildIndex = this._getRightChildIndex(index);
          }

          if (this._heap[index] < this._heap[smallerChildIndex]) {
              break;
          } else {
              this._swap(index, smallerChildIndex);
          }
          index = smallerChildIndex;
      }
  }
}

// Main for demonstration
const heap = new MinHeap();
heap.insert(3);
heap.insert(2);
heap.insert(15);
heap.insert(5);
heap.insert(4);
heap.insert(45);

console.log("Min-Heap Peek:", heap.peekMin()); // Expected: 2

console.log("Extracting minimum:", heap.extractMin()); // 2
console.log("Min-Heap Peek after extract:", heap.peekMin()); // Expected: 3

console.log("Extracting minimum:", heap.extractMin()); // 3
console.log("Extracting minimum:", heap.extractMin()); // 4
console.log("Extracting minimum:", heap.extractMin()); // 5

Complexity (Heap Operations):

  • Insert (Push): O(log N) - The heapify-up operation involves traversing at most the height of the tree.
  • Extract Min/Max (Pop): O(log N) - Replacing the root and heapify-down involves traversing at most the height of the tree.
  • Peek Min/Max: O(1) - The min/max element is always at the root.
  • Space Complexity: O(N) for storing N elements in an array.

Note: Because a heap is a complete binary tree, it’s very efficient to store it in a flat array. This means less memory overhead compared to a linked-node tree (which needs pointers for each child) and better cache locality because elements are stored contiguously in memory.

⭐️ Priority Queues

A Priority Queue is an abstract data type that is like a regular queue or stack, but each element has a “priority” associated with it. Elements with higher priority are served before elements with lower priority. If two elements have the same priority, they are served according to their order in the queue.

How Heaps implement Priority Queues: Heaps are the most common and efficient way to implement priority queues.

  • Enqueue (add to PQ): Corresponds to the heap’s insert operation. The new element is added, and heapify-up ensures the heap property is maintained.
  • Dequeue (remove highest priority from PQ): Corresponds to the heap’s extract-min (for min-priority queues) or extract-max (for max-priority queues) operation. The highest priority element (root) is removed, and heapify-down restores the heap property.

This ensures that finding and removing the highest priority item is always efficient.

Analogy: The emergency room at a hospital. Patients aren’t seen in order of arrival (FIFO), but by the severity of their condition (priority).

🚀 Priority Systems in Action

Priority queues, powered by heaps, are critical in many real-world systems where task order isn’t strictly sequential but driven by importance or urgency.

Practical Usages:

  • Task Scheduling in Operating Systems: Processes are scheduled based on priority, with high-priority tasks (e.g., user input) getting CPU time before low-priority tasks (e.g., background updates).
  • Event-Driven Simulations: In simulations (e.g., traffic flow, ecosystem models), events need to be processed in chronological order. A priority queue can store future events, ordered by their timestamp.
  • Shortest Path Algorithms (Dijkstra’s Algorithm, Prim’s Algorithm): These graph algorithms use a priority queue to efficiently select the next edge or node to visit based on the lowest cost.
  • Huffman Coding: Used for data compression, Huffman trees are built using a min-priority queue to repeatedly combine the two lowest frequency symbols.
  • Load Balancing: Distributing requests across servers based on server load or task priority.
  • Undo/Redo Functionality (Advanced): While a simple stack might suffice, some applications might prioritize certain undoable actions.

Interesting Note: The ability of heaps to provide O(log N) insertion and O(log N) extraction of the highest/lowest priority item, combined with O(1) peek, makes them superior to other data structures for priority queue functionality. For example, using a sorted array would give O(1) peek but O(N) insert/delete, while an unsorted array would give O(1) insert but O(N) extract.