Min-heap: insert and sift up

A heap is a complete binary tree stored in an array, where every parent is smaller than its children.

Time O(log n) per insertSpace O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Add the new value at the end of the array, which is the next free leaf. While it is smaller than its parent, swap them. It climbs at most the height of the tree.

Code

C++PythonC#

void push(vector<int>& heap, int value) {
    heap.push_back(value);
    int i = (int)heap.size() - 1;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[parent] <= heap[i]) break;
        swap(heap[parent], heap[i]);
        i = parent;
    }
}

def push(heap: list[int], value: int) -> None:
    heap.append(value)
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] <= heap[i]: break
        heap[parent], heap[i] = heap[i], heap[parent]
        i = parent
    # heap order restored
# (heapq.heappush(heap, value) does exactly this)

public static void Push(List<int> heap, int value) {
    heap.Add(value);
    int i = heap.Count - 1;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[parent] <= heap[i]) break;
        (heap[parent], heap[i]) = (heap[i], heap[parent]);
        i = parent;
    }
}

Tips

Index arithmetic replaces pointers: parent of i is (i - 1) / 2, children are 2i + 1 and 2i + 2.
The smallest value is always at index 0. The rest is only partly ordered.

In the .NET library

PriorityQueue<TElement, TPriority> (since .NET 6) is a min-heap. Enqueue(item, priority) does this sift-up for you.