Heap Data Structure

calendarDec 13, 2025 · 9 min read · heap priority-queue data-structures binary-heap  ·
Share on: linkedincopy

A heap is a specialized tree-based data structure that satisfies the heap property. It's commonly used to implement priority queues and for efficient sorting (heapsort).

Heap Property

Max-Heap Property

For every node $i$ other than the root:

$$ A[\text{parent}(i)] \geq A[i] $$

The parent's value is greater than or equal to its children's values. The maximum element is at the root.

Min-Heap Property

For every node $i$ other than the root:

$$ A[\text{parent}(i)] \leq A[i] $$

The parent's value is less than or equal to its children's values. The minimum element is at the root.

Binary Heap Structure

A binary heap is a complete binary tree stored as an array. For a node at index $i$:

  • Parent index: $\lfloor (i-1)/2 \rfloor$
  • Left child index: $2i + 1$
  • Right child index: $2i + 2$

Array Representation

Array: [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

Core Operations

1. Heapify (Bubble Down)

Maintains the heap property by moving a node down the tree.

Time Complexity: $O(\log n)$

Process:

  1. Compare node with its children
  2. If heap property is violated, swap with the larger child (max-heap) or smaller child (min-heap)
  3. Recursively heapify the affected subtree

Mathematical Analysis:

  • Height of heap: $h = \lfloor \log_2 n \rfloor$
  • Maximum swaps: $h = O(\log n)$
 1// MaxHeap implementation
 2type MaxHeap struct {
 3    items []int
 4}
 5
 6// Heapify maintains max-heap property at index i
 7func (h *MaxHeap) heapify(i int) {
 8    n := len(h.items)
 9    largest := i
10    left := 2*i + 1
11    right := 2*i + 2
12    
13    // Find largest among node and its children
14    if left < n && h.items[left] > h.items[largest] {
15        largest = left
16    }
17    if right < n && h.items[right] > h.items[largest] {
18        largest = right
19    }
20    
21    // If largest is not root, swap and continue heapifying
22    if largest != i {
23        h.items[i], h.items[largest] = h.items[largest], h.items[i]
24        h.heapify(largest)
25    }
26}

2. Bubble Up (Sift Up)

Moves a node up the tree to restore heap property.

Time Complexity: $O(\log n)$

 1// bubbleUp moves element at index i up to restore heap property
 2func (h *MaxHeap) bubbleUp(i int) {
 3    for i > 0 {
 4        parent := (i - 1) / 2
 5        
 6        if h.items[parent] >= h.items[i] {
 7            break // Heap property satisfied
 8        }
 9        
10        // Swap with parent
11        h.items[i], h.items[parent] = h.items[parent], h.items[i]
12        i = parent
13    }
14}

3. Insert

Add a new element to the heap.

Time Complexity: $O(\log n)$

 1// Insert adds a new element to the heap
 2func (h *MaxHeap) Insert(value int) {
 3    // Add element at the end
 4    h.items = append(h.items, value)
 5    
 6    // Bubble up to restore heap property
 7    h.bubbleUp(len(h.items) - 1)
 8}
 9
10// Example
11func main() {
12    heap := &MaxHeap{}
13    heap.Insert(10)
14    heap.Insert(5)
15    heap.Insert(15)
16    heap.Insert(3)
17    
18    fmt.Println(heap.items) // [15, 10, 5, 3]
19}

4. Extract Max/Min

Remove and return the root element.

Time Complexity: $O(\log n)$

 1// ExtractMax removes and returns the maximum element
 2func (h *MaxHeap) ExtractMax() (int, error) {
 3    if len(h.items) == 0 {
 4        return 0, errors.New("heap is empty")
 5    }
 6    
 7    // Store root value
 8    max := h.items[0]
 9    
10    // Move last element to root
11    lastIdx := len(h.items) - 1
12    h.items[0] = h.items[lastIdx]
13    h.items = h.items[:lastIdx]
14    
15    // Heapify root
16    if len(h.items) > 0 {
17        h.heapify(0)
18    }
19    
20    return max, nil
21}
22
23// Example
24func main() {
25    heap := &MaxHeap{items: []int{16, 14, 10, 8, 7, 9, 3, 2, 4, 1}}
26    
27    max, _ := heap.ExtractMax()
28    fmt.Println(max)         // Output: 16
29    fmt.Println(heap.items)  // [14, 8, 10, 4, 7, 9, 3, 2, 1]
30}

5. Peek

Return the root element without removing it.

Time Complexity: $O(1)$

1// Peek returns the maximum element without removing it
2func (h *MaxHeap) Peek() (int, error) {
3    if len(h.items) == 0 {
4        return 0, errors.New("heap is empty")
5    }
6    return h.items[0], nil
7}

6. Build Heap

Convert an arbitrary array into a heap.

Time Complexity: $O(n)$ - surprisingly linear!

Process:

  1. Start from the last non-leaf node: $\lfloor n/2 \rfloor - 1$
  2. Heapify each node moving backwards to the root

Why $O(n)$?

The sum of work done at each level:

$$ \sum_{h=0}^{\lfloor \log n \rfloor} \frac{n}{2^{h+1}} \cdot h = O(n) $$

Most nodes are near the leaves and require minimal work. Only a few nodes near the root require $O(\log n)$ operations.

 1// BuildMaxHeap converts array to max-heap in-place
 2func BuildMaxHeap(arr []int) *MaxHeap {
 3    h := &MaxHeap{items: arr}
 4    n := len(arr)
 5    
 6    // Start from last non-leaf node and heapify all
 7    for i := n/2 - 1; i >= 0; i-- {
 8        h.heapify(i)
 9    }
10    
11    return h
12}
13
14// Example
15func main() {
16    arr := []int{4, 10, 3, 5, 1}
17    heap := BuildMaxHeap(arr)
18    fmt.Println(heap.items) // [10, 5, 3, 4, 1]
19}

Heapify Process Visualization

Complexity Summary

OperationTime Complexity
Insert$O(\log n)$
Extract Max/Min$O(\log n)$
Peek$O(1)$
Heapify$O(\log n)$
Build Heap$O(n)$
Search$O(n)$

Space Complexity: $O(1)$ auxiliary (in-place operations)

Complete Go Implementation

  1package main
  2
  3import (
  4    "errors"
  5    "fmt"
  6)
  7
  8type MaxHeap struct {
  9    items []int
 10}
 11
 12func (h *MaxHeap) parent(i int) int { return (i - 1) / 2 }
 13func (h *MaxHeap) left(i int) int   { return 2*i + 1 }
 14func (h *MaxHeap) right(i int) int  { return 2*i + 2 }
 15
 16func (h *MaxHeap) swap(i, j int) {
 17    h.items[i], h.items[j] = h.items[j], h.items[i]
 18}
 19
 20func (h *MaxHeap) heapify(i int) {
 21    n := len(h.items)
 22    largest := i
 23    left := h.left(i)
 24    right := h.right(i)
 25    
 26    if left < n && h.items[left] > h.items[largest] {
 27        largest = left
 28    }
 29    if right < n && h.items[right] > h.items[largest] {
 30        largest = right
 31    }
 32    
 33    if largest != i {
 34        h.swap(i, largest)
 35        h.heapify(largest)
 36    }
 37}
 38
 39func (h *MaxHeap) bubbleUp(i int) {
 40    for i > 0 && h.items[h.parent(i)] < h.items[i] {
 41        p := h.parent(i)
 42        h.swap(i, p)
 43        i = p
 44    }
 45}
 46
 47func (h *MaxHeap) Insert(value int) {
 48    h.items = append(h.items, value)
 49    h.bubbleUp(len(h.items) - 1)
 50}
 51
 52func (h *MaxHeap) ExtractMax() (int, error) {
 53    if len(h.items) == 0 {
 54        return 0, errors.New("heap is empty")
 55    }
 56    
 57    max := h.items[0]
 58    lastIdx := len(h.items) - 1
 59    h.items[0] = h.items[lastIdx]
 60    h.items = h.items[:lastIdx]
 61    
 62    if len(h.items) > 0 {
 63        h.heapify(0)
 64    }
 65    
 66    return max, nil
 67}
 68
 69func (h *MaxHeap) Peek() (int, error) {
 70    if len(h.items) == 0 {
 71        return 0, errors.New("heap is empty")
 72    }
 73    return h.items[0], nil
 74}
 75
 76func (h *MaxHeap) Size() int {
 77    return len(h.items)
 78}
 79
 80func BuildMaxHeap(arr []int) *MaxHeap {
 81    h := &MaxHeap{items: make([]int, len(arr))}
 82    copy(h.items, arr)
 83    
 84    for i := len(arr)/2 - 1; i >= 0; i-- {
 85        h.heapify(i)
 86    }
 87    
 88    return h
 89}
 90
 91// Heapsort using heap
 92func HeapSort(arr []int) []int {
 93    heap := BuildMaxHeap(arr)
 94    result := make([]int, len(arr))
 95    
 96    for i := len(arr) - 1; i >= 0; i-- {
 97        result[i], _ = heap.ExtractMax()
 98    }
 99    
100    return result
101}
102
103func main() {
104    // Example usage
105    heap := &MaxHeap{}
106    
107    values := []int{4, 10, 3, 5, 1, 15, 7}
108    for _, v := range values {
109        heap.Insert(v)
110        fmt.Printf("Inserted %d: %v\n", v, heap.items)
111    }
112    
113    fmt.Println("\nExtracting max values:")
114    for heap.Size() > 0 {
115        max, _ := heap.ExtractMax()
116        fmt.Printf("Extracted %d, remaining: %v\n", max, heap.items)
117    }
118    
119    // Build heap from array
120    arr := []int{4, 10, 3, 5, 1}
121    heap2 := BuildMaxHeap(arr)
122    fmt.Printf("\nBuilt heap from %v: %v\n", arr, heap2.items)
123    
124    // Heapsort
125    unsorted := []int{4, 10, 3, 5, 1, 15, 7}
126    sorted := HeapSort(unsorted)
127    fmt.Printf("\nHeapsort %v: %v\n", unsorted, sorted)
128}

Min-Heap Implementation

 1type MinHeap struct {
 2    items []int
 3}
 4
 5func (h *MinHeap) heapify(i int) {
 6    n := len(h.items)
 7    smallest := i
 8    left := 2*i + 1
 9    right := 2*i + 2
10    
11    if left < n && h.items[left] < h.items[smallest] {
12        smallest = left
13    }
14    if right < n && h.items[right] < h.items[smallest] {
15        smallest = right
16    }
17    
18    if smallest != i {
19        h.items[i], h.items[smallest] = h.items[smallest], h.items[i]
20        h.heapify(smallest)
21    }
22}
23
24func (h *MinHeap) Insert(value int) {
25    h.items = append(h.items, value)
26    i := len(h.items) - 1
27    
28    for i > 0 {
29        parent := (i - 1) / 2
30        if h.items[parent] <= h.items[i] {
31            break
32        }
33        h.items[i], h.items[parent] = h.items[parent], h.items[i]
34        i = parent
35    }
36}
37
38func (h *MinHeap) ExtractMin() (int, error) {
39    if len(h.items) == 0 {
40        return 0, errors.New("heap is empty")
41    }
42    
43    min := h.items[0]
44    lastIdx := len(h.items) - 1
45    h.items[0] = h.items[lastIdx]
46    h.items = h.items[:lastIdx]
47    
48    if len(h.items) > 0 {
49        h.heapify(0)
50    }
51    
52    return min, nil
53}

Applications

1. Priority Queue

 1type Task struct {
 2    name     string
 3    priority int
 4}
 5
 6type PriorityQueue struct {
 7    heap *MaxHeap
 8    tasks map[int][]Task
 9}
10
11func (pq *PriorityQueue) Enqueue(task Task) {
12    pq.heap.Insert(task.priority)
13    pq.tasks[task.priority] = append(pq.tasks[task.priority], task)
14}
15
16func (pq *PriorityQueue) Dequeue() (Task, error) {
17    priority, err := pq.heap.ExtractMax()
18    if err != nil {
19        return Task{}, err
20    }
21    
22    tasks := pq.tasks[priority]
23    task := tasks[0]
24    pq.tasks[priority] = tasks[1:]
25    
26    return task, nil
27}

2. Heapsort

Sort an array in $O(n \log n)$ time:

  1. Build max-heap: $O(n)$
  2. Extract max $n$ times: $O(n \log n)$

Total: $O(n \log n)$

3. K-th Largest/Smallest Element

Use a min-heap of size $k$ to find the $k$-th largest element in $O(n \log k)$ time.

 1func FindKthLargest(nums []int, k int) int {
 2    minHeap := &MinHeap{}
 3    
 4    for _, num := range nums {
 5        minHeap.Insert(num)
 6        if minHeap.Size() > k {
 7            minHeap.ExtractMin()
 8        }
 9    }
10    
11    result, _ := minHeap.Peek()
12    return result
13}

4. Merge K Sorted Arrays

 1type HeapNode struct {
 2    value    int
 3    arrayIdx int
 4    elemIdx  int
 5}
 6
 7func MergeKSortedArrays(arrays [][]int) []int {
 8    // Use min-heap to track smallest element from each array
 9    // Time: O(N log k) where N is total elements, k is number of arrays
10    
11    result := []int{}
12    // Implementation details omitted for brevity
13    return result
14}

Heap vs. Binary Search Tree

FeatureHeapBST
StructureComplete binary treeCan be unbalanced
OrderingPartial (heap property)Total (in-order traversal)
Find min/max$O(1)$$O(h)$, $O(\log n)$ if balanced
Search arbitrary$O(n)$$O(h)$, $O(\log n)$ if balanced
Insert$O(\log n)$$O(h)$, $O(\log n)$ if balanced
Delete$O(\log n)$$O(h)$, $O(\log n)$ if balanced
Space efficiencyCompact (array)Pointers overhead

When to Use Heaps

✅ Use when:

  • Need repeated access to min/max element
  • Priority-based processing
  • Don't need to search for arbitrary elements
  • Want $O(1)$ space overhead

❌ Don't use when:

  • Need to search for arbitrary elements frequently
  • Need sorted order of all elements
  • Need to find k-th smallest efficiently (use selection algorithms instead)

Related Snippets

  • Binary Search
    Binary search is an efficient algorithm for finding a target value in a sorted …
  • Binary Tree
    A binary tree is a tree data structure where each node has at most two children, …
  • General Tree
    A tree is a hierarchical data structure consisting of nodes connected by edges, …
  • Heap Sort
    Heap sort is a comparison-based sorting algorithm that uses a binary heap data …
  • Linked List Operations
    Optimal techniques for common linked list operations using pointer manipulation, …
  • LRU and LFU Cache
    Cache replacement policies determine which items to evict when the cache is …
  • Merge Sort
    Merge sort is a stable, comparison-based sorting algorithm that uses the …
  • Quadtree
    A Quadtree is a tree data structure where each internal node has exactly four …
  • Quick Sort
    Quick sort is an efficient, in-place, comparison-based sorting algorithm that …
  • String Similarity Algorithms
    Algorithms for measuring similarity between strings, used in spell checking, DNA …
  • Terrain & Heightmap Generation
    Procedural terrain generation creates realistic landscapes using mathematical …
  • Trie (Prefix Tree)
    A Trie (pronounced &quot;try&quot;) is a tree-like data structure used to store …
  • Wave Function Collapse
    Wave Function Collapse (WFC) is a procedural generation algorithm that creates …