---
title: "Binary heap / priority queue"
url: https://algopath.pro/patterns/binary-heap
language: en
summary: "A heap keeps the smallest value at the very top and puts nothing else in order at all. Pushing and popping each cost log n."
updated: 2026-08-24
---

# Binary heap / priority queue

A heap keeps the smallest value at the very top and puts nothing else in order at all. Pushing and popping each cost log n.

## How does Binary heap / priority queue work?

A heap is a tree kept inside a flat array. The children of index i sit at 2i plus one and two.

The only rule is that a parent beats its children. Siblings are in no order whatsoever.

A push writes at the end, then bubbles the value up. It swaps with the parent while it wins.

A pop takes the root, moves the last item up there, and sinks it. It swaps with the better child until it fits.

Both moves walk one path of the tree. The height is log n, so both cost log n.

Only the root ever means anything. Every other position is arbitrary.

- `[5]` Pushing 5, 3 and 8. The first value is the root.
- `[3, 5]` 3 is pushed and bubbles above the 5.
- `[3, 5, 8]` 8 stays where it lands. It does not beat its parent.
- `pop returns 3` The root is taken away. The last item, 8, moves to the top.
- `[5, 8]` 8 sinks below the 5. The new root is the smallest left.

## When should you use Binary heap / priority queue?

- always need the current smallest/largest
- top k elements
- merge k sorted lists
- running median while items keep arriving
- priority queue / most urgent next

## What is Binary heap / priority queue confused with?

- **Fast sort (merge / quick)** - Sorting gives a full order once. A heap gives the front repeatedly, while data still arrives.
- **Binary search tree** - A search tree orders every pair of nodes. A heap only promises the root.
- **Monotonic deque (sliding window max/min)** - A deque can drop the element that just expired. A heap has no cheap way to do that.
- **Dijkstra's algorithm** - Dijkstra is the best-known user of a heap. This page is about the container itself.

## What is the time and space complexity of Binary heap / priority queue?

n up to 1e6 gives O(log n) per push or pop. Reading the top alone is O(1).

## A worked example of Binary heap / priority queue

### The k closest points to the origin

Return the k points that lie closest to the origin.

The list can be far too long to sort, and only k points are wanted.

Keep a heap of size k whose top is the worst point still kept.

Push each point, and pop the top whenever the heap grows past k. What remains is the answer.

```javascript
function kClosest(points, k) {
    // a max-heap keyed by squared distance: the worst kept point sits on top
    const heap = new MaxHeap((p) => p[0] * p[0] + p[1] * p[1]);

    for (const point of points) {
        heap.push(point);

        if (heap.size() > k) {
            heap.pop(); // drops the farthest, never the closest
        }
    }

    return heap.toArray();
}
```

## Common mistakes with Binary heap / priority queue

- **Expecting a sorted array** Only the root is in any order. Reading the array from front to back gives nonsense.
- **Keeping every element for a top-k question** A heap of size k costs O(n log k). Holding all of them costs more memory for no gain.
- **Building the heap the wrong way round** For the k largest you need a min-heap, so the worst kept sits on top. That is easy to invert.
- **Trying to delete an arbitrary element** A heap has no cheap way to find one. Mark it dead and skip it when it surfaces.

## Which interview problems use Binary heap / priority queue?

- **Kth largest element in a stream** A min-heap of size k, and the root is the answer.
- **K closest points to origin** A bounded max-heap over squared distance.
- **Merge k sorted lists** The heap holds the front node of every list.
- **Top k frequent elements** Counts first, then a heap of size k.
- **Task scheduler** The most frequent task goes first each round.
- **Find median from a data stream** Two heaps facing each other across the middle.
- **Dijkstra's shortest path** The heap decides which node to settle next.

## JavaScript

```javascript
function kSmallest(nums, k) {
    const heap = []; // max-heap: keeps the k smallest seen so far
    const swap = (i, j) => ([heap[i], heap[j]] = [heap[j], heap[i]]);
    function push(v) {
        heap.push(v);
        let i = heap.length - 1;
        while (i > 0 && heap[(i - 1) >> 1] < heap[i]) { swap((i - 1) >> 1, i); i = (i - 1) >> 1; }
    }
    function pop() {
        const top = heap[0];
        heap[0] = heap.pop();
        let i = 0;
        while (2 * i + 1 < heap.length) {
            let c = 2 * i + 1;
            if (c + 1 < heap.length && heap[c + 1] > heap[c]) c++;
            if (heap[i] >= heap[c]) break;
            swap(i, c); i = c;
        }
        return top;
    }
    for (const x of nums) {
        push(x);
        if (heap.length > k) pop();
    }
    return heap.slice().sort((a, b) => a - b);
}
```

## Python

```python
import heapq

def k_smallest(nums, k):
    heap = []  # max-heap via negation: keeps the k smallest seen so far
    for x in nums:
        heapq.heappush(heap, -x)
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(-x for x in heap)
```

## PHP

```php
function kSmallest(array $nums, int $k): array {
    $heap = new SplMaxHeap(); // keeps the k smallest seen so far
    foreach ($nums as $x) {
        $heap->insert($x);
        if ($heap->count() > $k) {
            $heap->extract();
        }
    }
    $result = [];
    foreach ($heap as $x) {
        $result[] = $x;
    }
    sort($result);
    return $result;
}
```