Heap Fundamentals
A heap is a complete binary tree where every parent satisfies the heap property (min-heap: parent = children). The root is always the min (or max). Core operations: insert: O(log n). extract-min/max: O(log n). peek-min/max: O(1). Build heap from array: O(n) (not O(n log n) — counterintuitively). Python: heapq is a min-heap. For max-heap: negate all values. Key insight: heaps give you the minimum/maximum efficiently but are not sorted — use only when you need the extremes, not a full sort.
K-th Largest Element (LC 215) — Min-Heap of Size K
import heapq
def find_kth_largest(nums: list[int], k: int) -> int:
# Maintain a min-heap of size k
# The root is always the k-th largest
heap = []
for n in nums:
heapq.heappush(heap, n)
if len(heap) > k:
heapq.heappop(heap) # remove the smallest
return heap[0] # k-th largest = smallest in the heap of k largest
# O(n log k) time. Better than sorting (O(n log n)) when k << n.K Closest Points to Origin (LC 973)
def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
# Max-heap of size k (negate distances for max-heap with heapq)
heap = []
for x, y in points:
dist = x*x + y*y # no need for sqrt -- monotone
heapq.heappush(heap, (-dist, x, y))
if len(heap) > k:
heapq.heappop(heap)
return [[x, y] for _, x, y in heap]Merge K Sorted Lists (LC 23)
from heapq import heappush, heappop
def merge_k_lists(lists):
heap = []
for i, node in enumerate(lists):
if node:
heappush(heap, (node.val, i, node))
dummy = ListNode(0)
curr = dummy
while heap:
val, i, node = heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heappush(heap, (node.next.val, i, node.next))
return dummy.next
# O(n log k) where n = total nodes, k = number of listsTask Scheduler with Heap (LC 621 Alternative)
from collections import Counter
import heapq
from collections import deque
def least_interval(tasks: list[str], n: int) -> int:
freq = Counter(tasks)
# Max-heap (negate for Python min-heap)
heap = [-f for f in freq.values()]
heapq.heapify(heap)
time = 0
cooldown = deque() # (available_at, neg_freq)
while heap or cooldown:
time += 1
if heap:
freq_remaining = heapq.heappop(heap) + 1 # decrement count
if freq_remaining < 0: # still has remaining tasks
cooldown.append((time + n, freq_remaining))
if cooldown and cooldown[0][0] == time:
_, f = cooldown.popleft()
heapq.heappush(heap, f)
return timeFind Median from Data Stream (LC 295)
class MedianFinder:
def __init__(self):
self.small = [] # max-heap (negated): lower half
self.large = [] # min-heap: upper half
def addNum(self, num: int) -> None:
heapq.heappush(self.small, -num)
# Balance: largest in small self.large[0]):
heapq.heappush(self.large, -heapq.heappop(self.small))
# Size balance: small can have at most 1 more than large
if len(self.small) > len(self.large) + 1:
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2.0
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you find the k-th largest element using a heap?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Maintain a min-heap of size k. For each element, push it onto the heap. If the heap exceeds size k, pop the minimum. After processing all elements, the root of the heap is the k-th largest. Time: O(n log k), which is better than O(n log n) sorting when k << n. This is LC 215.”}},{“@type”:”Question”,”name”:”How does merging k sorted lists with a heap work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Push the first node from each list into a min-heap as (value, list_index, node). Each iteration: pop the minimum, add it to the result, then push the next node from that list (if any). Total time is O(n log k) where n is total nodes and k is number of lists. The heap size never exceeds k. This is LC 23.”}},{“@type”:”Question”,”name”:”How do you find the running median using two heaps?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Maintain a max-heap (small, lower half) and a min-heap (large, upper half). On each insert: push to small (max-heap), then rebalance so the largest of small <= smallest of large, and sizes differ by at most 1. Median is the root of the larger heap, or the average of both roots if equal sizes. All operations are O(log n). This is LC 295.”}},{“@type”:”Question”,”name”:”What is the difference between a min-heap and max-heap, and how do you implement max-heap in Python?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A min-heap always has the minimum at the root (heapq default in Python). A max-heap has the maximum at the root. To simulate a max-heap in Python, negate all values before pushing: heapq.heappush(heap, -val). To retrieve the max, negate the popped value: -heapq.heappop(heap). Python's heapq module only supports min-heaps natively.”}},{“@type”:”Question”,”name”:”What is the time complexity of building a heap from an array?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Building a heap from an array using heapify takes O(n) time, not O(n log n) as you might expect. This is because most nodes are near the leaves and require little work to sift down. The mathematical sum of work across all levels converges to O(n). In Python: heapq.heapify(array) builds a min-heap in-place in O(n).”}}]}
Meta coding interviews frequently ask heap-based problems like k-th largest and merge k sorted lists. Review patterns for Meta interview: heap and priority queue patterns.
Databricks interviews test heap-based streaming algorithms like running median and k-th largest. See problem patterns in Databricks interview: heap patterns for streaming data.
Atlassian coding rounds test heap-based scheduling problems. Review commonly asked patterns for Atlassian interview: priority queue and scheduling problems.