Heaps

Priority Queues

A priority queue is a data structure that stores elements with associated priorities. Elements with higher priorities are dequeued before elements with lower priorities. Priority queues are commonly used in algorithms that require elements to be processed in a specific order, such as Dijkstra’s algorithm for finding the shortest path in a graph.

Operations

A priority queue supports the following operations:

• Insert: Add an element to the priority queue with an associated priority.
• Delete Min/Max: Remove and return the element with the highest priority (min priority in a min-heap, max priority in a max-heap).
• Peek Min/Max: Return the element with the highest priority without removing it.

Therefore, in a priority queue, we care about retrieving the element with the highest priority (min or max) first as fast as possible. Additionally, we need to be able to insert elements with priorities as efficiently as possible.

A heap offers an efficient implementation of a priority queue, as it allows for fast insertion and retrieval of the element with the highest priority.

Heaps

A heap is a binary tree data structure that satisfies the heap property.

Heap Property

A heap satisfies the heap property, which depends on the type of heap:

• Min-Heap: In a min-heap, for every node i other than the root, the value of i is greater than or equal to the value of its parent.
• Max-Heap: In a max-heap, for every node i other than the root, the value of i is less than or equal to the value of its parent.

Binary Heap

A binary heap is a complete binary tree that satisfies the heap property. In a complete binary tree, all levels are filled except possibly for the last level, which is filled from left to right.

Accessing Elements

In order to access elements in a binary heap, we can use the following formulas:

• Parent: The parent of a node at index $i$ is at index $\lfloor (i-1)/2\rfloor$ for $i>0$ (the root has no parent).
• Left Child: The left child of a node at index $i$ is at index $2i+1$.
• Right Child: The right child of a node at index $i$ is at index $2i+2$.

Pseudocode

parent(index):
    return (index - 1) / 2

left_child(index):
    return 2 * index + 1

right_child(index):
    return 2 * index + 2

Java

static int parent(int index) {
    return (index - 1) / 2;
}

static int leftChild(int index) {
    return 2 * index + 1;
}

static int rightChild(int index) {
    return 2 * index + 2;
}

Operations

A binary heap supports the following operations:

• Insert: Add an element to the heap.
• Delete Min/Max: Remove and return the element with the highest priority (min in a min-heap, max in a max-heap).
• Heapify: Ensure that the heap property is maintained after an insertion or deletion operation.

Heapify

Heapify is the core operation that maintains the heap property after an insertion or deletion operation. It involves “bubbling up” or “bubbling down” a node to its correct position in the heap.

Note

The examples below implement a min-heap. Swap upward only when the parent is greater than the child. During downward repair, choose the smaller child and stop when the parent is already no greater than that child. Reverse the comparisons for a max-heap.

Insertion — Heapify Up

When inserting an element into a heap, we add the element to the end of the array and then “bubble up” the element to its correct position. We compare the element with its parent and swap them if the heap property is violated. We continue this process until the element is in the correct position.

Pseudocode

insert(heap, element):
    heap.add(element)
    index = heap.size() - 1
    heapify_up(heap, index)

heapify_up(heap, index):
    while index > 0 and heap[parent(index)] > heap[index]:
        swap(heap, parent(index), index)
        index = parent(index)

Java

static <T extends Comparable<? super T>> void insert(java.util.List<T> heap, T element) {
    heap.add(element);
    int index = heap.size() - 1;
    heapifyUp(heap, index);
}

static <T extends Comparable<? super T>> void heapifyUp(java.util.List<T> heap, int index) {
    while (index > 0 && heap.get(parent(index)).compareTo(heap.get(index)) > 0) {
        java.util.Collections.swap(heap, parent(index), index);
        index = parent(index);
    }
}

Delete — Heapify Down

When deleting the root element of a heap (min or max), we remove the element and replace it with the last element in the heap. We then “bubble down” the element to its correct position by comparing it with its children and swapping it with the smaller (min-heap) or larger (max-heap) child. We continue this process until the element is in the correct position.

Pseudocode

delete(heap):
    if heap is empty: report an error
    swap(heap, 0, heap.size() - 1)
    heap.remove(heap.size() - 1)
    heapify_down(heap, 0)

heapify_down(heap, index):
    while left_child(index) < heap.size():
        int child = left_child(index)
        if child + 1 < heap.size() and heap[child + 1] < heap[child]:
            child++
        if heap[index] <= heap[child]:
            break
        swap(heap, index, child)
        index = child

Java

static <T extends Comparable<? super T>> T delete(java.util.List<T> heap) {
    if (heap.isEmpty()) throw new java.util.NoSuchElementException();
    T result = heap.get(0);
    java.util.Collections.swap(heap, 0, heap.size() - 1);
    heap.remove(heap.size() - 1);
    heapifyDown(heap, 0);
    return result;
}

static <T extends Comparable<? super T>> void heapifyDown(java.util.List<T> heap, int index) {
    while (leftChild(index) < heap.size()) {
        int child = leftChild(index);
        if (child + 1 < heap.size() && heap.get(child + 1).compareTo(heap.get(child)) < 0) {
            child++;
        }
        if (heap.get(index).compareTo(heap.get(child)) <= 0) {
            break;
        }
        java.util.Collections.swap(heap, index, child);
        index = child;
    }
}

Complexity

For an array-backed binary heap with $N$ elements, peek is $O(1)$ and insertion/root removal are $O(\log N)$ worst case, apart from occasional dynamic-array resizing. Bottom-up construction of a heap is $O(N)$.

Source

The existing course note was retained and normalized during the merge.

Related: Topic index.