8.2 Heap Data Structure and Operations

Heap Data Structure

A binary heap is a tree-based data structure that keeps elements in a partially sorted order, guaranteeing fast access to either the minimum or maximum element. Heaps are the go-to backing structure for priority queues and play a central role in algorithms like heapsort and Dijkstra's shortest path.

Structure and Properties of Binary Heaps

A binary heap must satisfy two properties:

1. Complete binary tree: Every level is fully filled except possibly the last, and the last level is filled left to right. This shape guarantee is what makes the array-based implementation work so cleanly.
2. Heap ordering property: Every parent node has a specific relationship with its children (defined by whether it's a min-heap or max-heap).

One thing that trips people up: there's no ordering between sibling nodes. Just because the left child is smaller than the right child in one subtree doesn't mean that holds everywhere. The only guarantee is the parent-child relationship.

Min-Heaps vs Max-Heaps

• Min-heap: Every parent is less than or equal to its children. The root always holds the smallest value. This is the standard choice when you need to repeatedly extract the minimum, like in task scheduling where the lowest-priority (or earliest-deadline) task should come out first.
• Max-heap: Every parent is greater than or equal to its children. The root always holds the largest value. Useful when you need the maximum quickly, such as in event-driven simulations where the highest-priority event fires next.

The operations work identically for both; the only difference is the direction of the comparison (less-than vs. greater-than).

Array-Based Implementation of Heaps

Because a binary heap is always a complete binary tree, you can store it in a flat array with no pointers at all. The tree structure is encoded entirely through index arithmetic.

For a node at index $i$ (using 0-based indexing):

</>Code
        2          index 0
       / \
      5   3        indices 1, 2
     / \
    8   7          indices 3, 4

Node 5 is at index 1. Its left child is at $2(1)+1 = 3$ (which is 8), and its parent is at $\lfloor(1-1)/2\rfloor = 0$ (which is 2). This direct index calculation is what makes heap operations fast with no pointer chasing.

Heap Operations

Insertion (Heapify-Up)

To insert a new element into a min-heap:

1. Place the new element at the end of the array (the next open position in the last level).

2. Compare it with its parent at index $\lfloor(i - 1) / 2\rfloor$.

3. If the new element is smaller than its parent, swap them.

4. Repeat steps 2-3, moving upward, until the element is greater than or equal to its parent, or it becomes the root.

Walkthrough: Insert 1 into the min-heap [2, 5, 3, 8, 7].

• Place 1 at index 5. Parent is at index $\lfloor(5-1)/2\rfloor = 2$, which holds 3. Since $1 < 3$, swap. Array: [2, 5, 1, 8, 7, 3].
• Now 1 is at index 2. Parent is at index $\lfloor(2-1)/2\rfloor = 0$, which holds 2. Since $1 < 2$, swap. Array: [1, 5, 2, 8, 7, 3].
• Now 1 is at index 0 (the root). Done.

Deletion (Heapify-Down)

Deletion always removes the root (the min or max element). To delete from a min-heap:

1. Replace the root with the last element in the array, then shrink the array by one.
2. Compare the new root with both of its children.
3. Swap it with the smaller child if the heap property is violated. (In a max-heap, you'd swap with the larger child.)
4. Repeat steps 2-3, moving downward, until the element is smaller than or equal to both children, or it reaches a leaf.

Walkthrough: Delete the root from [1, 5, 2, 8, 7, 3].

• Remove 1, move last element (3) to the root. Array: [3, 5, 2, 8, 7].
• Compare 3 with children: left child 5 (index 1), right child 2 (index 2). Smaller child is 2. Since $3 > 2$, swap. Array: [2, 5, 3, 8, 7].
• Now 3 is at index 2. Its left child would be at index $2(2)+1 = 5$, which is out of bounds. 3 is a leaf. Done.

Peek

Peek simply returns the element at index 0 without modifying anything.

Time Complexity of Heap Operations

The height of a complete binary tree with $n$ nodes is $\lfloor \log_2 n \rfloor$, which is where the $O(\log n)$ bound comes from.

Build heap deserves a closer look. You might expect $O(n \log n)$ since you're calling heapify-down on multiple nodes. But most nodes are near the bottom of the tree and only need to sift down a short distance. Mathematically, the work sums to $O(n)$. The key detail: you start heapifying from the last non-leaf node (index $\lfloor n/2 \rfloor - 1$) and work backward to the root, calling heapify-down on each. This bottom-up approach is what makes it linear.