Eventually Bitwise

Heaps

Overview

A Heap is a specialized tree-based data structure that satisfies the heap property. It is most commonly implemented as a binary heap, which is a complete binary tree. Heaps are primarily used to implement priority queues and the heapsort algorithm.

Core Concepts

  • Heap Property:
    • Max-Heap: The value of the root node must be the maximum among all nodes in the heap. This must be recursively true for all subtrees.
    • Min-Heap: The value of the root node must be the minimum among all nodes in the heap.
  • Complete Binary Tree: A heap is always a complete binary tree, meaning all levels are completely filled except possibly the last level, which is filled from left to right.
  • Array Representation: Because it is a complete tree, a heap can be stored efficiently in an array:
    • Root is at index 0.
    • Left child of index i is at 2i + 1.
    • Right child of index i is at 2i + 2.
    • Parent of index i is at floor((i - 1) / 2).
  • Key Operations:
    • Insert: Add to the end and “bubble up” (percolate up) to maintain the heap property. $O(\log n)$.
    • Extract Min/Max: Remove the root, move the last element to the root, and “bubble down” (percolate down). $O(\log n)$.
    • Peek: Return the root value. $O(1)$.

Code Examples

// Conceptual Min-Heap Extract-Min logic
function bubbleDown(heap: number[], index: number) {
    let smallest = index;
    const left = 2 * index + 1;
    const right = 2 * index + 2;

    if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
    if (right < heap.length && heap[right] < heap[smallest]) smallest = right;

    if (smallest !== index) {
        [heap[index], heap[smallest]] = [heap[smallest], heap[index]];
        bubbleDown(heap, smallest);
    }
}

Use Cases

  • Priority Queues: Scheduling tasks in an OS or managing packets in a network.
  • Dijkstra’s Algorithm: Using a Min-Heap to efficiently find the next closest node.
  • Heapsort: A sorting algorithm with $O(n \log n)$ time complexity.

Gotchas

  • Not a Sorted List: A heap is not fully sorted; it only guarantees the relationship between parent and child. To get a sorted list, you must extract elements one by one.
  • Array Indexing: Off-by-one errors are common when implementing the parent/child index formulas.

Related Notes

, ,