← All topics

Heaps / Priority Queues

For 'give me the smallest/largest so far, repeatedly' problems, a heap keeps the current best at the top in O(log n) per update -- much cheaper than re-sorting everything each time a new element arrives.

Easy reps

1046. Last Stone Weight

Repeatedly smash the two heaviest stones together (the lighter's weight is removed, the heavier is reduced by that amount) until at most one stone remains. Return its weight, or 0.

import heapq

def last_stone_weight(stones):
    heap = [-s for s in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        y = -heapq.heappop(heap)
        x = -heapq.heappop(heap)
        if y != x:
            heapq.heappush(heap, -(y - x))
    return -heap[0] if heap else 0

Python's heapq is a min-heap, so negating every value turns 'pop the two largest' into 'pop the two smallest' -- a common trick instead of implementing a separate max-heap.

703. Kth Largest Element in a Stream

Design a class that, given a stream of integers arriving one at a time, always reports the kth largest element seen so far.

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)

    def add(self, val):
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

Keep a min-heap of exactly size k -- the smallest element in that heap is, by construction, the kth largest overall. Every insert that overflows the heap evicts the new minimum, which is the only element too small to matter.

Level up

Same topic, no training wheels. Solve these on your own before you check the editorial.