Description

A heap is a complete binary tree that always keeps the smallest (min-heap) or largest (max-heap) element at the root.
?

Reach for when

You repeatedly need the smallest/largest element while the data keeps changing: top-k / kth, merge k sorted, schedule by priority, or (two heaps) running median.

Runtime

peek O(1)
push O(log n)
pop O(log n)
build-heap (heapify) O(n)

Visualization

Pseudocode

push(x):
	add x at the end of the array
	bubble up: while x < its parent, swap with parent

pop():                 # remove the root (the min)
	swap root with the last element, remove the last
	bubble down: while root > its smaller child, swap with it
	return the removed root

Code

import heapq

heap = []
heapq.heappush(heap, x)          # push        O(log n)
smallest = heapq.heappop(heap)   # pop min     O(log n)
smallest = heap[0]               # peek        O(1)
heapq.heapify(nums)              # build       O(n)

# heapq is MIN-only → for a max-heap, push negatives
heapq.heappush(heap, -x)
largest = -heapq.heappop(heap)

# k largest → a MIN-heap of size k (evict the smallest)
def k_largest(nums, k):
	h = []
	for x in nums:
		heapq.heappush(h, x)
		if len(h) > k:
			heapq.heappop(h)     # drop the smallest, keep the k biggest
	return h