Comprehensive Guide to Heaps: Definition, Operations, Sorting, and Production Applications

Heaps are a crucial data structure in production environments, frequently appearing in interview questions such as Top‑K and serving as the backbone of priority queues.

Common production problems include implementing priority queues, solving Top‑K queries, and quickly calculating TP99 metrics; all of these can be efficiently addressed using heaps.

Definition : A heap is a complete binary tree (also called a binary heap) where each node's value is greater than or equal to (max‑heap) or less than or equal to (min‑heap) its children. Because the tree is complete, it can be stored compactly in an array.

The array representation uses the relationship parent(i) = i/2 , left(i) = 2*i , and right(i) = 2*i + 1 , eliminating the need for explicit child pointers and saving space.

Basic operations :

1. Insertion – Insert the new element at the end of the array and then perform a bottom‑up heapify (sift‑up) to restore the heap property. The Java implementation is:

public class Heap {
    private int[] arr; // array storage
    private int capacity;
    private int n; // current size

    public Heap(int count) {
        capacity = count;
        arr = new int[capacity + 1];
        n = 0;
    }

    public void insert(int value) {
        if (n >= capacity) {
            return; // overflow
        }
        n++;
        arr[n] = value;
        int i = n;
        while (i / 2 > 0 && arr[i] > arr[i / 2]) {
            swap(arr, i, i / 2);
            i = i / 2;
        }
    }
}

The time complexity is O(log n) .

2. Deletion of the top element – Replace the root with the last element, shrink the size, and then perform a top‑down heapify (sift‑down) to maintain the heap property. The Java code is:

/**
 * Remove the heap top element
 */
public void removeTopElement() {
    if (n == 0) {
        return;
    }
    int count = n;
    arr[1] = arr[count];
    --count;
    heapify(1, count);
}

/**
 * Top‑down heapify for a max‑heap
 */
public void heapify(int index, int n) {
    while (true) {
        int maxValueIndex = index;
        if (2 * index <= n && arr[index] < arr[2 * index]) {
            maxValueIndex = 2 * index;
        }
        if (2 * index + 1 <= n && arr[maxValueIndex] < arr[2 * index + 1]) {
            maxValueIndex = 2 * index + 1;
        }
        if (maxValueIndex == index) {
            break;
        }
        swap(arr, index, maxValueIndex);
        index = maxValueIndex;
    }
}

/**
 * Swap two elements in the array
 */
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

This operation also runs in O(log n) time.

Heap sort builds a max‑heap from the input array, repeatedly swaps the root with the last unsorted element, reduces the heap size, and heapifies the new root. The core methods are:

/**
 * Build a max‑heap by heapifying all non‑leaf nodes
 */
public void buildHeap() {
    for (int i = n / 2; i > 0; i--) {
        heapify(i);
    }
}

/**
 * Heap sort implementation
 */
public void heapsort() {
    // build heap
    buildHeap();
    int i = n;
    while (true) {
        if (i <= 1) {
            break;
        }
        // move current max to the end
        swap(arr, 1, i);
        i--;
        // restore heap property for the reduced heap
        heapify(1, i);
    }
}

The overall time complexity is O(n log n) , comparable to quicksort, but heap sort does not benefit from cache locality and is not a stable sort.

Production applications :

Priority queues are implemented with max‑heaps (e.g., Java's PriorityQueue ).

Top‑K queries use a min‑heap of size K to keep the K largest elements, achieving O(n log K) time.

TP99 calculation can be performed with two heaps (a max‑heap for the lower 99% and a min‑heap for the top 1%) to maintain the percentile in streaming data.

Understanding heaps and their operations is essential for designing efficient algorithms and for grasping the underlying implementations of many high‑level data structures used in real‑world systems.