Nov 4, 2025

Heap

Overview

A heap maintains quick access to an extreme value while supporting insertion and removal in O(log n). Min-heaps expose the smallest item; max-heaps expose the largest.

Python’s heapq implements a min-heap over a list: heap[0] is the minimum, while heappush and heappop take O(log n). The portable max-heap technique used on interview platforms is to store numeric values as negatives and negate them again when reading or removing them. Python 3.14 also provides dedicated functions such as heappush_max and heappop_max, but negation remains compatible with older runtimes. heapq.heapify(values) transforms an existing list into a heap in place in O(n) time, which is faster than inserting all n items separately in O(n log n).

Java uses PriorityQueue, which follows natural ascending order by default. A numeric max-heap can use new PriorityQueue<>(Collections.reverseOrder()). When elements lack a natural order, or priority depends on one field, provide a comparator—for example, new PriorityQueue<int[]>((a, b) -> Integer.compare(a[0], b[0])) orders arrays by their first element.

Heaps are ideal when only the next best item matters: top-k selection, merging sorted sources, scheduling, streaming medians, and shortest-path frontiers. A size-k min-heap is often preferable to sorting all n values, reducing work to O(n log k).

Templates

Create a min-heap for the k largest items.
Push each candidate.
If heap size exceeds k, remove the smallest.
After processing everything, the heap contains the k largest candidates.
The root is the kth largest because it is the smallest retained item.

import java.util.PriorityQueue;

public class HeapTemplate {
	public static int kthLargest(int[] values, int k) {
		PriorityQueue<Integer> heap = new PriorityQueue<>();

		for (int value : values) {
			heap.offer(value);

			if (heap.size() > k) {
				heap.poll();
			}
		}

		return heap.peek();
	}
}

import heapq

def kth_largest(values: list[int], k: int) -> int:
	heap: list[int] = []

	for value in values:
		heapq.heappush(heap, value)

		if len(heap) > k:
			heapq.heappop(heap)

	return heap[0]

Problems

215. Kth Largest Element in an Array

Find the kth largest value without fully sorting the array. Keep only the k largest values in a min-heap; the root is the smallest retained value and therefore the kth largest overall.

import java.util.PriorityQueue;

class Solution {
	public int findKthLargest(int[] nums, int k) {
		PriorityQueue<Integer> minHeap = new PriorityQueue<>();

		for (int idx = 0; idx < nums.length; idx++) {
			int num = nums[idx];
			if (idx < k) {
				minHeap.offer(num);
			} else {
				minHeap.offer(num);
				minHeap.poll();
			}
		}

		return minHeap.peek();
	}
}

import heapq
from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        min_heap = []

        for idx, num in enumerate(nums):
            if idx < k:
                heapq.heappush(min_heap, num)
            else:
                heapq.heappushpop(min_heap, num)

        return min_heap[0]

347. Top K Frequent Elements

Count every value, then retain the k entries with the highest frequencies in a min-heap ordered by count. Limiting the heap to k gives O(n log k) time and avoids sorting all distinct values.

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
	public int[] topKFrequent(int[] nums, int k) {
		Map<Integer, Integer> numToFreq = new HashMap<>();

		for (int num : nums) {
			numToFreq.put(num, numToFreq.getOrDefault(num, 0) + 1);
		}

		PriorityQueue<int[]> minHeap = new PriorityQueue<>(
			(first, second) -> {
				int freqComparison = Integer.compare(first[0], second[0]);
				return freqComparison != 0
					? freqComparison
					: Integer.compare(first[1], second[1]);
			}
		);

		for (Map.Entry<Integer, Integer> entry : numToFreq.entrySet()) {
			int num = entry.getKey();
			int freq = entry.getValue();

			if (minHeap.size() < k) {
				minHeap.offer(new int[] {freq, num});
			} else {
				minHeap.offer(new int[] {freq, num});
				minHeap.poll();
			}
		}

		int[] res = new int[k];
		for (int index = 0; index < k; index++) {
			res[index] = minHeap.poll()[1];
		}
		return res;
	}
}

import heapq
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        num_to_freq = {}

        for num in nums:
            num_to_freq[num] = num_to_freq.get(num, 0) + 1

        min_heap = []
        for num, freq in num_to_freq.items():
            if len(min_heap) < k:
                heapq.heappush(min_heap, (freq, num))
            else:
                heapq.heappushpop(min_heap, (freq, num))

        return [n for _, n in min_heap]

23. Merge k Sorted Lists

Merge k sorted linked lists by placing each non-empty head in a min-heap. Repeatedly append the smallest node and add its successor. If there are N total nodes, the runtime is O(N log k).

import java.util.PriorityQueue;

class Solution {
	public ListNode mergeKLists(ListNode[] lists) {
		PriorityQueue<ListNode> heap = new PriorityQueue<>(
			(first, second) -> Integer.compare(first.val, second.val)
		);
		ListNode dummy = new ListNode();
		ListNode curr = dummy;

		for (ListNode l : lists) {
			if (l != null) {
				heap.offer(l);
			}
		}

		while (!heap.isEmpty()) {
			ListNode node = heap.poll();
			curr.next = node;
			node = node.next;
			curr = curr.next;

			if (node != null) {
				heap.offer(node);
			}
		}

		return dummy.next;
	}
}

import heapq
from typing import List, Optional

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        ListNode.__lt__ = lambda self, other: self.val < other.val

        heap = []
        dummy = curr = ListNode()

        for l in lists:
            if l:
                heap.append(l)

        heapq.heapify(heap)

        while heap:
            node = heapq.heappop(heap)
            curr.next = node
            node = node.next
            curr = curr.next
            if node:
                heapq.heappush(heap, node)

        return dummy.next

295. Find Median from Data Stream

Maintain the smaller half in max-heap small and the larger half in min-heap large. Always keep the extra element in small: when their sizes match, move the smallest candidate from large into small; otherwise move the largest candidate from small into large.

import java.util.Collections;
import java.util.PriorityQueue;

class MedianFinder {
	private final PriorityQueue<Integer> small;
	private final PriorityQueue<Integer> large;

	public MedianFinder() {
		small = new PriorityQueue<>(Collections.reverseOrder());
		large = new PriorityQueue<>();
	}

	public void addNum(int num) {
		if (small.size() == large.size()) {
			large.offer(num);
			int val = large.poll();
			small.offer(val);
		} else {
			small.offer(num);
			int val = small.poll();
			large.offer(val);
		}
	}

	public double findMedian() {
		if (small.size() > large.size()) {
			return small.peek();
		}

		return ((long) large.peek() + small.peek()) / 2.0;
	}
}

import heapq

class MedianFinder:

    def __init__(self):
        # Always store the extra one in self.small
        self.small = [] # stores the smaller half as MAX heap
        self.large = [] # stores the larger half as MIN heap

    def addNum(self, num: int) -> None:
        if len(self.small) == len(self.large):
            val = heapq.heappushpop(self.large, num)
            heapq.heappush(self.small, -val)
        else:
            val = heapq.heappushpop(self.small, -num)
            heapq.heappush(self.large, -val)

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -1 * self.small[0]
        else:
            return 0.5*(self.large[0]-self.small[0])

621. Task Scheduler

Schedule tasks with a cooldown between equal labels. Let maxFreq be the highest task frequency and maxfCount the number of tasks with that frequency. Those tasks require at least (n + 1) * (maxFreq - 1) + maxfCount positions, but the result cannot be shorter than the total number of tasks.

import java.util.HashMap;
import java.util.Map;

class Solution {
	public int leastInterval(char[] tasks, int n) {
		Map<Character, Integer> letToFreq = new HashMap<>();
		int maxFreq = 0;
		int N = tasks.length;

		for (char letter : tasks) {
			letToFreq.put(
				letter,
				letToFreq.getOrDefault(letter, 0) + 1
			);
			maxFreq = Math.max(maxFreq, letToFreq.get(letter));
		}

		int maxfCount = 0;
		for (int frequency : letToFreq.values()) {
			if (frequency == maxFreq) {
				maxfCount++;
			}
		}

		// Calculate the total time needed for all maxFreq letters
		int time = (1 + n) * (maxFreq - 1) + maxfCount;

		// The calculated time may not be enough to hold all tasks
		// that's just the min time needed to hold maxFreq elements
		return Math.max(N, time);
	}
}

from collections import defaultdict
from typing import List

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        let_to_freq = defaultdict(int)
        max_freq = 0
        N = len(tasks)

        for letter in tasks:
            let_to_freq[letter] += 1
            max_freq = max(max_freq, let_to_freq[letter])

        maxf_count = 0
        for f in let_to_freq.values():
            if f == max_freq:
                maxf_count += 1

        # Calculate the total time needed for all max_freq letters
        time = (1 + n) * (max_freq - 1) + maxf_count

        # The calculated time may not be enough to hold all tasks
        # that's just the min time needed to hold max_freq element
        return max(N, time)