Heaps in five languages

A heap hands you the smallest item of a collection at any moment, and keeps doing so while items come and go: looking at the smallest item costs O(1), and adding an item or removing the smallest costs O(log n). That one operation drives top-k lists, merges of sorted streams, running medians, schedulers and shortest-path searches. Python, Java, C++ and Go each ship a heap in their standard library; JavaScript does not, so you keep a short one of your own. The five disagree on their defaults: Python’s heapq, Java’s PriorityQueue and Go’s container/heap give the smallest item first, and C++’s std::priority_queue gives the largest. This lesson runs one task in all five languages, then shows how to order entries so that ties and large numbers cannot break a heap, how to get the largest item first, and why building a heap from a whole list in one step beats pushing the items one at a time. It ends by solving one problem in full, from a brute force to code in five languages that is checked against it.

When a problem wants a heap

A heap answers one need: you repeatedly want the smallest item you hold (or the largest, or the most urgent), and the set of items changes between the times you ask. These cues in a problem statement point to one:

Shortest paths on weighted graphs use the same structure, as a frontier ordered by distance, in the graph modules of this track.

A heap is the wrong tool in four nearby cases. If you need the smallest item once, one pass over the data finds it in O(n) with no structure at all. If you need every item in order, sort once. If you must find, change or delete any item by its key, use a hash map or a sorted structure, because a heap knows where its top is and nothing else. And if the question asks for the nearest earlier item that is larger, that is the job of a monotonic stack.

What a heap promises

Every standard heap in this lesson is a binary heap: a list read as a binary tree that is filled level by level, from left to right. The item at index i has its children at 2i + 1 and 2i + 2 and its parent at (i − 1) // 2, so the tree needs no pointers. A min-heap keeps one rule, called the heap property: every parent is at most each of its children. Following parents upwards never increases a value, so the smallest item is always at the root, index 0. Python’s documentation states the rule for heapq as heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2].

import heapq

prices = [42, 17, 58, 17, 33, 71, 25]
heapq.heapify(prices)  # rearranges the list in place
print(prices)

[17, 17, 25, 42, 33, 71, 58]

The list is not sorted: 42 comes before 33, and nothing orders the two children of one parent. Only the root is certain, and that is all a heap promises. It is enough, because both operations repair the rule along a single path. A push puts the new item at the end and lets it rise past larger parents. A pop takes the root, moves the last item into its place and lets it sink below smaller children. A heap of n items is about log₂ n levels deep, so each walk is short: 20 levels for a million items.

A push is O(log n) amortised, because the list behind the heap grows now and then, and a build from a whole list works in place. Finding any item other than the top means looking through the whole list. Java’s documentation of PriorityQueue gives matching costs for its own methods: O(log n) for offer, poll and add, linear time for remove(Object) and contains(Object), and constant time for peek and size.

One task in five languages

Seven shops sell the same item, and you want the cheapest price, then the three cheapest. Here is that task in each language. The Python and JavaScript versions run in your browser; the Java, C++ and Go versions show a recorded terminal session.

# One item, seven shops: print the cheapest price, then take out the three cheapest.
import heapq

prices = [42, 17, 58, 17, 33, 71, 25]

heap = prices.copy()  # heapify works in place, so keep the original list as it was
heapq.heapify(heap)  # O(n): the smallest price is now heap[0]
print("cheapest first:", heap[0])
three = [heapq.heappop(heap) for _ in range(3)]
print("three cheapest:", *three)
print("left in the heap:", len(heap))

cheapest first: 17
three cheapest: 17 17 25
left in the heap: 4

// One item, seven shops: print the cheapest price, then take out the three cheapest.
import { MinHeap } from "./min_heap.mjs";

const prices = [42, 17, 58, 17, 33, 71, 25];

const heap = new MinHeap((a, b) => a - b); // smallest first
for (const p of prices) heap.push(p);
console.log("cheapest first:", heap.peek());
const three = [heap.pop(), heap.pop(), heap.pop()];
console.log("three cheapest:", three.join(" "));
console.log("left in the heap:", heap.size);

cheapest first: 17
three cheapest: 17 17 25
left in the heap: 4

// The binary heap template of the JavaScript toolkit lesson, as a module: the comparator decides
// what comes out first (negative: a before b), so (a, b) => b - a makes it a max-heap.
export class MinHeap {
  constructor(compare = (a, b) => a - b) {
    this.items = [];
    this.compare = compare;
  }

  get size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(value) {
    const a = this.items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(a[i], a[parent]) >= 0) break;
      [a[i], a[parent]] = [a[parent], a[i]];
      i = parent;
    }
  }

  pop() {
    const a = this.items;
    if (a.length === 0) return undefined;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const left = 2 * i + 1;
        const right = left + 1;
        let best = i;
        if (left < a.length && this.compare(a[left], a[best]) < 0) best = left;
        if (right < a.length && this.compare(a[right], a[best]) < 0) best = right;
        if (best === i) break;
        [a[i], a[best]] = [a[best], a[i]];
        i = best;
      }
    }
    return top;
  }
}

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

// One item, seven shops: print the cheapest price, then take out the three cheapest.
public class Cheapest {
    public static void main(String[] args) {
        List<Integer> prices = List.of(42, 17, 58, 17, 33, 71, 25);

        // Built from the list in one step, in natural ordering: the least element is the head.
        PriorityQueue<Integer> heap = new PriorityQueue<>(prices);
        System.out.println("cheapest first: " + heap.peek());
        System.out.println("three cheapest: " + heap.poll() + " " + heap.poll() + " " + heap.poll());
        System.out.println("left in the heap: " + heap.size());
    }
}

// One item, seven shops: print the cheapest price, then take out the three cheapest.
#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    const std::vector<int> prices{42, 17, 58, 17, 33, 71, 25};

    // The default comparison is std::less, which puts the LARGEST element on top.
    std::priority_queue<int> by_default(prices.begin(), prices.end());
    std::cout << "default top: " << by_default.top() << '\n';

    // std::greater<> turns it into a min-heap. The range constructor builds it in one step.
    std::priority_queue<int, std::vector<int>, std::greater<>> heap(prices.begin(), prices.end());
    std::cout << "cheapest first: " << heap.top() << '\n';
    std::cout << "three cheapest:";
    for (int i = 0; i < 3; ++i) {
        std::cout << ' ' << heap.top();  // pop() returns nothing, so read top() first
        heap.pop();
    }
    std::cout << "\nleft in the heap: " << heap.size() << '\n';
}

// One item, seven shops: print the cheapest price, then take out the three cheapest.
package main

import (
	"container/heap"
	"fmt"
)

// prices satisfies heap.Interface: Len, Less and Swap (sort.Interface), plus Push and Pop.
type prices []int

func (h prices) Len() int           { return len(h) }
func (h prices) Less(i, j int) bool { return h[i] < h[j] } // "<": the smallest comes out first
func (h prices) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

// Push and Pop are for package heap to call: they only add or remove at the end of the slice.
func (h *prices) Push(x any) { *h = append(*h, x.(int)) }
func (h *prices) Pop() any {
	old := *h
	last := old[len(old)-1]
	*h = old[:len(old)-1]
	return last
}

func main() {
	h := &prices{42, 17, 58, 17, 33, 71, 25}
	heap.Init(h) // one step, O(n), like Python's heapify
	fmt.Println("cheapest first:", (*h)[0])
	fmt.Print("three cheapest:")
	for i := 0; i < 3; i++ {
		fmt.Print(" ", heap.Pop(h)) // heap.Pop(h), never h.Pop()
	}
	fmt.Println()
	fmt.Println("left in the heap:", h.Len())
}

from session import run, versions

# Cheapest.java runs as a single source file, cheapest.cpp is built with the sanitizers on, and go run builds cheapest.go.
versions("java -version", "clang++ --version", "go version")
run("""
java Cheapest.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined cheapest.cpp -o cheapest && ./cheapest
go run cheapest.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java Cheapest.java
cheapest first: 17
three cheapest: 17 17 25
left in the heap: 4
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined cheapest.cpp -o cheapest && ./cheapest
default top: 71
cheapest first: 17
three cheapest: 17 17 25
left in the heap: 4
$ go run cheapest.go
cheapest first: 17
three cheapest: 17 17 25
left in the heap: 4

All five agree on the answer, 17, 17 and 25, and the code shows where they differ.

• Python. heapq is a set of functions over an ordinary list, so the list is the heap. heapify rearranges it in place, heap[0] is the smallest item, and heappop raises IndexError on an empty heap. Copy the list first if you still need its original order.
• JavaScript. The language has no heap, so min_heap.mjs is the short class from the JavaScript toolkit lesson: an array, a comparator and two loops, one that moves a new item up and one that moves the last item down after a pop. The comparator decides the order as it does for sort: a negative result means its first argument comes out first.
• Java. A PriorityQueue built from a list uses the elements’ natural ordering, which puts the least element at the head. peek and poll return null on an empty queue instead of throwing. java Cheapest.java runs the source file directly, without a separate javac step.
• C++. std::priority_queue is the odd one out: its default comparison is std::less, and the standard keeps on top the element that is greatest under the comparison, which is why the default queue printed 71. Pass std::greater<> as the third template argument to get the smallest first. pop() returns nothing, so read top() before you pop. The build switches on AddressSanitizer and UndefinedBehaviorSanitizer, which check memory accesses and undefined behaviour while the program runs, and they reported nothing.
• Go. container/heap supplies the algorithms, and you supply the type: a slice with Len, Less and Swap, plus Push and Pop methods that only add and remove at the end of the slice. heap.Init builds the heap in O(n), and from then on you call heap.Push(h, x) and heap.Pop(h). The package documentation says its interface methods are for the package to call: h.Pop() called directly just removes the last element, skipping the reordering, and the heap silently breaks.

Ties, tuples and comparators

Real heap entries carry a priority and a payload: a price and a seller, a time and a job. Two things go wrong in practice: priorities tie, and comparisons that look harmless break on large numbers.

Python: a tie moves the comparison to the next element

Python heaps usually hold tuples, and tuples compare element by element: the first pair that differs decides. Equal priorities therefore send the comparison on to the payload. When the payload is a dictionary, which has no order, heappush fails:

import heapq
import itertools

# Two jobs share priority 2. Tuples compare element by element, so the tie
# makes heapq compare the two dictionaries, which have no order.
jobs = []
heapq.heappush(jobs, (2, {"name": "send invoices"}))
try:
    heapq.heappush(jobs, (2, {"name": "back up the database"}))
except TypeError as error:
    print("TypeError:", error)

# The fix: a running number between the priority and the job. No two numbers
# are equal, so the dictionaries are never compared, and jobs with the same
# priority come out in the order they went in.
arrival = itertools.count()
jobs = []
for priority, name in [(2, "send invoices"), (1, "renew the certificate"), (2, "back up the database"), (2, "rotate the logs")]:
    heapq.heappush(jobs, (priority, next(arrival), {"name": name}))
while jobs:
    priority, _, job = heapq.heappop(jobs)
    print(priority, job["name"])

TypeError: '<' not supported between instances of 'dict' and 'dict'
1 renew the certificate
2 send invoices
2 back up the database
2 rotate the logs

The heapq documentation recommends the fix used in the second half: a running count between the priority and the payload. No two counts are equal, so a comparison never reaches the payload, and among equal priorities the entry pushed first comes out first. itertools.count() numbers the entries; in a loop over a list, the index from enumerate does the same job.

Java: ties come out in any order, and subtraction overflows

The PriorityQueue documentation says that when several elements tie for least, ties are broken arbitrarily: the order of equal elements has nothing to do with the order in which you added them. This program adds six offers, five of them at the same price, to two queues, one that compares prices only and one that compares the listing number too:

from session import run, versions

# Equal prices with and without a tie-breaker, then a comparator that subtracts.
versions("java -version")
run("""
java Ties.java
""")

# openjdk version "25.0.4.1" LTS
$ java Ties.java
listed:                 asha bala chen dev esha farid
by price:               dev farid esha bala chen asha
by price, then number:  dev asha bala chen esha farid
a - b as an int:        -294967296
(x, y) -> x - y:        5 2000000000 -2000000000
Integer::compare:       -2000000000 5 2000000000

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

public class Ties {
    record Offer(String seller, int price, int number) {}

    static String drain(PriorityQueue<Offer> heap) {
        List<String> out = new ArrayList<>();
        while (!heap.isEmpty()) out.add(heap.poll().seller());
        return String.join(" ", out);
    }

    static String drainInts(PriorityQueue<Integer> heap) {
        List<String> out = new ArrayList<>();
        while (!heap.isEmpty()) out.add(String.valueOf(heap.poll()));
        return String.join(" ", out);
    }

    public static void main(String[] args) {
        String[] sellers = {"asha", "bala", "chen", "dev", "esha", "farid"};
        int[] prices = {300, 300, 300, 100, 300, 300};

        // Price alone leaves ties to the heap; price, then listing number, decides every tie.
        PriorityQueue<Offer> byPrice = new PriorityQueue<>(Comparator.comparingInt(Offer::price));
        PriorityQueue<Offer> byPriceThenNumber =
                new PriorityQueue<>(Comparator.comparingInt(Offer::price).thenComparingInt(Offer::number));
        for (int i = 0; i < sellers.length; i++) {
            byPrice.add(new Offer(sellers[i], prices[i], i));
            byPriceThenNumber.add(new Offer(sellers[i], prices[i], i));
        }
        System.out.println("listed:                 " + String.join(" ", sellers));
        System.out.println("by price:               " + drain(byPrice));
        System.out.println("by price, then number:  " + drain(byPriceThenNumber));

        // Subtraction overflows int when the two values are far apart.
        int a = 2_000_000_000, b = -2_000_000_000;
        System.out.println("a - b as an int:        " + (a - b));
        PriorityQueue<Integer> subtracting = new PriorityQueue<>((x, y) -> x - y);
        PriorityQueue<Integer> comparing = new PriorityQueue<>(Integer::compare);
        for (int value : new int[] {a, b, 5}) {
            subtracting.add(value);
            comparing.add(value);
        }
        System.out.println("(x, y) -> x - y:        " + drainInts(subtracting));
        System.out.println("Integer::compare:       " + drainInts(comparing));
    }
}

Comparing prices alone, the five offers at 300 came out as farid, esha, bala, chen and asha, almost the reverse of their listing order. With the listing number as a second key, added by thenComparingInt, every tie is decided and the offers came back in listing order. No heap in this lesson promises more than Java’s: the heapq documentation lists getting equal priorities back in the order they were added as a problem to solve, and the counter above is its answer. When the order of equal items matters, put the arrival number into the key.

The last lines show the second trap. (x, y) -> x - y looks like a comparator, but int arithmetic wraps around: the Java Language Specification says that an integer sum that overflows keeps only its low-order bits. 2,000,000,000 − (−2,000,000,000) is 4,000,000,000, which does not fit in an int, and it came out as −294,967,296. The comparator then claimed that 2,000,000,000 is less than −2,000,000,000, and the queue handed out 5 first. Integer.compare, or Comparator.comparingInt, compares the values without subtracting them.

C++, Go and JavaScript

• C++. std::tuple and std::pair compare member by member, like Python’s tuples, so a std::tuple<int, int, std::string> of price, listing number and seller works with std::greater<>. A comparator for a struct of your own has a reversed feel: the queue puts on top the element that is greatest under the comparator, so for the cheapest first the comparator must return true when its first argument should come out later, that is, when it costs more.
• Go. Less(i, j) reports whether item i should come out before item j. Compare the prices, and when they are equal, the listing numbers.
• JavaScript. A comparator returns a number, and || chains keys: (a, b) => a.price - b.price || a.number - b.number. Subtracting is safe there, because JavaScript numbers hold every integer up to Number.MAX_SAFE_INTEGER, 2⁵³ − 1, exactly. In Java, whose int has 32 bits, the same habit breaks as soon as two values can be more than about 2.1 billion apart, as the run above showed.

Largest first

Every heap in this lesson can hand out the largest item instead.

import heapq

scores = [61, 94, 78, 94, 55]

# Python 3.14 and later: the max-heap functions work on an ordinary list.
best = scores.copy()
heapq.heapify_max(best)
print("3.14 max-heap:", best[0], "then", heapq.heappop_max(best), heapq.heappop_max(best))

# Any version: keep negated scores in an ordinary min-heap, and negate them back on the way out.
negated = [-s for s in scores]
heapq.heapify(negated)
print("negated keys: ", -negated[0], "then", -heapq.heappop(negated), -heapq.heappop(negated))

# Negating works for numbers only.
try:
    -"zebra"
except TypeError as error:
    print("TypeError:", error)

3.14 max-heap: 94 then 94 94
negated keys:  94 then 94 94
TypeError: bad operand type for unary -: 'str'

• Python, any version: flip the sign of each number as it goes into an ordinary min-heap, and flip it back as it comes out, so the largest value sits at the root as the most negative one. That only works for numbers, as the last line of the run shows; for strings, use the 3.14 functions.
• Java: new PriorityQueue<>(Comparator.reverseOrder()) reverses the natural ordering, and reversed() turns any comparator of your own around.
• C++: the default already gives the largest first.
• Go and JavaScript: flip the comparison, h[i] > h[j] in Less and (a, b) => b - a for the class.

Building a heap in one step

When all the items are there from the start, build the heap in one step. Python’s documentation says that heapify transforms a list into a heap in place, in linear time. Go’s says that heap.Init is O(n). The C++ standard has priority_queue’s constructor from two iterators call make_heap, which makes at most three comparisons per element. Pushing the items one at a time costs up to O(log n) each, O(n log n) in all. Sorting is a third way, because a list in ascending order already satisfies the heap property. This program counts the comparisons of all three on 100,000 numbers in three orders:

"""Comparisons made by heapify, by n pushes and by sorting, counted on 100,000 numbers in three orders."""
import heapq
import random


class Counted:
    """A number that counts every comparison made between such numbers."""

    comparisons = 0
    __slots__ = ("value",)

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Counted.comparisons += 1
        return self.value < other.value


def by_heapify(values):
    heap = [Counted(v) for v in values]
    Counted.comparisons = 0
    heapq.heapify(heap)
    return Counted.comparisons


def by_pushes(values):
    items = [Counted(v) for v in values]
    Counted.comparisons = 0
    heap = []
    for item in items:
        heapq.heappush(heap, item)
    return Counted.comparisons


def by_sorting(values):
    items = [Counted(v) for v in values]
    Counted.comparisons = 0
    items.sort()  # an ascending list is a valid min-heap too
    return Counted.comparisons


n = 100_000
orders = {
    "random": random.Random(7).sample(range(n), n),
    "ascending": list(range(n)),
    "descending": list(range(n, 0, -1)),
}
print(f"{'order':<11}{'heapify':>10}{'pushes':>12}{'sorting':>12}")
for name, values in orders.items():
    print(f"{name:<11}{by_heapify(values):>10,}{by_pushes(values):>12,}{by_sorting(values):>12,}")

order         heapify      pushes     sorting
random        165,086     227,558   1,531,850
ascending     199,983      99,999      99,999
descending    149,988   1,468,946      99,999

heapify made between 1.5 and 2 comparisons per number in every order. The pushes depend on the order:

• Ascending. Each new number is larger than its parent, so it costs one comparison and stays where it lands: 99,999 in all, half of what heapify made.
• Random. A new number rarely climbs far: 227,558 comparisons, about 1.4 times heapify’s 165,086.
• Descending. Every new number is the smallest so far and climbs all the way to the root: 1,468,946 comparisons, almost ten times heapify’s 149,988.

So O(n log n) for n pushes is a worst case, and input that arrives in order reaches it. Sorting shows the opposite pattern: 1,531,850 comparisons on the random numbers, more than nine times heapify’s, but only 99,999 on either sorted order, because Python’s sort takes advantage of any order already in the data, as its documentation says. heapify’s cost hardly moves with the input, and that is the reason to prefer it when all you need is a heap.

Java offers the same choice with a catch. new PriorityQueue<>(collection) builds from a collection in one step, but it orders the elements by their natural ordering, and no constructor takes both a collection and a comparator. With a comparator you create an empty queue and add the elements, and addAll adds them one at a time, as its documentation says. The documentation states no cost for the constructor, so this program counts the comparisons on 100,000 numbers in descending order:

from session import run, versions

# Two ways to fill a PriorityQueue with 100,000 numbers, with their comparisons counted.
versions("java -version")
run("""
java BuildCost.java
""")

# openjdk version "25.0.4.1" LTS
$ java BuildCost.java
new PriorityQueue<>(list):            199,978 comparisons
comparator queue, then addAll:      1,468,946 comparisons
smallest in each: 1 and 1

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

// Comparisons made by two ways of filling a PriorityQueue with 100,000 numbers in descending order.
public class BuildCost {
    static long comparisons = 0;

    // Natural ordering, with a counter: the collection constructor uses compareTo.
    record Price(int value) implements Comparable<Price> {
        public int compareTo(Price other) {
            comparisons++;
            return Integer.compare(value, other.value);
        }
    }

    public static void main(String[] args) {
        int n = 100_000;
        List<Price> descending = new ArrayList<>();
        for (int v = n; v >= 1; v--) descending.add(new Price(v));

        comparisons = 0;
        PriorityQueue<Price> fromList = new PriorityQueue<>(descending);
        System.out.printf("new PriorityQueue<>(list):        %,11d comparisons%n", comparisons);

        // No constructor takes a collection and a comparator, so with a comparator the numbers go in one add at a time.
        Comparator<Price> counting = (x, y) -> {
            comparisons++;
            return Integer.compare(x.value(), y.value());
        };
        comparisons = 0;
        PriorityQueue<Price> withComparator = new PriorityQueue<>(counting);
        withComparator.addAll(descending);
        System.out.printf("comparator queue, then addAll:    %,11d comparisons%n", comparisons);

        System.out.println("smallest in each: " + fromList.peek().value() + " and " + withComparator.peek().value());
    }
}

The constructor made 199,978 comparisons, under two per number. The comparator queue made 1,468,946, the same count as Python’s pushes on the same input, because every number climbed to the root. When a Java solution must build a large heap ordered by its own key, give the element type a natural ordering: a record that implements Comparable, passed to the constructor as a list.

A worked problem: the cheapest ticket at a resale counter

Settle the details that change the code before you write any:

• Does the order of equal prices matter? Yes: the earlier listing sells first, which is why a report names the seller.
• What does a buy report when nothing is on sale? none, and the counter carries on.
• How large can the numbers get? Prices fit a 32-bit integer in every language, and no sum is ever formed.
• How many tickets can wait at once? Up to 200,000, if every event before the buys is a sale.

Work the first example by hand and keep it as a test. The events sell asha 300, sell bala 250, sell chen 300, buy, sell dev 250, buy, buy, buy, buy give bala 250, dev 250, asha 300, chen 300, none. Bala’s 250 is the cheapest at the first buy. Dev’s 250 arrives later and sells next, as the only 250 left. Asha’s 300 goes before Chen’s because Asha listed first, and the last buy finds nothing.

The brute force

Keep the tickets on sale in a list, in listing order. A sale appends; a buy scans the whole list for the lowest price and removes the first ticket it found at that price:

def resale_counter_brute(events):
    """Keeps the tickets on sale in listing order and scans them all on every buy."""
    on_sale = []  # (price, seller) pairs, oldest listing first
    reports = []
    for event in events:
        parts = event.split()
        if parts[0] == "sell":
            on_sale.append((int(parts[2]), parts[1]))
        elif not on_sale:
            reports.append("none")
        else:
            best = 0
            for i in range(1, len(on_sale)):
                if on_sale[i][0] < on_sale[best][0]:  # strictly cheaper: an equal price never replaces an older listing
                    best = i
            price, seller = on_sale.pop(best)
            reports.append(f"{seller} {price}")
    return reports


if __name__ == "__main__":
    events = ["sell asha 300", "sell bala 250", "sell chen 300", "buy", "sell dev 250", "buy", "buy", "buy", "buy"]
    print(", ".join(resale_counter_brute(events)))

bala 250, dev 250, asha 300, chen 300, none

It is easy to trust: the strict < means an equal price never replaces an older listing. But each buy costs time in proportion to the tickets on sale. The worst input lists 100,000 tickets and then buys 100,000 times, and the scans compare 99,999 + 99,998 + … + 1 pairs, 4,999,950,000 in all. Using the rough rates from the lesson on constraints, a hundred million simple steps each second in a compiled language and ten million in CPython, that comes to roughly 50 seconds in C++ and more than 8 minutes in Python, where the limit is a few seconds.

What to notice

Each buy needs exactly one thing: the cheapest ticket, the earliest one on a tie. The order of all the other tickets never matters. Tickets keep arriving between buys, so sorting once at the start is not enough, and keeping a sorted list means moving part of it on every sale that lands in the middle. Repeatedly taking the smallest item while new items arrive is the heap’s cue from the start of this lesson.

A heap of (price, listing number, seller)

Keep the tickets on sale in a min-heap of entries (price, listing number, seller). A sale pushes an entry; a buy pops the smallest entry, or reports none when the heap is empty. The listing number is the event’s position in the list, so it is unique and grows with time. It does two jobs: among equal prices it puts the earlier listing first, and because no two entries are ever equal, a comparison never reaches the seller.

Each event costs one push or one pop on a heap of at most n entries, so n events take O(n log n) time, and the heap holds at most one entry per ticket.

A dry run

This version prints the heap after every event of the first example, as the list that stores it:

# The heap after every event of the first example, in the order the list keeps it.
import heapq

events = ["sell asha 300", "sell bala 250", "sell chen 300", "buy", "sell dev 250", "buy", "buy", "buy", "buy"]
on_sale = []
for number, event in enumerate(events):
    parts = event.split()
    report = ""
    if parts[0] == "sell":
        heapq.heappush(on_sale, (int(parts[2]), number, parts[1]))
    elif on_sale:
        price, _, seller = heapq.heappop(on_sale)
        report = f"-> {seller} {price}"
    else:
        report = "-> none"
    entries = "  ".join(f"({p}, {n}, {s})" for p, n, s in on_sale) or "empty"
    print(f"{event:<14}{report:<14}heap: {entries}")

sell asha 300               heap: (300, 0, asha)
sell bala 250               heap: (250, 1, bala)  (300, 0, asha)
sell chen 300               heap: (250, 1, bala)  (300, 0, asha)  (300, 2, chen)
buy           -> bala 250   heap: (300, 0, asha)  (300, 2, chen)
sell dev 250                heap: (250, 4, dev)  (300, 2, chen)  (300, 0, asha)
buy           -> dev 250    heap: (300, 0, asha)  (300, 2, chen)
buy           -> asha 300   heap: (300, 2, chen)
buy           -> chen 300   heap: empty
buy           -> none       heap: empty

Read the heap column as a list, not as a sorted order. After sell dev 250, Dev’s entry has climbed to the root, past both entries at 300, and Asha’s entry sits last although it is the older of the two. When Dev’s entry is popped, the heap repairs itself, and Asha’s (300, 0) beats Chen’s (300, 2) on the listing number, so Asha sells before Chen. The lesson on dry runs shows how to keep a trace like this by hand.

The same counter in five languages

import heapq


def resale_counter(events):
    """Sells the cheapest ticket on every buy; equal prices go in the order they were listed."""
    on_sale = []  # a min-heap of (price, listing number, seller)
    reports = []
    for number, event in enumerate(events):
        parts = event.split()
        if parts[0] == "sell":
            heapq.heappush(on_sale, (int(parts[2]), number, parts[1]))
        elif on_sale:
            price, _, seller = heapq.heappop(on_sale)
            reports.append(f"{seller} {price}")
        else:
            reports.append("none")
    return reports


if __name__ == "__main__":
    first = ["sell asha 300", "sell bala 250", "sell chen 300", "buy", "sell dev 250", "buy", "buy", "buy", "buy"]
    second = ["buy", "sell esha 120", "sell farid 120", "sell gita 90", "buy", "buy"]
    print(", ".join(resale_counter(first)))
    print(", ".join(resale_counter(second)))

bala 250, dev 250, asha 300, chen 300, none
none, gita 90, esha 120

import { MinHeap } from "./min_heap.mjs";

// Sells the cheapest ticket on every buy; equal prices go in the order they were listed.
function resaleCounter(events) {
  // Lower price first; for equal prices, the lower listing number. Subtracting is safe here: prices
  // are at most 10^9 and JavaScript numbers hold integers exactly up to 2^53.
  const onSale = new MinHeap((a, b) => a.price - b.price || a.number - b.number);
  const reports = [];
  events.forEach((event, number) => {
    const [kind, seller, price] = event.split(" ");
    if (kind === "sell") {
      onSale.push({ price: Number(price), number, seller });
    } else if (onSale.size > 0) {
      const ticket = onSale.pop();
      reports.push(`${ticket.seller} ${ticket.price}`);
    } else {
      reports.push("none");
    }
  });
  return reports;
}

const first = ["sell asha 300", "sell bala 250", "sell chen 300", "buy", "sell dev 250", "buy", "buy", "buy", "buy"];
const second = ["buy", "sell esha 120", "sell farid 120", "sell gita 90", "buy", "buy"];
console.log(resaleCounter(first).join(", "));
console.log(resaleCounter(second).join(", "));

bala 250, dev 250, asha 300, chen 300, none
none, gita 90, esha 120

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

public class Counter {
    record Ticket(int price, int number, String seller) {}

    // Sells the cheapest ticket on every buy; equal prices go in the order they were listed.
    static List<String> resaleCounter(List<String> events) {
        // Integer.compare inside comparingInt, never a subtraction; the listing number decides every tie.
        PriorityQueue<Ticket> onSale =
                new PriorityQueue<>(Comparator.comparingInt(Ticket::price).thenComparingInt(Ticket::number));
        List<String> reports = new ArrayList<>();
        for (int number = 0; number < events.size(); number++) {
            String[] parts = events.get(number).split(" ");
            if (parts[0].equals("sell")) {
                onSale.add(new Ticket(Integer.parseInt(parts[2]), number, parts[1]));
            } else if (!onSale.isEmpty()) {
                Ticket t = onSale.poll();
                reports.add(t.seller() + " " + t.price());
            } else {
                reports.add("none");
            }
        }
        return reports;
    }

    public static void main(String[] args) {
        List<String> first = List.of("sell asha 300", "sell bala 250", "sell chen 300", "buy", "sell dev 250", "buy", "buy", "buy", "buy");
        List<String> second = List.of("buy", "sell esha 120", "sell farid 120", "sell gita 90", "buy", "buy");
        System.out.println(String.join(", ", resaleCounter(first)));
        System.out.println(String.join(", ", resaleCounter(second)));
    }
}

#include <functional>
#include <iostream>
#include <queue>
#include <sstream>
#include <string>
#include <tuple>
#include <vector>

// Sells the cheapest ticket on every buy; equal prices go in the order they were listed.
std::vector<std::string> resale_counter(const std::vector<std::string>& events) {
    // (price, listing number, seller): tuples compare member by member, as in Python, and
    // std::greater<> makes the smallest come out first. Listing numbers never repeat, so the
    // sellers are never compared.
    using Ticket = std::tuple<int, int, std::string>;
    std::priority_queue<Ticket, std::vector<Ticket>, std::greater<>> on_sale;
    std::vector<std::string> reports;
    for (int number = 0; number < static_cast<int>(events.size()); ++number) {
        std::istringstream in(events[number]);
        std::string kind, seller;
        int price = 0;
        in >> kind >> seller >> price;
        if (kind == "sell") {
            on_sale.emplace(price, number, seller);
        } else if (!on_sale.empty()) {
            const auto [p, n, s] = on_sale.top();  // copy the ticket out before pop() destroys it
            on_sale.pop();
            reports.push_back(s + " " + std::to_string(p));
        } else {
            reports.push_back("none");
        }
    }
    return reports;
}

void print(const std::vector<std::string>& reports) {
    for (std::size_t i = 0; i < reports.size(); ++i) std::cout << (i ? ", " : "") << reports[i];
    std::cout << '\n';
}

int main() {
    print(resale_counter({"sell asha 300", "sell bala 250", "sell chen 300", "buy", "sell dev 250", "buy", "buy", "buy", "buy"}));
    print(resale_counter({"buy", "sell esha 120", "sell farid 120", "sell gita 90", "buy", "buy"}));
}

package main

import (
	"container/heap"
	"fmt"
	"strconv"
	"strings"
)

type ticket struct {
	price, number int
	seller        string
}

// tickets is a min-heap: Less says which ticket must come out first.
type tickets []ticket

func (h tickets) Len() int { return len(h) }
func (h tickets) Less(i, j int) bool {
	if h[i].price != h[j].price {
		return h[i].price < h[j].price
	}
	return h[i].number < h[j].number // equal prices: the earlier listing first
}
func (h tickets) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *tickets) Push(x any)   { *h = append(*h, x.(ticket)) }
func (h *tickets) Pop() any {
	old := *h
	last := old[len(old)-1]
	*h = old[:len(old)-1]
	return last
}

// resaleCounter sells the cheapest ticket on every buy; equal prices go in the order they were listed.
func resaleCounter(events []string) []string {
	onSale := &tickets{}
	var reports []string
	for number, event := range events {
		parts := strings.Fields(event)
		switch {
		case parts[0] == "sell":
			price, _ := strconv.Atoi(parts[2])
			heap.Push(onSale, ticket{price, number, parts[1]})
		case onSale.Len() > 0:
			t := heap.Pop(onSale).(ticket)
			reports = append(reports, t.seller+" "+strconv.Itoa(t.price))
		default:
			reports = append(reports, "none")
		}
	}
	return reports
}

func main() {
	first := []string{"sell asha 300", "sell bala 250", "sell chen 300", "buy", "sell dev 250", "buy", "buy", "buy", "buy"}
	second := []string{"buy", "sell esha 120", "sell farid 120", "sell gita 90", "buy", "buy"}
	fmt.Println(strings.Join(resaleCounter(first), ", "))
	fmt.Println(strings.Join(resaleCounter(second), ", "))
}

from session import run, versions

# The resale counter in Java, C++ (built with the sanitizers on) and Go, each on the two sample event lists.
versions("java -version", "clang++ --version", "go version")
run("""
java Counter.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined counter.cpp -o counter && ./counter
go run counter.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java Counter.java
bala 250, dev 250, asha 300, chen 300, none
none, gita 90, esha 120
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined counter.cpp -o counter && ./counter
bala 250, dev 250, asha 300, chen 300, none
none, gita 90, esha 120
$ go run counter.go
bala 250, dev 250, asha 300, chen 300, none
none, gita 90, esha 120

All five print the same two lines, and each settles ties on the listing number in its own way. Python and C++ compare tuples member by member. Java chains comparingInt(Ticket::price) with thenComparingInt(Ticket::number). Go’s Less compares the numbers when the prices are equal, and the JavaScript comparator chains the two keys with ||. The C++ version copies the top ticket out before pop(), because pop() destroys the element.

Checked against the brute force

A slow version you trust is the best test of a fast one, so this program runs both on random event lists:

"""The heap version against the brute force on 2,000 random event lists with many equal prices."""
import random

from brute import resale_counter_brute
from counter import resale_counter

rng = random.Random(5)
sellers = ["asha", "bala", "chen", "dev", "esha"]
agreed = 0
for trial in range(2000):
    events = []
    for _ in range(rng.randint(0, 12)):
        if rng.random() < 0.6:
            events.append(f"sell {rng.choice(sellers)} {rng.randint(1, 4) * 10}")  # 4 prices: ties everywhere
        else:
            events.append("buy")
    fast, slow = resale_counter(events), resale_counter_brute(events)
    if trial == 0:
        print("first list:", events)
        print("reports:   ", fast)
    if fast != slow:
        print("they disagree on", events)
        print("heap:       ", fast)
        print("brute force:", slow)
        break
    agreed += 1
print(f"{agreed} of 2000 random event lists: the same reports from both")

first list: ['sell chen 10', 'buy', 'buy', 'sell asha 20', 'sell dev 20', 'sell asha 20', 'sell bala 40', 'sell dev 20', 'buy']
reports:    ['chen 10', 'none', 'asha 20']
2000 of 2000 random event lists: the same reports from both

The random lists use only four prices, so ties are everywhere, and they mix sales, buys and buys at an empty counter. The heap version and the brute force gave the same reports for all 2,000 lists. On the input that hurts the brute force most, the difference is easy to count:

"""Comparisons on the input that hurts the brute force most: 100,000 sells, then 100,000 buys."""
import heapq
import random


class Entry(tuple):
    """A heap entry that counts how often it is compared."""

    comparisons = 0

    def __lt__(self, other):
        Entry.comparisons += 1
        return tuple.__lt__(self, other)


rng = random.Random(3)
sells = 100_000
events = [f"sell s{i} {rng.randint(1, 10**9)}" for i in range(sells)] + ["buy"] * sells

# Each buy of the brute force compares every ticket on sale with the best one so far: one fewer than are left.
brute = sum(left - 1 for left in range(sells, 0, -1))

on_sale = []
for number, event in enumerate(events):
    parts = event.split()
    if parts[0] == "sell":
        heapq.heappush(on_sale, Entry((int(parts[2]), number, parts[1])))
    else:
        heapq.heappop(on_sale)

print(f"events:      {len(events):,}")
print(f"brute force: {brute:,} comparisons")
print(f"heap:        {Entry.comparisons:,} comparisons")
print(f"the brute force makes about {round(brute / Entry.comparisons):,} times as many")

events:      200,000
brute force: 4,999,950,000 comparisons
heap:        1,762,567 comparisons
the brute force makes about 2,837 times as many

The brute force’s count follows from the length of the list that each buy scans; the heap’s was counted one comparison at a time. The heap made 1,762,567 comparisons, about 2,800 times fewer.

Practise: the k smallest values so far

The exercise turns the idea around. After each value of a stream, report the k smallest values seen so far. A heap that gives the largest first keeps them at hand, because its top is the value to drop when a smaller one arrives, and it never holds more than k values. The next lesson of this module builds the same size-k heap into a general method for top-k problems. The JavaScript starter file already holds the MinHeap class, so a reversed comparator is all it needs.

k_smallest_streaming([5, 1, 4, 1, 3], 2)
# [[5], [1, 5], [1, 4], [1, 1], [1, 1]]
k_smallest_streaming([7, 3, 9], 5)
# [[7], [3, 7], [3, 7, 9]]

import heapq


def k_smallest_streaming(stream, k):
    """After each value of stream, the k smallest values seen so far, in ascending order.

    Returns one list per value of stream; while fewer than k values have arrived, a list holds all of them.
    k is at least 1, and the values are integers that may be negative and may repeat. Leave stream unchanged.
    """
    # Replace this line with your code.
    return []

import random

from k_smallest import k_smallest_streaming


def test_the_example():
    """[5, 1, 4, 1, 3] with k = 2"""
    assert k_smallest_streaming([5, 1, 4, 1, 3], 2) == [[5], [1, 5], [1, 4], [1, 1], [1, 1]]


def test_fewer_values_than_k():
    """until k values have arrived, every value seen so far is kept"""
    assert k_smallest_streaming([7, 3, 9], 5) == [[7], [3, 7], [3, 7, 9]]


def test_an_empty_stream():
    """no values, no lists"""
    assert k_smallest_streaming([], 3) == []


def test_k_is_one():
    """k = 1 is the running minimum"""
    assert k_smallest_streaming([4, 6, 2, 2, 8, -1], 1) == [[4], [4], [2], [2], [2], [-1]]


def test_negative_values_and_repeats():
    """negative values, and a value equal to the largest kept one"""
    assert k_smallest_streaming([-3, 0, -3, -7, 2, -3], 3) == [
        [-3],
        [-3, 0],
        [-3, -3, 0],
        [-7, -3, -3],
        [-7, -3, -3],
        [-7, -3, -3],
    ]


def test_each_list_is_its_own():
    """changing one list of the result changes no other"""
    result = k_smallest_streaming([3, 1, 2], 2)
    result[0].append(99)
    assert result[1:] == [[1, 3], [1, 2]]


def test_the_stream_is_left_unchanged():
    """the input list is the caller's"""
    stream = [5, 2, 8, 1]
    k_smallest_streaming(stream, 2)
    assert stream == [5, 2, 8, 1]


def test_against_sorting():
    """400 random streams, checked against sorting every prefix"""
    rng = random.Random(8)
    for _ in range(400):
        stream = [rng.randint(-20, 20) for _ in range(rng.randint(0, 25))]
        k = rng.randint(1, 6)
        expected = [sorted(stream[: i + 1])[:k] for i in range(len(stream))]
        assert k_smallest_streaming(stream, k) == expected, (stream, k)

// The lesson's binary heap: the comparator decides what comes out first (negative: a before b).
export class MinHeap {
  constructor(compare = (a, b) => a - b) {
    this.items = [];
    this.compare = compare;
  }

  get size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(value) {
    const a = this.items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(a[i], a[parent]) >= 0) break;
      [a[i], a[parent]] = [a[parent], a[i]];
      i = parent;
    }
  }

  pop() {
    const a = this.items;
    if (a.length === 0) return undefined;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const left = 2 * i + 1;
        const right = left + 1;
        let best = i;
        if (left < a.length && this.compare(a[left], a[best]) < 0) best = left;
        if (right < a.length && this.compare(a[right], a[best]) < 0) best = right;
        if (best === i) break;
        [a[i], a[best]] = [a[best], a[i]];
        i = best;
      }
    }
    return top;
  }
}

/**
 * After each value of stream, the k smallest values seen so far, in ascending order. Returns one array per value of
 * stream; while fewer than k values have arrived, an array holds all of them. k is at least 1, and the values are
 * integers that may be negative and may repeat. Leave stream unchanged.
 */
export function kSmallestStreaming(stream, k) {
  // Replace this line with your code.
  return [];
}

import { test, assert } from 'mysmartcopilot:test';
import { kSmallestStreaming } from './k_smallest.mjs';

let seed = 8;
const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
const randInt = (lo, hi) => lo + Math.floor(random() * (hi - lo + 1));

test('[5, 1, 4, 1, 3] with k = 2', () => {
  assert.deepEqual(kSmallestStreaming([5, 1, 4, 1, 3], 2), [[5], [1, 5], [1, 4], [1, 1], [1, 1]]);
});

test('until k values have arrived, every value seen so far is kept', () => {
  assert.deepEqual(kSmallestStreaming([7, 3, 9], 5), [[7], [3, 7], [3, 7, 9]]);
});

test('an empty stream gives no arrays, and k = 1 is the running minimum', () => {
  assert.deepEqual(kSmallestStreaming([], 3), []);
  assert.deepEqual(kSmallestStreaming([4, 6, 2, 2, 8, -1], 1), [[4], [4], [2], [2], [2], [-1]]);
});

test('negative values, and a value equal to the largest kept one', () => {
  assert.deepEqual(kSmallestStreaming([-3, 0, -3, -7, 2, -3], 3), [[-3], [-3, 0], [-3, -3, 0], [-7, -3, -3], [-7, -3, -3], [-7, -3, -3]]);
});

test('changing one array of the result changes no other, and the stream is left unchanged', () => {
  const stream = [3, 1, 2];
  const result = kSmallestStreaming(stream, 2);
  result[0].push(99);
  assert.deepEqual(result.slice(1), [[1, 3], [1, 2]]);
  assert.deepEqual(stream, [3, 1, 2]);
});

test('400 random streams, checked against sorting every prefix', () => {
  for (let trial = 0; trial < 400; trial++) {
    const stream = Array.from({ length: randInt(0, 25) }, () => randInt(-20, 20));
    const k = randInt(1, 6);
    const expected = stream.map((_, i) => stream.slice(0, i + 1).sort((a, b) => a - b).slice(0, k));
    assert.deepEqual(kSmallestStreaming(stream, k), expected, JSON.stringify([stream, k]));
  }
});

Interview questions

Warm-up (fresher to mid-level): Python’s heappush raised TypeError: '<' not supported between instances of 'dict' and 'dict'. What happened, and what is the usual fix?

The heap entries were tuples such as (priority, job), with a dictionary as the job. Tuples compare element by element, and the first pair that differs decides, so two entries with equal priorities went on to compare their dictionaries, and dictionaries do not support <. The push that met the tie raised the error. The usual fix puts an element that can never tie between the priority and the payload: a running count from itertools.count(), or the item’s index. The entry becomes (priority, count, job). No two counts are equal, so the payloads are never compared, and equal priorities come out in the order they went in, which a heap does not promise otherwise. A dataclass with order=True and the payload field marked compare=False, as the heapq documentation shows, stops the payload comparison too, but it does not keep equal priorities in order.

Warm-up (fresher to mid-level): Why does heapify take O(n) time when n pushes take O(n log n) in the worst case?

heapify works from the bottom up. It starts at the last parent, lets each item sink below its smaller child until neither child is smaller, and moves on to the previous parent, ending at the root. An item can sink only as far as the levels below it, and most items have few: half the items of a heap are leaves and never move, a quarter sink at most one level, an eighth at most two, and so on, which adds up to at most about n moves. Pushes are different: each new item lands at the bottom and may climb to the root, about log₂ n levels in a heap of n items, and when items arrive in descending order every one of them does. In this lesson’s count on 100,000 numbers in descending order, the pushes made 1,468,946 comparisons and heapify 149,988.

Key takeaways

• Reach for a heap when you repeatedly need the smallest, largest or most urgent item while the items change. For one minimum, scan once; for everything in order, sort.
• Python’s heapq, Java’s PriorityQueue and Go’s container/heap give the smallest first; C++’s std::priority_queue gives the largest unless you pass std::greater<>; JavaScript has no heap, so keep a tested class.
• A heap is a list with one rule, every parent at most its children. Only the root is certain; the list is not sorted.
• No heap keeps equal items in arrival order: add the arrival number to the key. In Python it also keeps comparisons away from payloads that cannot be compared; in Java, compare with Integer.compare or comparingInt, never by subtracting.
• For the largest first, use Python 3.14’s max-heap functions or negated keys, Comparator.reverseOrder() in Java, the default in C++, and a flipped comparison in Go and JavaScript.
• Build from a full list in one step with heapify, heap.Init, C++’s range constructor or Java’s collection constructor: under two comparisons per item on 100,000 numbers, against up to 1,468,946 for pushes.
• The resale counter is the pattern in its plainest form: push on every arrival, pop on every request, and let a tie-breaking key decide equal priorities, for O(n log n) in place of the brute force’s O(n²).