Priority queues
Binary search needs an array that is sorted once and then left alone. In the problems of this lesson the values keep changing: new ones arrive, old ones are used up, and after every change we need the largest value that is left. Here is a game that works this way.
You get the weights of some stones. On each turn, the two heaviest stones are smashed together. If they weigh the same, both are destroyed. Otherwise the lighter one is destroyed and the heavier one loses that much weight.
When at most one stone is left, return its weight, or 0 if none is left.
Constraints
-
stones.length -
stones[i]
Sample 1 · Input
stones = [2,7,4,1,8,1]
Output
1
Sample 2 · Input
stones = [1]
Output
1
Here is the first sample, one turn per line:
stones the two heaviest what the smash leaves2 7 4 1 8 1 8 and 7 a stone of weight 12 4 1 1 1 4 and 2 a stone of weight 21 1 1 2 2 and 1 a stone of weight 11 1 1 1 and 1 nothing1One stone of weight 1 is left, so the answer is 1. The stone that a smash puts back can land anywhere among the others: the 1 from the first turn is one of the lightest stones, and the 2 from the second turn is the heaviest. So sorting the stones once at the start is not enough.
The direct method reads the whole list on every turn to find the two heaviest stones. Every turn destroys at least one stone, so stones last at most turns, and the turns read at most stones, about . For the 30 stones allowed here that is 464 reads, which the judge accepts. A contest problem built on the same loop can have 200,000 values, and then it is about
which is 200 seconds of work at the rule-of-thumb rate of simple operations a second.
The game does only three things with its stones: it adds one, it reads the heaviest, and it removes the heaviest.
Definition
A priority queue is a collection with three operations: add a value, read the value with the highest priority, and remove that value.
In a max-priority queue the largest value has the highest priority, and in a min-priority queue the smallest.
A plain list, sorted or not, already has these three operations, but not all of them are fast:
| Stored as | Add | Read the largest | Remove the largest |
|---|---|---|---|
| Unsorted list | |||
| Sorted list | |||
| Binary heap |
A sorted list has its largest value at the end, but a new value has to be inserted at its sorted place, which moves every value after it one position along, up to of them. Binary search finds that place in steps, but the values after it still have to move.
A binary heap sits between the two. It keeps its list only partly ordered: ordered enough that the value with the highest priority is always at the front, and loosely enough that an add or a remove repairs the order in about steps, at most 17 for 200,000 values. Python's and C++'s priority queues are both binary heaps, which is why "heap" and "priority queue" are often used as names for the same thing.
The priority queue in the standard library
Python's priority queue is the heapq module, a set of functions that work on an ordinary list. heappush(h, x) adds x to the list h, heappop(h) removes the smallest value and returns it, and h[0] is the smallest value. heapq is a min-priority queue: the smallest value comes out first.
Here is a short run of calls, with the result of each in a comment:
h = []
for x in [5, 2, 8, 3]:
heappush(h, x)
print(h[0]) # 2, the smallest of 5, 2, 8, 3
print(heappop(h)) # 2 again, and now it is removed
print(heappop(h)) # 3
heappush(h, 1)
print(h[0]) # 1
print(h) # [1, 8, 5]The last line prints the list itself. Its front is the smallest value, but the rest is not sorted, as 8 comes before 5. A later part shows the order heapq keeps. To get the largest value first, as the stones need, we store every value negated: we push -x and negate what comes out. Negation reverses the order of two numbers (8 is larger than 7, and is smaller than ), so the smallest negated value belongs to the largest original.
With a priority queue the game is a short loop. Each turn pops the two heaviest stones, and pushes their difference when they are not equal.
def last_stone_weight(stones):
heap = [-s for s in stones]
heapify(heap)
while len(heap) > 1:
y = -heappop(heap)
x = -heappop(heap)
if y != x:
heappush(heap, -(y - x))
return -heap[0] if heap else 0
print(last_stone_weight([2, 7, 4, 1, 8, 1]))
print(last_stone_weight([1]))Prints 1 and 1, the two samples' answers.
heapify(heap) turns a list in any order into a heap with one call. The last line returns 0 when the last two stones destroyed each other and the list is empty.
A game with stones has at most turns, and each turn makes at most three operations on the queue, two removals and one add. Each operation takes steps, so the game takes . For 200,000 stones the loop makes at most
about a two-thousandth of the work of reading the whole list on every turn.
Deeper read: max-heap functions in Python 3.14
Python 3.14 added largest-first versions of the heapq functions, named with a _max suffix: heappush_max, heappop_max, heapify_max and so on. A judge may run an older Python, and negation works on every version, so the listings in this lesson negate. Negation works only on numbers, so when the items are strings or other objects, give each a numeric priority and push the pair (-priority, item). If two priorities can be equal, Python then compares the items, so put a counter between them: (-priority, count, item).
The shape and order of a heap
To see why an add or a remove takes about steps, we look at how a heap arranges its values. We draw the smallest-first kind, a min-heap. A largest-first max-heap is the same with every comparison reversed.
A heap arranges its values as a tree. Each value sits in a node. The top node is the root, the nodes directly below a node are its children, and it is their parent. In a binary heap a node has at most two children.
Two rules make the tree a heap. The shape rule: the levels fill from the top down and each level from left to right, so only the last level can be partly filled. Such a tree is called complete. The order rule: every parent is less than or equal to each of its children.
Here 3 is at most 8 and 5, 8 is at most 9 and 12, and 5 is at most 7. That puts the smallest value at the root, because on the way up from any node, from child to parent, the values never get larger.
The order rule is much weaker than sorted order. It does not order 8 and 5, which sit side by side, and 7 on the bottom level is smaller than 8 on the level above.
The number of levels sets the cost of the operations in the next part. The levels hold 1, 2, 4, 8 values and so on, so full levels hold values. Seventeen levels hold at most values, so a heap of 200,000 values has 18 levels. In general, a heap of values has levels.
Store the tree in a list
The tree is only a picture. What is stored is a plain list with no links: the values level by level, each level from left to right. Our tree is the list [3, 8, 5, 9, 12, 7]. A complete tree has no gaps, so the positions of a node's relatives follow from its own index :
For example, 8 is at index 1, so its children are at indexes 3 and 4, which hold 9 and 12.
The formula holds because the children are listed in the same order as their parents. If has a child, every node before it has two, because the levels fill from left to right, and those children fill the indexes from 1 to , so the children of come next, at and . The parent formula reverses this: and are both .
h. Each parent's edges in the tree become arcs of the same color in the list.The list [1, 8, 5] printed by the short run of calls is arranged this way: a root 1 with the children 8 and 5.
The list is not sorted, and only index 0 has a fixed meaning. A heap cannot say quickly whether it holds a given value, or which value is at its other end: the largest in a min-heap, the smallest in a max-heap. Either question can mean reading the whole list.
Push and pop: sift up and sift down
Adding a value to a heap is called a push, and removing its smallest value a pop. Both first make the shape of the tree right and then repair the order along one path.
A push puts the new value in the first free slot, which is the end of the list. The tree is still complete, but the new value may be smaller than its parent, so it sifts up: while it is smaller than its parent, the two swap. Push 2 onto [3, 8, 5, 9, 12, 7]. It lands at index 6, under the 5, and swaps with it. Its parent is now the root, 3, and they swap as well, which makes 2 the new root.
A swap does not break the order elsewhere: the value that moves up is smaller than the parent it replaces, and the parent that moves down was already at most every value below it. When 2 moved above 5, it also became the parent of 7, and .
A pop removes the root, and the simplest way to fill the hole is to move the last value of the list into it, which keeps the tree complete. That value came from the bottom of the tree and is probably too large for the root, so it sifts down: we compare it with its two children. If it is the smallest of the three, it stays. Otherwise it swaps with the smaller child, and the comparison repeats one level down.
It has to be the smaller child, because the child that moves up becomes the parent of the other one and must be at most it. Pop from [3, 8, 5, 9, 12, 7]: 3 is returned and 7 moves to the root. Its smaller child is 5, and they swap. Now 7 has no children, and the heap is [5, 8, 7, 9, 12].
The widget starts from the same heap. Push 2 and step through its two swaps, push 10, which stays where it lands, and then pop.
Each swap moves a value by one level, so a push or a pop makes at most swaps: 2 for our six values and 17 for 200,000. These are the steps of the table in the first part.
Build a heap from a whole list
The stones program has all of its values at the start. Pushing them one at a time costs up to 17 swaps each for 200,000 values. Building the heap from the bottom up is quicker.
The values in the second half of the list have no children, because a first child at would be past the end, so each is already a heap of one value. From the last parent back to the root, we sift each value down. When we reach a value, the trees under its children are heaps already, because their indexes are larger, so sifting it down makes the tree under it a heap too.
In [5, 1, 4, 2, 3] the parents are at indexes 1 and 0, since index 4 has its parent at 1. The 1 at index 1 is already at most its children 2 and 3, so it stays. Then the 5 at the root swaps with its smaller child, 1, and then with its new smaller child, 2, which gives [1, 2, 4, 5, 3].
This takes fewer than swaps in all, because most nodes are near the bottom and have few levels to sift down. It is what heapify(h) does.
Deeper read: counting the swaps of the build
A node sifts down at most as many levels as lie below it, so the figure's labels add up to the most swaps the build can make, . Counted another way, each node adds 1 for every level it can move: the 7 nodes that can move at least one level add 7, the 3 that can move two add 3 more, and the root adds 1 for its third, so again .
In a heap of values, at most nodes have a child and can move one level, at most can move two, and so on. So the build takes time: the swaps number fewer than
Keep only the k largest values
In the stones game the heap held every value. In the next problem it holds only the few values that can still matter.
Write a class KthLargest for a stream of test scores. The constructor receives and a list nums of the scores so far. Each call add(val) adds one score and returns the -th largest of all the scores so far, counting equal scores separately.
In a sample, the first line lists the calls and the second their arguments. The output lists what each call returns, with null for the constructor.
Constraints
-
nums.length -
nums.length -
nums[i],val - At most calls to
add
Sample 1 · Input
["KthLargest","add","add","add","add","add"] [[3,[4,5,8,2]],[3],[5],[10],[9],[4]]
Output
[null,4,5,5,8,8]
Sample 2 · Input
["KthLargest","add","add","add","add"] [[4,[7,7,7,7,8,3]],[2],[10],[9],[9]]
Output
[null,7,7,7,8]
In the first sample is 3 and the scores start as 4, 5, 8 and 2. From the largest down they are 8, 5, 4, 2, so the third largest is 4.
Sorting all the scores from scratch after every call is too slow. With the largest input, each of the calls sorts at least 10,000 scores, which takes about comparisons. That is more than comparisons in all, or 13 seconds.
Think of a leaderboard that shows the best scores so far. Once it holds scores, the -th largest score is the lowest score on the board. A new score gets on the board only if it is above that lowest score, which then drops off. A score that drops off, or never gets on, cannot become the answer later: at least scores as large as it are already on the board, and scores are only ever added. The program has to keep only the board.
So the board has to read its lowest score, remove it, and add a score. That is a min-priority queue of at most values. We use a min-heap although we want large values, because the value we read and remove is the smallest one on the board.
The first sample on a board of three
In the first sample the constructor leaves 8, 5 and 4 on the board, and the 2 does not get on. Each of the five calls then compares its score with the lowest on the board:
| Score added | What happens | Board afterwards | add returns |
|---|---|---|---|
| 3 | not above 4: skipped | 8, 5, 4 | 4 |
| 5 | above 4: replaces it | 8, 5, 5 | 5 |
| 10 | above 5: replaces one 5 | 10, 8, 5 | 5 |
| 9 | above 5: replaces it | 10, 9, 8 | 8 |
| 4 | not above 8: skipped | 10, 9, 8 | 8 |
The moves on another stream
In this widget you make the moves on another stream, 6, 2, 9, 1, 8, 7, again with a board of three. The root is the board's lowest score.
The board in code
The code makes these moves with two calls. It pushes every new score, and if the heap then holds scores, it pops the smallest. If the new score was above the lowest on the board, the pop removes that lowest score. If it was not, the pop removes the new score itself.
class KthLargest:
def __init__(self, k, nums):
self.k = k
self.heap = []
for x in nums:
self.add(x)
def add(self, val):
heappush(self.heap, val)
if len(self.heap) > self.k:
heappop(self.heap)
return self.heap[0]
s = KthLargest(3, [4, 5, 8, 2])
print([s.add(v) for v in [3, 5, 10, 9, 4]])Prints [4, 5, 5, 8, 8], the first sample's answers.
The heap holds at most scores, so scores take time and memory. The largest input has 20,000 scores, in nums and calls. A heap of at most 10,002 scores has 14 levels, so a push or a pop makes at most 13 swaps, and each score costs one push and at most one pop: at most swaps in all.
Worked example
The heap's list after each score
The trace runs the listing on the first sample and shows the heap's list after each score. The other inputs are a stream with two equal scores, which both stay on the board, and a board of one.
After 4, the heap keeps the largest value seen. Its root is the smallest value kept.
- capacity
- 3
Change the example input
Current result: [10,9,8]
Merge sorted lists with one entry per list
The heap of the last section held the best values of one stream. In this section is a number of sorted lists, and the heap holds one value from each list.
You get lists, each sorted in ascending order. Merge them into one sorted list.
On LeetCode the lists are linked lists, which the Linked lists lesson covers. The listing below uses arrays, and the method is the same.
Constraints
- each list's length
- At most values in all
- each value
Sample 1 · Input
lists = [[1,4,5],[1,3,4],[2,6]]
Output
[1,1,2,3,4,4,5,6]
Sample 2 · Input
lists = []
Output
[]
Sample 3 · Input
lists = [[]]
Output
[]
We take values off the fronts of the lists. Each list is sorted, so the smallest value left in it is at its front, and the smallest value left anywhere is one of the fronts.
We could compare all fronts each time we take a value, which is up to comparisons for values. With values in lists that is comparisons, the whole budget of a second.
We keep removing the smallest front and adding one new front, which is the work of a min-priority queue. It holds one entry per list: the front value, the number of the list, and the position of the value in that list. We pop the smallest entry, append its value to the output, and push the next value of the same list if there is one. Here are the first four pops on the first sample, with each entry written as (value, list):
entries, smallest first popped output so far(1, 0) (1, 1) (2, 2) (1, 0) 1(1, 1) (2, 2) (4, 0) (1, 1) 1 1(2, 2) (3, 1) (4, 0) (2, 2) 1 1 2(3, 1) (4, 0) (6, 2) (3, 1) 1 1 2 3def merge_k_lists(lists):
heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
heapify(heap)
out = []
while heap:
value, i, j = heappop(heap)
out.append(value)
if j + 1 < len(lists[i]):
heappush(heap, (lists[i][j + 1], i, j + 1))
return out
print(merge_k_lists([[1, 4, 5], [1, 3, 4], [2, 6]]))
print(merge_k_lists([]))
print(merge_k_lists([[]]))Prints [1, 1, 2, 3, 4, 4, 5, 6], [] and [], the three samples' answers.
Python details
The standard library has this merge built in: heapq.merge(*lists) gives the merged values one at a time.
Python compares tuples field by field. Two entries with the same value are told apart by their list numbers, which always differ, so Python does not compare their third fields. That matters on LeetCode, where the third field would be a node of a linked list: Python cannot compare two nodes, and a heap of (value, node) pairs stops with a TypeError as soon as two values tie.
Each of the values is pushed once and popped once, on a heap of at most entries, so the merge takes time. In the case above that is at most swaps. Joining the lists and sorting everything takes , which is just as fast for these limits. The heap is ahead when a few long lists are merged, because is then much smaller than .
A running median with two heaps
One heap gives quick access to one end of a collection, its smallest value or its largest. The last problem asks for the value in the middle, and it takes two heaps.
Write a class MedianFinder with two methods. addNum(num) adds a number. findMedian() returns the median of the numbers added so far: the middle value when they are put in order, or the average of the two middle values when their count is even. Answers within of the true median are accepted.
Constraints
-
num findMedianis called only after at least one number was added- At most calls in all
Sample · Input
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] [[],[1],[2],[],[3],[]]
Output
[null,null,null,1.5,null,2.0]
A sorted list would keep the median in the middle, but inserting a number moves every larger number one position along. If almost 50,000 numbers arrive in decreasing order, each one goes to the front and moves all the others, which is about moves in all.
The median needs only the one or two values in the middle. So we split the numbers into a lower half and an upper half. The middle is where they meet, at the largest value of the lower half and the smallest value of the upper half. We keep the lower half in a max-heap and the upper half in a min-heap, so that each of these values sits at the top of its heap. Two rules hold after every addNum:
- Order: every value in the lower half is at most every value in the upper half.
- Size: the lower half holds as many values as the upper half, or one more.
When the sizes are equal, the median is the average of the two tops. Otherwise it is the top of the lower half.
addNum does not know in advance which half the new number belongs to, so it takes three steps:
- Push the number into the lower half.
- Move the largest value of the lower half to the upper half. If that is the new number, the lower half is left with its older values, which were already at most every value in the upper half and are at most the new number too. If an older value moves instead, the new number stays behind, and it is at most that older value, which was at most every value in the upper half. Either way the order rule holds.
- If the upper half now holds more values than the lower half, move its smallest value back. Steps 1 and 2 leave the lower half with as many values as the upper half or one fewer, so one move is enough to restore the size rule. The order rule still holds, because the value that moves back is at least every value in the lower half and at most every value left in the upper half.
The two halves on a stream of four numbers
Here are the halves after each number of the stream 5, 15, 1, 3:
| Number added | Lower half | Upper half | Median |
|---|---|---|---|
| 5 | 5 | empty | 5 |
| 15 | 5 | 15 | |
| 1 | 1, 5 | 15 | 5 |
| 3 | 1, 3 | 5, 15 |
When 1 arrives, step 2 moves the 5 up and step 3 moves it back, because the upper half would otherwise hold two values and the lower half one.
The two heaps in code
class MedianFinder:
def __init__(self):
self.low = [] # lower half, stored negated as a max-heap
self.high = [] # upper half, a min-heap
def addNum(self, num):
heappush(self.low, -num)
heappush(self.high, -heappop(self.low))
if len(self.high) > len(self.low):
heappush(self.low, -heappop(self.high))
def findMedian(self):
if len(self.low) > len(self.high):
return -self.low[0]
return (-self.low[0] + self.high[0]) / 2
m = MedianFinder()
m.addNum(1)
m.addNum(2)
print(m.findMedian())
m.addNum(3)
print(m.findMedian())Prints 1.5 and 2, the sample's two medians.
Each addNum makes at most five heap operations and findMedian reads the two tops, so a call takes time. With 50,000 numbers, each heap holds at most about 25,000 values and an operation makes at most 14 swaps, which is swaps in all.
Common heap mistakes
Reading a heap's list as if it were sorted (Python).
- Where it breaks
[1, 5, 2, 6, 7, 3]is a valid heap. Its last value,h[-1], is 3, while its largest value is 7.- The fix
- Only
h[0]has a fixed meaning. To read the values in order, pop them one at a time.
Keeping the largest values in a max-heap.
- Where it breaks
- On the first Kth Largest sample, a max-heap that pops its top whenever it holds four scores throws away the largest score each time. If
addreturns its top, the five calls give 4, 4, 4, 4, 4 instead of 4, 5, 5, 8, 8. - The fix
- Keep the largest values in a min-heap, so that the value popped is the smallest of them.
Choosing the half for a new number by size alone.
- Where it breaks
- For the stream 5, 1, 15, pushing each number into the half that holds fewer values, the lower half on a tie, puts 5 and 15 in the lower half and 1 in the upper half, and the reported median is 15 instead of 5.
- The fix
- Send every number through the lower half first, as
addNumdoes.
Recall In the min-heap list `[3, 8, 5, 9, 12, 7]`, which positions can hold the second smallest value, and why?
Index 1 or index 2, the children of the root. Any value further down has a parent that is not the root, and both that parent and the root are at most it, so it is third smallest at best. Here indexes 1 and 2 hold 8 and 5, and the second smallest value is 5.
Further reading
- USACO Guide, SilverPriority Queues(opens in a new tab)
Python's
heapqand C++'spriority_queueside by side, then Room Allocation from CSES solved with a min-heap of departure times, and a graded problem list. - Python documentationheapq: Heap queue algorithm(opens in a new tab)
Every function, the max-heap variants added in 3.14,
merge,nlargestandnsmallest, and implementation notes on breaking ties with a counter and marking entries as removed. - MIT 6.006 lecture notes, Spring 2020Lecture 8: Binary Heaps(opens in a new tab)
The priority queue interface compared across an array, a sorted array and a balanced tree, the array as an implicit complete tree, heap sort in place and the linear-time build.
- Antti Laaksonen (PDF)Competitive Programmer’s Handbook, Section 4.5: Other structures(opens in a new tab)
Page 43 covers C++'s
priority_queueas a max-heap, thegreater<int>form for a min-heap, and why it has smaller constant factors than an ordered set. - OI Wiki, in Chinese二叉堆 (Binary heap)(opens in a new tab)
Insertion and deletion with sift-up and sift-down, both ways of building a heap with their costs, and the two-heap technique used for the running median.
- Pat MorinOpen Data Structures, Chapter 10: Heaps(opens in a new tab)
Section 10.1 stores a complete binary tree in an array and adds or removes a value by swapping along one path; Section 11.1.3, in the next chapter, builds the heap from the bottom up for heap-sort and counts its work. Parts of this page adapt the text of these sections, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code.