A heap gives you the smallest (or largest) element of a changing collection in O(1), with O(log n) insert and remove. Almost every “top k”, “k-way merge” and “running statistic” problem is a heap of the right type and the right size.

A heap is just an array with a parent/child index rule — no pointers

min-heap as a tree              the same heap as an array
         5                      index:  0   1   2   3   4
       /   \                   value:  5   8  10  15  20
      8     10
     / \                       parent(i) = (i - 1) / 2
   15   20                     children(i) = 2i + 1, 2i + 2

Operation	Time	How
`peek()` — min or max	O(1)	it is `a[0]`
`push(x)`	O(log n)	append, then sift up while smaller than the parent
`pop()`	O(log n)	move the last element to the root, then sift down
`heapify(array)`	O(n)	sift down from the last internal node to the root — cheaper than `n` pushes
search for an arbitrary key	O(n)	a heap is not sorted; only the root is special

Priority queues in each language

Language	Type	Default	Max-heap
Python	`heapq` functions on a list	min-heap	push `-x`, negate on pop (or `(-key, item)` tuples)
C++	`std::priority_queue<T>`	max-heap	default; min-heap needs `priority_queue<T, vector<T>, greater<T>>`
Java	`java.util.PriorityQueue<T>`	min-heap	`new PriorityQueue<>(Collections.reverseOrder())` or a comparator
JavaScript	none built in	—	write a small `Heap` class with a comparator once (below) and reuse it

Python

import heapq

nums = [5, 15, 10, 20, 8]

mn = []                                  # heapq is a min-heap only
for x in nums:
    heapq.heappush(mn, x)
print("min-heap:", *(heapq.heappop(mn) for _ in range(len(nums))))

mx = [-x for x in nums]                  # max-heap: store the negated keys
heapq.heapify(mx)                        # O(n) build
print("max-heap:", *(-heapq.heappop(mx) for _ in range(len(nums))))

C++

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    vector<int> nums = {5, 15, 10, 20, 8};

    priority_queue<int, vector<int>, greater<int>> mn;     // min-heap needs greater<>
    for (int x : nums) mn.push(x);
    cout << "min-heap:";
    while (!mn.empty()) { cout << " " << mn.top(); mn.pop(); }
    cout << "\n";

    priority_queue<int> mx(nums.begin(), nums.end());       // default is a max-heap; O(n) build
    cout << "max-heap:";
    while (!mx.empty()) { cout << " " << mx.top(); mx.pop(); }
    cout << "\n";
}

Java

import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        int[] nums = {5, 15, 10, 20, 8};

        PriorityQueue<Integer> mn = new PriorityQueue<>();        // min-heap by default
        for (int x : nums) mn.add(x);
        StringBuilder sb = new StringBuilder("min-heap:");
        while (!mn.isEmpty()) sb.append(' ').append(mn.poll());
        System.out.println(sb);

        PriorityQueue<Integer> mx = new PriorityQueue<>(Collections.reverseOrder());   // or (a, b) -> b - a
        for (int x : nums) mx.add(x);
        sb = new StringBuilder("max-heap:");
        while (!mx.isEmpty()) sb.append(' ').append(mx.poll());
        System.out.println(sb);
    }
}

JavaScript

class Heap {
    constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }   // cmp(x, y) < 0 → x comes out first
    size() { return this.a.length; }
    peek() { return this.a[0]; }
    push(x) {
        const a = this.a;
        a.push(x);
        let i = a.length - 1;
        while (i > 0) {                                    // sift up
            const p = (i - 1) >> 1;
            if (this.cmp(a[i], a[p]) >= 0) break;
            [a[i], a[p]] = [a[p], a[i]];
            i = p;
        }
    }
    pop() {
        const a = this.a, top = a[0], last = a.pop();
        if (a.length) {
            a[0] = last;
            let i = 0;
            for (;;) {                                     // sift down
                let m = i;
                const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
                if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]];
                i = m;
            }
        }
        return top;
    }
}

const nums = [5, 15, 10, 20, 8];

const mn = new Heap((a, b) => a - b);                      // min-heap
for (const x of nums) mn.push(x);
const small = [];
while (mn.size()) small.push(mn.pop());
console.log("min-heap:", small.join(" "));

const mx = new Heap((a, b) => b - a);                      // max-heap: flip the comparator
for (const x of nums) mx.push(x);
const big = [];
while (mx.size()) big.push(mx.pop());
console.log("max-heap:", big.join(" "));

Output

min-heap: 5 8 10 15 20
max-heap: 20 15 10 8 5

Sort a k-sorted (nearly sorted) array

Every element is at most k positions away from its sorted position. A full sort is O(n log n); exploiting k gives O(n log k).

Python

import heapq

def sort_k(arr, k):
    h, res = [], []
    for x in arr:
        heapq.heappush(h, x)
        if len(h) > k:                   # k+1 elements inside → the minimum is final
            res.append(heapq.heappop(h))
    while h:                             # drain the last k elements in order
        res.append(heapq.heappop(h))
    return res

print(*sort_k([9, 8, 7, 18, 19, 17], 2))
print(*sort_k([10, 9, 8, 7, 4, 70, 60, 50], 4))

C++

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> sortK(const vector<int>& arr, int k) {
    priority_queue<int, vector<int>, greater<int>> h;     // min-heap
    vector<int> res;
    for (int x : arr) {
        h.push(x);
        if ((int)h.size() > k) { res.push_back(h.top()); h.pop(); }   // k+1 inside → the minimum is final
    }
    while (!h.empty()) { res.push_back(h.top()); h.pop(); }           // drain the last k elements
    return res;
}

void print(const vector<int>& v) {
    for (int i = 0; i < (int)v.size(); i++) cout << (i ? " " : "") << v[i];
    cout << "\n";
}

int main() {
    print(sortK({9, 8, 7, 18, 19, 17}, 2));
    print(sortK({10, 9, 8, 7, 4, 70, 60, 50}, 4));
}

Java

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    static List<Integer> sortK(int[] arr, int k) {
        PriorityQueue<Integer> h = new PriorityQueue<>();     // min-heap
        List<Integer> res = new ArrayList<>();
        for (int x : arr) {
            h.add(x);
            if (h.size() > k) res.add(h.poll());              // k+1 inside → the minimum is final
        }
        while (!h.isEmpty()) res.add(h.poll());               // drain the last k elements
        return res;
    }

    static String join(List<Integer> xs) {
        StringBuilder sb = new StringBuilder();
        for (int x : xs) sb.append(x).append(' ');
        return sb.toString().trim();
    }

    public static void main(String[] args) {
        System.out.println(join(sortK(new int[]{9, 8, 7, 18, 19, 17}, 2)));
        System.out.println(join(sortK(new int[]{10, 9, 8, 7, 4, 70, 60, 50}, 4)));
    }
}

JavaScript

class Heap {
    constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
    size() { return this.a.length; }
    peek() { return this.a[0]; }
    push(x) {
        const a = this.a;
        a.push(x);
        let i = a.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(a[i], a[p]) >= 0) break;
            [a[i], a[p]] = [a[p], a[i]];
            i = p;
        }
    }
    pop() {
        const a = this.a, top = a[0], last = a.pop();
        if (a.length) {
            a[0] = last;
            let i = 0;
            for (;;) {
                let m = i;
                const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
                if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]];
                i = m;
            }
        }
        return top;
    }
}

function sortK(arr, k) {
    const h = new Heap(), res = [];                        // min-heap
    for (const x of arr) {
        h.push(x);
        if (h.size() > k) res.push(h.pop());               // k+1 inside → the minimum is final
    }
    while (h.size()) res.push(h.pop());                    // drain the last k elements
    return res;
}

console.log(sortK([9, 8, 7, 18, 19, 17], 2).join(" "));
console.log(sortK([10, 9, 8, 7, 4, 70, 60, 50], 4).join(" "));

Output

7 8 9 17 18 19
4 7 8 9 10 50 60 70

Time O(n log k) · Space O(k)

Purchase maximum items with a budget

Python

def max_items_sorted(cost, budget):
    count = 0
    for c in sorted(cost):            # cheapest first
        if c > budget:
            break
        budget -= c
        count += 1
    return count

print(max_items_sorted([1, 12, 5, 111, 200], 10))
print(max_items_sorted([20, 10, 5, 30, 100], 35))

Output

2
3

Time O(n log n) · Space O(1) extra (in-place sort)

But you usually stop long before the end — the budget runs out after r items. A min-heap built in O(n) and popped r times costs O(n + r log n), which beats a sort when r is small (a tight budget, a huge catalogue).

Python

import heapq

def max_items(cost, budget):
    h = list(cost)
    heapq.heapify(h)                     # O(n) — cheaper than sorting everything
    count = 0
    while h and h[0] <= budget:          # cheapest remaining item is affordable
        budget -= heapq.heappop(h)
        count += 1
    return count

print(max_items([1, 12, 5, 111, 200], 10))
print(max_items([20, 10, 5, 30, 100], 35))

C++

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int maxItems(const vector<int>& cost, int budget) {
    priority_queue<int, vector<int>, greater<int>> h(cost.begin(), cost.end());   // O(n) heapify
    int count = 0;
    while (!h.empty() && h.top() <= budget) {    // cheapest remaining item is affordable
        budget -= h.top();
        h.pop();
        count++;
    }
    return count;
}

int main() {
    cout << maxItems({1, 12, 5, 111, 200}, 10) << "\n";
    cout << maxItems({20, 10, 5, 30, 100}, 35) << "\n";
}

Java

import java.util.PriorityQueue;

public class Main {
    static int maxItems(int[] cost, int budget) {
        PriorityQueue<Integer> h = new PriorityQueue<>();
        for (int c : cost) h.add(c);                 // n pushes: O(n log n); a Collection ctor heapifies in O(n)
        int count = 0;
        while (!h.isEmpty() && h.peek() <= budget) { // cheapest remaining item is affordable
            budget -= h.poll();
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(maxItems(new int[]{1, 12, 5, 111, 200}, 10));
        System.out.println(maxItems(new int[]{20, 10, 5, 30, 100}, 35));
    }
}

JavaScript

class Heap {
    constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
    size() { return this.a.length; }
    peek() { return this.a[0]; }
    push(x) {
        const a = this.a;
        a.push(x);
        let i = a.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(a[i], a[p]) >= 0) break;
            [a[i], a[p]] = [a[p], a[i]];
            i = p;
        }
    }
    pop() {
        const a = this.a, top = a[0], last = a.pop();
        if (a.length) {
            a[0] = last;
            let i = 0;
            for (;;) {
                let m = i;
                const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
                if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]];
                i = m;
            }
        }
        return top;
    }
}

function maxItems(cost, budget) {
    const h = new Heap();                            // min-heap
    for (const c of cost) h.push(c);
    let count = 0;
    while (h.size() && h.peek() <= budget) {         // cheapest remaining item is affordable
        budget -= h.pop();
        count++;
    }
    return count;
}

console.log(maxItems([1, 12, 5, 111, 200], 10));
console.log(maxItems([20, 10, 5, 30, 100], 35));

Output

2
3

Time O(n + r log n) · Space O(n)

K largest elements

Build
Put the first k elements into a min-heap.
Scan the rest
If x <= heap.top() ignore it; otherwise pop the top and push x.
Collect
The heap now holds exactly the k largest. Pop them for ascending order.

Python

import heapq

def k_largest(arr, k):
    h = arr[:k]
    heapq.heapify(h)                      # min-heap of the k largest seen so far
    for x in arr[k:]:
        if x > h[0]:                      # bigger than the current threshold
            heapq.heapreplace(h, x)       # pop the root and push x in one sift
    return sorted(h)

print(*k_largest([5, 15, 10, 20, 8], 2))
print(*k_largest([3, 9, 1, 7, 5, 8], 3))

C++

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> kLargest(const vector<int>& arr, int k) {
    priority_queue<int, vector<int>, greater<int>> h;     // min-heap of the k largest seen so far
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        if (i < k) h.push(arr[i]);
        else if (arr[i] > h.top()) { h.pop(); h.push(arr[i]); }   // beats the threshold
    }
    vector<int> res;
    while (!h.empty()) { res.push_back(h.top()); h.pop(); }       // popped in ascending order
    return res;
}

void print(const vector<int>& v) {
    for (int i = 0; i < (int)v.size(); i++) cout << (i ? " " : "") << v[i];
    cout << "\n";
}

int main() {
    print(kLargest({5, 15, 10, 20, 8}, 2));
    print(kLargest({3, 9, 1, 7, 5, 8}, 3));
}

Java

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    static List<Integer> kLargest(int[] arr, int k) {
        PriorityQueue<Integer> h = new PriorityQueue<>();     // min-heap of the k largest seen so far
        for (int i = 0; i < arr.length; i++) {
            if (i < k) h.add(arr[i]);
            else if (arr[i] > h.peek()) { h.poll(); h.add(arr[i]); }   // beats the threshold
        }
        List<Integer> res = new ArrayList<>();
        while (!h.isEmpty()) res.add(h.poll());               // polled in ascending order
        return res;
    }

    static String join(List<Integer> xs) {
        StringBuilder sb = new StringBuilder();
        for (int x : xs) sb.append(x).append(' ');
        return sb.toString().trim();
    }

    public static void main(String[] args) {
        System.out.println(join(kLargest(new int[]{5, 15, 10, 20, 8}, 2)));
        System.out.println(join(kLargest(new int[]{3, 9, 1, 7, 5, 8}, 3)));
    }
}

JavaScript

class Heap {
    constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
    size() { return this.a.length; }
    peek() { return this.a[0]; }
    push(x) {
        const a = this.a;
        a.push(x);
        let i = a.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(a[i], a[p]) >= 0) break;
            [a[i], a[p]] = [a[p], a[i]];
            i = p;
        }
    }
    pop() {
        const a = this.a, top = a[0], last = a.pop();
        if (a.length) {
            a[0] = last;
            let i = 0;
            for (;;) {
                let m = i;
                const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
                if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]];
                i = m;
            }
        }
        return top;
    }
}

function kLargest(arr, k) {
    const h = new Heap();                                  // min-heap of the k largest seen so far
    for (let i = 0; i < arr.length; i++) {
        if (i < k) h.push(arr[i]);
        else if (arr[i] > h.peek()) { h.pop(); h.push(arr[i]); }   // beats the threshold
    }
    const res = [];
    while (h.size()) res.push(h.pop());                    // popped in ascending order
    return res;
}

console.log(kLargest([5, 15, 10, 20, 8], 2).join(" "));
console.log(kLargest([3, 9, 1, 7, 5, 8], 3).join(" "));

Output

15 20
7 8 9

Time O(n log k) · Space O(k)

The alternative is a max-heap of all n elements, popped k times. It is simpler and gives the results largest-first, but it needs O(n) memory and cannot process a stream:

Python

import heapq

def k_largest_maxheap(arr, k):
    h = [-x for x in arr]                   # max-heap via negation
    heapq.heapify(h)                        # O(n)
    return [-heapq.heappop(h) for _ in range(k)]   # k pops, O(k log n)

print(*k_largest_maxheap([5, 15, 10, 20, 8], 2))

Output

20 15

Approach	Time	Space	Works on a stream?
sort, take the last `k`	O(n log n)	O(1)	no
max-heap of all, pop `k`	O(n + k log n)	O(n)	no
min-heap of size `k`	O(n log k)	O(k)	yes — the heap is the running answer
quickselect	O(n) average	O(1)	no (unordered result)

K closest elements to x

Pick the k elements with the smallest |arr[i] - x|. The naive approach finds the closest element, removes it and repeats k times:

Python

def k_closest_naive(arr, x, k):
    arr = list(arr)
    res = []
    for _ in range(k):                                     # k passes …
        mi = 0
        for j in range(1, len(arr)):                       # … each scanning the whole array
            if abs(arr[j] - x) < abs(arr[mi] - x):
                mi = j
        res.append(arr.pop(mi))
    return sorted(res)

print(*k_closest_naive([10, 15, 7, 3, 4], 8, 2))

Output

7 10

Time O(n · k) · Space O(k)

Python

import heapq

def k_closest(arr, x, k):
    h = []                                        # max-heap on distance: push (-dist, -value)
    for v in arr:
        heapq.heappush(h, (-abs(v - x), -v))
        if len(h) > k:
            heapq.heappop(h)                      # drop the farthest (on ties: the larger value)
    return sorted(-v for _, v in h)

print(*k_closest([10, 15, 7, 3, 4], 8, 2))
print(*k_closest([5, 15, 10, 20, 8], 12, 3))

C++

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> kClosest(const vector<int>& arr, int x, int k) {
    priority_queue<pair<int, int>> h;             // max-heap on (distance, value)
    for (int v : arr) {
        h.push({abs(v - x), v});
        if ((int)h.size() > k) h.pop();           // drop the farthest (on ties: the larger value)
    }
    vector<int> res;
    while (!h.empty()) { res.push_back(h.top().second); h.pop(); }
    sort(res.begin(), res.end());
    return res;
}

void print(const vector<int>& v) {
    for (int i = 0; i < (int)v.size(); i++) cout << (i ? " " : "") << v[i];
    cout << "\n";
}

int main() {
    print(kClosest({10, 15, 7, 3, 4}, 8, 2));
    print(kClosest({5, 15, 10, 20, 8}, 12, 3));
}

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    static List<Integer> kClosest(int[] arr, int x, int k) {
        // max-heap on distance, then on value: int[]{distance, value}
        PriorityQueue<int[]> h = new PriorityQueue<>(
            (a, b) -> a[0] != b[0] ? Integer.compare(b[0], a[0]) : Integer.compare(b[1], a[1]));
        for (int v : arr) {
            h.add(new int[]{Math.abs(v - x), v});
            if (h.size() > k) h.poll();                   // drop the farthest (on ties: the larger value)
        }
        List<Integer> res = new ArrayList<>();
        while (!h.isEmpty()) res.add(h.poll()[1]);
        Collections.sort(res);
        return res;
    }

    static String join(List<Integer> xs) {
        StringBuilder sb = new StringBuilder();
        for (int v : xs) sb.append(v).append(' ');
        return sb.toString().trim();
    }

    public static void main(String[] args) {
        System.out.println(join(kClosest(new int[]{10, 15, 7, 3, 4}, 8, 2)));
        System.out.println(join(kClosest(new int[]{5, 15, 10, 20, 8}, 12, 3)));
    }
}

JavaScript

class Heap {
    constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
    size() { return this.a.length; }
    peek() { return this.a[0]; }
    push(x) {
        const a = this.a;
        a.push(x);
        let i = a.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(a[i], a[p]) >= 0) break;
            [a[i], a[p]] = [a[p], a[i]];
            i = p;
        }
    }
    pop() {
        const a = this.a, top = a[0], last = a.pop();
        if (a.length) {
            a[0] = last;
            let i = 0;
            for (;;) {
                let m = i;
                const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
                if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]];
                i = m;
            }
        }
        return top;
    }
}

function kClosest(arr, x, k) {
    // max-heap on distance, then on value: [distance, value]
    const h = new Heap((a, b) => a[0] !== b[0] ? b[0] - a[0] : b[1] - a[1]);
    for (const v of arr) {
        h.push([Math.abs(v - x), v]);
        if (h.size() > k) h.pop();                         // drop the farthest (on ties: the larger value)
    }
    const res = [];
    while (h.size()) res.push(h.pop()[1]);
    return res.sort((a, b) => a - b);
}

console.log(kClosest([10, 15, 7, 3, 4], 8, 2).join(" "));
console.log(kClosest([5, 15, 10, 20, 8], 12, 3).join(" "));

Output

7 10
8 10 15

Time O(n log k) · Space O(k)

Merge k sorted arrays

N is the total number of elements, k the number of arrays. Two obvious approaches ignore the fact that the inputs are already sorted:

Python

# 1. concatenate everything and sort: O(N log N) — ignores the existing order
def merge_k_sort(arrays):
    res = []
    for a in arrays:
        res.extend(a)
    return sorted(res)

# 2. merge the arrays one by one into the result: O(N · k) — the result is re-merged k times
def merge_two(a, b):
    res, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    return res + a[i:] + b[j:]

def merge_k_pairwise(arrays):
    res = list(arrays[0])
    for a in arrays[1:]:
        res = merge_two(res, a)
    return res

arrays = [[10, 20, 30], [5, 15], [1, 9, 11, 18]]
print(*merge_k_sort(arrays))
print(*merge_k_pairwise(arrays))

Output

1 5 9 10 11 15 18 20 30
1 5 9 10 11 15 18 20 30

The heap never holds more than one element per array

heap of heads          output so far
{10, 5, 1}       pop 1  → push 9       1
{10, 5, 9}       pop 5  → push 15      1 5
{10, 15, 9}      pop 9  → push 11      1 5 9
{10, 15, 11}     pop 10 → push 20      1 5 9 10
{20, 15, 11}     pop 11 → push 18      1 5 9 10 11
...

Python

import heapq

def merge_k(arrays):
    h = [(a[0], i, 0) for i, a in enumerate(arrays) if a]   # (value, which array, index in it)
    heapq.heapify(h)
    res = []
    while h:
        val, ai, j = heapq.heappop(h)
        res.append(val)
        if j + 1 < len(arrays[ai]):                          # the same array has more
            heapq.heappush(h, (arrays[ai][j + 1], ai, j + 1))
    return res

print(*merge_k([[10, 20, 30], [5, 15], [1, 9, 11, 18]]))

C++

#include <array>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> mergeK(const vector<vector<int>>& arrays) {
    using Item = array<int, 3>;                              // {value, which array, index in it}
    priority_queue<Item, vector<Item>, greater<Item>> h;     // min-heap, compares lexicographically
    int k = arrays.size();
    for (int i = 0; i < k; i++)
        if (!arrays[i].empty()) h.push({arrays[i][0], i, 0});
    vector<int> res;
    while (!h.empty()) {
        Item it = h.top(); h.pop();
        int val = it[0], ai = it[1], j = it[2];
        res.push_back(val);
        if (j + 1 < (int)arrays[ai].size())                  // the same array has more
            h.push({arrays[ai][j + 1], ai, j + 1});
    }
    return res;
}

int main() {
    vector<int> res = mergeK({{10, 20, 30}, {5, 15}, {1, 9, 11, 18}});
    for (int i = 0; i < (int)res.size(); i++) cout << (i ? " " : "") << res[i];
    cout << "\n";
}

Java

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    static List<Integer> mergeK(int[][] arrays) {
        // int[]{value, which array, index in it}, ordered by value
        PriorityQueue<int[]> h = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 0; i < arrays.length; i++)
            if (arrays[i].length > 0) h.add(new int[]{arrays[i][0], i, 0});
        List<Integer> res = new ArrayList<>();
        while (!h.isEmpty()) {
            int[] it = h.poll();
            int val = it[0], ai = it[1], j = it[2];
            res.add(val);
            if (j + 1 < arrays[ai].length)                   // the same array has more
                h.add(new int[]{arrays[ai][j + 1], ai, j + 1});
        }
        return res;
    }

    public static void main(String[] args) {
        List<Integer> res = mergeK(new int[][]{{10, 20, 30}, {5, 15}, {1, 9, 11, 18}});
        StringBuilder sb = new StringBuilder();
        for (int v : res) sb.append(v).append(' ');
        System.out.println(sb.toString().trim());
    }
}

JavaScript

class Heap {
    constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
    size() { return this.a.length; }
    peek() { return this.a[0]; }
    push(x) {
        const a = this.a;
        a.push(x);
        let i = a.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(a[i], a[p]) >= 0) break;
            [a[i], a[p]] = [a[p], a[i]];
            i = p;
        }
    }
    pop() {
        const a = this.a, top = a[0], last = a.pop();
        if (a.length) {
            a[0] = last;
            let i = 0;
            for (;;) {
                let m = i;
                const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
                if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]];
                i = m;
            }
        }
        return top;
    }
}

function mergeK(arrays) {
    const h = new Heap((a, b) => a[0] - b[0]);               // [value, which array, index in it]
    arrays.forEach((a, i) => { if (a.length) h.push([a[0], i, 0]); });
    const res = [];
    while (h.size()) {
        const [val, ai, j] = h.pop();
        res.push(val);
        if (j + 1 < arrays[ai].length)                       // the same array has more
            h.push([arrays[ai][j + 1], ai, j + 1]);
    }
    return res;
}

console.log(mergeK([[10, 20, 30], [5, 15], [1, 9, 11, 18]]).join(" "));

Output

1 5 9 10 11 15 18 20 30

Time O(N log k) · Space O(k) for the heap, plus the output

Approach	Time	Why
concatenate + sort	O(N log N)	throws away the input order
merge one array at a time	O(N · k)	the growing result is re-merged `k - 1` times
min-heap of `k` heads	O(N log k)	every element passes once through a heap of size `k`
divide and conquer (merge pairs)	O(N log k)	same bound, no heap, more copying

Median of a stream

After each new number, report the median of everything seen so far. A median needs the middle of the data, not its minimum — the trick is to split the data in two halves.

Numbers so far	Sorted	Median
`25`	25	25.0
`25 7`	7 25	(7 + 25) / 2 = 16.0
`25 7 10`	7 10 25	10.0
`25 7 10 15`	7 10 15 25	(10 + 15) / 2 = 12.5
`25 7 10 15 20`	7 10 15 20 25	15.0

Re-sorting after every arrival works but costs O(n log n) per element (or O(n) with insertion into a sorted list):

Python

def medians_naive(stream):
    seen, out = [], []
    for x in stream:
        seen.append(x)
        seen.sort()                                   # O(n log n) every time
        n = len(seen)
        m = seen[n // 2] if n % 2 else (seen[n // 2 - 1] + seen[n // 2]) / 2
        out.append(f"{m:.1f}")
    return out

print(*medians_naive([25, 7, 10, 15, 20]))

Output

25.0 16.0 10.0 12.5 15.0

Time O(n² log n) total · Space O(n)

Push x into small
The max-heap of the lower half.
Move small.top() to large
Guarantees every element of small is <= every element of large, even if x was big.
Rebalance
If large has more elements than small, move large.top() back. Now |small| = |large| or |small| = |large| + 1.
Read the median
small.top() when small is bigger, else (small.top() + large.top()) / 2.

One insertion into the two-heap structure

x = 20 arrives (seen: 25 7 10 15)
  small (max-heap) = {10, 7}     large (min-heap) = {15, 25}

1. small.push(20)        small = {20, 10, 7}   large = {15, 25}
2. large.push(small.pop) small = {10, 7}       large = {15, 20, 25}   ← 20 belongs in the upper half
3. |large| > |small|     small = {15, 10, 7}   large = {20, 25}       ← move 15 back
4. |small| > |large|     median = small.top() = 15

Python

import heapq

def running_medians(stream):
    small, large = [], []                   # small: max-heap via negation; large: min-heap
    out = []
    for x in stream:
        heapq.heappush(small, -x)
        heapq.heappush(large, -heapq.heappop(small))      # largest of small moves up
        if len(large) > len(small):
            heapq.heappush(small, -heapq.heappop(large))  # rebalance: small keeps the extra one
        if len(small) > len(large):
            out.append(f"{-small[0]:.1f}")
        else:
            out.append(f"{(-small[0] + large[0]) / 2:.1f}")
    return out

print(*running_medians([25, 7, 10, 15, 20]))

C++

#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    vector<int> stream = {25, 7, 10, 15, 20};
    priority_queue<int> small;                                 // max-heap: lower half
    priority_queue<int, vector<int>, greater<int>> large;      // min-heap: upper half
    cout << fixed << setprecision(1);
    bool firstOut = true;
    for (int x : stream) {
        small.push(x);
        large.push(small.top()); small.pop();                  // largest of small moves up
        if (large.size() > small.size()) { small.push(large.top()); large.pop(); }   // rebalance
        double median = small.size() > large.size() ? small.top() : (small.top() + large.top()) / 2.0;
        cout << (firstOut ? "" : " ") << median;
        firstOut = false;
    }
    cout << "\n";
}

Java

import java.util.Collections;
import java.util.Locale;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        int[] stream = {25, 7, 10, 15, 20};
        PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder());   // max-heap: lower half
        PriorityQueue<Integer> large = new PriorityQueue<>();                             // min-heap: upper half
        StringBuilder sb = new StringBuilder();
        for (int x : stream) {
            small.add(x);
            large.add(small.poll());                                   // largest of small moves up
            if (large.size() > small.size()) small.add(large.poll());  // rebalance
            double median = small.size() > large.size() ? small.peek() : (small.peek() + large.peek()) / 2.0;
            sb.append(String.format(Locale.ROOT, "%.1f", median)).append(' ');
        }
        System.out.println(sb.toString().trim());
    }
}

JavaScript

class Heap {
    constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
    size() { return this.a.length; }
    peek() { return this.a[0]; }
    push(x) {
        const a = this.a;
        a.push(x);
        let i = a.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(a[i], a[p]) >= 0) break;
            [a[i], a[p]] = [a[p], a[i]];
            i = p;
        }
    }
    pop() {
        const a = this.a, top = a[0], last = a.pop();
        if (a.length) {
            a[0] = last;
            let i = 0;
            for (;;) {
                let m = i;
                const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
                if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]];
                i = m;
            }
        }
        return top;
    }
}

function runningMedians(stream) {
    const small = new Heap((a, b) => b - a);                  // max-heap: lower half
    const large = new Heap((a, b) => a - b);                  // min-heap: upper half
    const out = [];
    for (const x of stream) {
        small.push(x);
        large.push(small.pop());                              // largest of small moves up
        if (large.size() > small.size()) small.push(large.pop());   // rebalance
        const median = small.size() > large.size() ? small.peek() : (small.peek() + large.peek()) / 2;
        out.push(median.toFixed(1));
    }
    return out;
}

console.log(runningMedians([25, 7, 10, 15, 20]).join(" "));

Output

25.0 16.0 10.0 12.5 15.0

Time O(log n) per element · Space O(n)

Choosing the heap

Problem	Heap type	Heap size	Time
k largest / k-th largest	min-heap	`k`	O(n log k)
k smallest / k closest	max-heap (on the key)	`k`	O(n log k)
sort a k-sorted array	min-heap	`k + 1`	O(n log k)
merge k sorted arrays	min-heap of heads	`k`	O(N log k)
buy cheapest first / schedule by priority	min-heap of everything	`n`	O(n + r log n)
running median	max-heap + min-heap	`n/2` each	O(log n) per element

Interview Q&A

Why is building a heap O(n) when n inserts cost O(n log n)?

Why a min-heap for the k largest elements?

Heap or balanced BST for a running median?

How do you get a max-heap in Python, and what is the catch?

Does a priority queue preserve insertion order for equal priorities?

What are the time bounds of the heap operations and why is search O(n)?