Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Binary heaps: select the next priority with a tie rule

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A binary min-heap stores a complete tree in an array with each parent no greater than its children. The smallest key is at index zero. Insertion and removal repair the heap in O(log n) time; inspecting the smallest item is O(1). A heap does not keep every item sorted, and searching for a named item is O(n) without another index. For equal priorities, include an explicit sequence number when first-in tie behavior matters. Python's heapq compares tuple fields in order, so a unique counter also avoids comparing non-orderable task payloads.

Operational case

A repair scheduler receives jobs J-47 at priority 2, J-52 at priority 1, and J-61 at priority 1. The two urgent jobs should run in arrival order. Their tuples include a sequence counter, so J-52 leaves before J-61 even though both have priority 1. The heap is an in-memory selection structure, not a durable job runner. If a worker fails after popping a job, the system needs an independent claim and retry record to avoid losing work.

Working Python program

python
import heapq

repair_heap = []
for arrival, (priority, job_id) in enumerate(((2, "J-47"), (1, "J-52"), (1, "J-61"))):
    heapq.heappush(repair_heap, (priority, arrival, job_id))
print(heapq.heappop(repair_heap)[2])
print(heapq.heappop(repair_heap)[2])

Output

Output
J-52
J-61

Time, space, and tradeoff

Building by repeated pushes costs O(n log n); heapify can build an existing batch in O(n). Each pop costs O(log n), and the heap retains O(n) entries. For mutable priorities, blindly pushing a changed job creates duplicates; use a versioned entry and skip stale records on pop, or maintain an indexed heap. The ordering tuple is part of correctness, not an incidental detail. Negative priorities are allowed if the contract defines them consistently.

Common Mistakes

  • Do not expect a heap's full array to be sorted.
  • Do not rely on task payload comparison to break priority ties.
  • Do not equate popping an in-memory heap with durable execution.

Connected lessons

Indexed binary heaps: decrease a queued priority continues this operation with mutation checks.

Two heaps: maintain an exact running median adds a related operation contract.

Expiry heaps: invalidate stale TTL records on replacement adds a related lifecycle choice.

Pairing heaps: meld roots and pair children on removal adds another queue operation contract.

Binomial heaps: carry equal-degree trees during merge adds another queue operation contract.

Tournament trees: merge sorted runs through one winner path adds a related structure with a different operation boundary.

Min-max heaps: remove either end of one dispatch priority array examines a related structure with a different operation boundary.

data structures
trees-and-heaps
Storage details