Heap (binary heap)

1class MinHeap:2    def __init__(self):3        self.data = []4
5    def push(self, value):6        # Append at the end, then bubble up to restore order7        self.data.append(value)8        i = len(self.data) - 19        while i > 0:10            parent = (i - 1) // 211            if self.data[parent] <= self.data[i]:12                break13            self.data[i], self.data[parent] = self.data[parent], self.data[i]14            i = parent15
16    def pop(self):17        # Move the last leaf to the root, then sift it down18        top = self.data[0]19        last = self.data.pop()20        if self.data:21            self.data[0] = last22            self._sift_down(0)23        return top24
25    def _sift_down(self, i):26        n = len(self.data)27        while True:28            smallest = i29            left, right = 2 * i + 1, 2 * i + 230            if left < n and self.data[left] < self.data[smallest]:31                smallest = left32            if right < n and self.data[right] < self.data[smallest]:33                smallest = right34            if smallest == i:35                return36            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37            i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42    heap.push(value)43
44print("Heap array:     ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])

1class MinHeap {2    constructor() {3        this.items = [];4    }5
6    push(value) {7        this.items.push(value);8        // Bubble the new value up while it is smaller than its parent9        let i = this.items.length - 1;10        while (i > 0) {11            const parent = Math.floor((i - 1) / 2);12            if (this.items[parent] <= this.items[i]) break;13            [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14            i = parent;15        }16    }17
18    pop() {19        const top = this.items[0];20        const last = this.items.pop();21        if (this.items.length > 0) {22            this.items[0] = last;23            this.sinkDown(0);24        }25        return top;26    }27
28    sinkDown(i) {29        const n = this.items.length;30        while (true) {31            let smallest = i;32            const left = 2 * i + 1;33            const right = 2 * i + 2;34            if (left < n && this.items[left] < this.items[smallest]) smallest = left;35            if (right < n && this.items[right] < this.items[smallest]) smallest = right;36            if (smallest === i) return;37            [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38            i = smallest;39        }40    }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));

1public class Main {2    static int[] heap = new int[32];3    static int size = 0;4
5    static void push(int value) {6        heap[size] = value;7        int i = size++;8        // Sift up while smaller than the parent9        while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10            swap(i, (i - 1) / 2);11            i = (i - 1) / 2;12        }13    }14
15    static int pop() {16        int min = heap[0];17        heap[0] = heap[--size];18        int i = 0;19        // Sift down: swap with the smaller child until in place20        while (true) {21            int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22            if (l < size && heap[l] < heap[smallest]) smallest = l;23            if (r < size && heap[r] < heap[smallest]) smallest = r;24            if (smallest == i) break;25            swap(i, smallest);26            i = smallest;27        }28        return min;29    }30
31    static void swap(int a, int b) {32        int tmp = heap[a];33        heap[a] = heap[b];34        heap[b] = tmp;35    }36
37    public static void main(String[] args) {38        int[] values = {9, 4, 7, 1, 8, 2};39        for (int v : values) push(v);40        System.out.print("Popped in order:");41        while (size > 0) System.out.print(" " + pop());42        System.out.println();43    }44}

1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6    std::vector<int> data;7
8    void push(int value) {9        data.push_back(value);10        // Sift up until the parent is no larger11        size_t i = data.size() - 1;12        while (i > 0) {13            size_t parent = (i - 1) / 2;14            if (data[parent] <= data[i]) break;15            std::swap(data[parent], data[i]);16            i = parent;17        }18    }19
20    int pop() {21        int top = data[0];22        data[0] = data.back();23        data.pop_back();24        // Sift down: swap with the smaller child25        size_t i = 0;26        while (true) {27            size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28            if (l < data.size() && data[l] < data[smallest]) smallest = l;29            if (r < data.size() && data[r] < data[smallest]) smallest = r;30            if (smallest == i) break;31            std::swap(data[i], data[smallest]);32            i = smallest;33        }34        return top;35    }36
37    int peek() const { return data[0]; }38    bool empty() const { return data.empty(); }39};40
41int main() {42    MinHeap heap;43    for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44    std::cout << "Min: " << heap.peek() << "\n";45    std::cout << "Popped in order: ";46    while (!heap.empty()) std::cout << heap.pop() << " ";47    std::cout << "\n";48    return 0;49}

1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9    // Sift up until the parent is no larger10    int i = heapSize++;11    heap[i] = value;12    while (i > 0) {13        int parent = (i - 1) / 2;14        if (heap[parent] <= heap[i]) break;15        int tmp = heap[parent];16        heap[parent] = heap[i];17        heap[i] = tmp;18        i = parent;19    }20}21
22int pop(void) {23    int top = heap[0];24    heap[0] = heap[--heapSize];25    // Sift down: swap with the smaller child26    int i = 0;27    while (1) {28        int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29        if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30        if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31        if (smallest == i) break;32        int tmp = heap[i];33        heap[i] = heap[smallest];34        heap[smallest] = tmp;35        i = smallest;36    }37    return top;38}39
40int main(void) {41    int values[] = {5, 3, 8, 1, 9, 2};42    for (int i = 0; i < 6; i++) push(values[i]);43    printf("Min: %d\n", heap[0]);44    printf("Popped in order: ");45    while (heapSize > 0) printf("%d ", pop());46    printf("\n");47    return 0;48}