Skip to main content

Heaps

Keep the smallest (or largest) thing within reach and stop caring about the order of everything else. A heap hands you its top in O(1) and absorbs a push or a pop in O(log n), which is exactly the trade a problem wants when it keeps asking "what is the best one right now?" while the set underneath it keeps changing.

987652min stays on toppeek in O(1)no order down here4push 4O(log n) to fix
The min sits on top and stays reachable in O(1); everything under it can be in any order. Pushing a new value only costs O(log n) to walk it back into place.

New to the structure itself? The Heaps & Priority Queues primer walks through the heap property, sift up and sift down, and heapq in practice.

Top K​

Only the best k ever matter. Keep a heap of at most k candidates and let everything else fall off the end, so the work scales with k instead of with the whole input.

1337. The K Weakest Rows in a Matrix​

1337

The K Weakest Rows in a Matrix

LeetCode
Easy

Count Soldiers, Keep K with a Heap

FIG. 1337 THE K WEAKEST ROWS IN A MATRIX● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left_rev(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] > target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] > target:
lo = mid + 1
else:
hi = mid
return lo
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
max_heap = []
for row in range(len(mat)):
soldiers = self.bisect_left_rev(mat[row], 0)
# Put the strength/index pairs into a priority queue.
entry = (-soldiers, -row)
heapq.heappush(max_heap, entry)
if len(max_heap) > k:
heapq.heappop(max_heap)
ans = []
# Pull out and return the indexes of the smallest k entries.
# Don't forget to convert them back to positive numbers!
while max_heap:
ans.append(-heapq.heappop(max_heap)[1])
return ans[::-1] # Reverse, as the indexes are around the wrong way.
top ↑

Earliest to Finish​

Sort the events by start, then keep a min-heap of the moments things end. The heap's top is always the next resource to free up, so each new arrival either reuses it or opens a new one.

These problems live with the intervals, on Greedy & Heap Sweeps, where the loop is worked as admit / expire / serve: 1353 Maximum Number of Events, 253 Meeting Rooms II, 1094 Car Pooling.

Window Extremes​

A sliding window needs its max (or min) at every step. Push each element as it enters and lazily discard the top only once it has slid out of the window - stale entries buried deeper in the heap can wait.

239. Sliding Window Maximum​

239

Sliding Window Maximum

LeetCode
Hard

Max Heap

FIG. 239 SLIDING WINDOW MAXIMUM● INTERACTIVE
visualization loads as you reach it
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
left = right = 0
heap = [] # Max heap
result = []
 
while right < n:
# Expansion: Add new elements to the heap
while right < n and right - left < k:
heapq.heappush_max(heap, (nums[right], right))
right += 1
# Logic: Append the current maximum to ans
result.append(heap[0][0])
left += 1
# Shrinking: Ensure the top of the heap is within the current window
while heap and heap[0][1] < left:
heapq.heappop_max(heap)
return result
top ↑

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit​

1438

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

LeetCode
Medium

Two Heaps (window min/max)

FIG. 1438 LONGEST CONTINUOUS SUBARRAY WITH ABSOLUTE DIFF LESS THAN OR EQUAL TO LIMIT● INTERACTIVE
visualization loads as you reach it
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
n = len(nums)
left = right = 0
maxi = 0
min_heap = []
max_heap = []
isValid = lambda: abs(min_heap[0][0] - max_heap[0][0]) <= limit
while right < n:
heapq.heappush(min_heap, (nums[right], right))
heapq.heappush_max(max_heap, (nums[right], right))
right += 1
while left < right and not isValid():
while min_heap[0][1] <= left:
heapq.heappop(min_heap)
while max_heap[0][1] <= left:
heapq.heappop_max(max_heap)
left += 1
maxi = max(maxi, right - left)
return maxi
top ↑
On this page