[Data Structure] Min-Max Heap

Last Updated on 2025-05-08 by Clay

Binary Heap

A binary heap is a common data structure ideal for retrieving the maximum or minimum value and is often used to solve top-k extraction problems.

Read more: [Data Structure] Min-Max Heap

A binary heap in defined as a complete binary tree: each node has at most two chidren, all levels are fully filled except possibly the last, which is filled from left to right.

For example:

There are two types of binary heaps: Max Heap and Min Heap. They are similar in structure but differ in their ordering rules.

In Max Heap, every node must be greater than or equal to its left and right children; in Min Heap, the opposite is true.

---

Operations of Max Heap (We take Max Heap for example)

Max Heap support two primary operations:

• insert()
• extractMax()

insert()

To insert an element into Max Heap, we need to do the following steps:

• Insert the element at the end of the heap.
• Compare it with its parent, if it is larger, swap them. Repeat this process util it is no longer larger than its parent or it becomes the root.

This operation is known as swim (or heapify-up).

extractMax()

To extract the maximum element, retrieve the root node. Then reheapify to maintain the Max Heap property.

We can do the following operations:

1. Swap the root with the last node, then remove the last node (which was the maximum).
2. Starting from the root, compare it with its children. If a child is larger, swap them. If both are larger, swap with the larger child.
3. Repeat the process until the current node is greater than or equal to both of its children.

(Note: The website have a good demo animate: https://www.shubo.io/binary-heap/)

---

Max Heap Implementation

A Max Heap can be efficiently implemented using a single array.

• The parent index of a node at index i is (i - 1) // 2.
• The left child index of a node at index i is 2 * i + 1, and the right child index is 2 * i + 2.

The following is an implementation of Max Heap by C++:

#include<iostream>
#include<vector>


class maxHeap {
private:
    std::vector<int> heap;
    void swim(int currId) {
        while (currId > 0) {
            int parentId = (currId - 1) / 2;
            if (heap[currId] > heap[parentId]) {
                std::swap(heap[currId], heap[parentId]);
                currId = parentId;
            }
            else {
                break;
            }
        }
    }

    void sink() {
        int currId = 0;
        int heapSize = heap.size();

        while (true) {
            int leftNodeId = currId * 2 + 1;
            int rightNodeId = currId * 2 + 2;
            int largestId = currId;

            // Check the left child
            if (heapSize > leftNodeId && heap[leftNodeId] > heap[largestId]) {
                largestId = leftNodeId;
            }

            // Check the right child
            if (heapSize > rightNodeId && heap[rightNodeId] > heap[largestId]) {
                largestId = rightNodeId;
            }

            // If parent is larger than two children, stop sink
            if (largestId == currId) {
                break;
            }

            std::swap(heap[currId], heap[largestId]);
            currId = largestId;
        }
    }
public:
    void insert(int val) {
        heap.emplace_back(val);
        swim(heap.size() - 1);
    }

    int extractMax() {
        std::swap(heap.front(), heap.back());
        int currMax = heap.back();
        heap.pop_back();
        sink();

        return currMax; 
    }

    void clear() {
        heap.clear();
    }

    int size() {
        return heap.size();
    }
};


int main() {
    maxHeap h;
    h.insert(5);
    h.insert(2);
    h.insert(8);
    h.insert(3);
    h.insert(10);

    std::cout << "Extracted: ";
    while (h.size() != 0) {
        try {
            std::cout << h.extractMax() << " ";
        } catch (const std::exception& e) {
            std::cout << "\nHeap is empty.\n";
            break;
        }
    }
}

Output:

Extracted: 10 8 5 3 2

---

References

• Introduction to Max-Heap – Data Structure and Algorithm Tutorials
• Wikipedia - Min-max heap

---