Heap vs Sorted List — When to Use Each, with Complexity and Worked Examples

A heap knows one thing well: which element is smallest (or largest). A sorted list knows everything, at a cost. The trade-off is what you pay per insertion — and which questions you can afford to ask on lookup. This post is the tie-breaker: when the extremum is all you need, when full order earns its keep, and where each falls apart.

The verdict

Binary heap. O(1) peek at the extremum, O(log n) push and pop, O(n) build from an array. Doesn't maintain full sorted order — only the root is guaranteed to be min (or max).

Sorted list (Python's sortedcontainers.SortedList, Java's TreeSet/TreeMap, C++'s std::set/std::map). O(log n) for all ops: insert, delete, find, floor, ceiling, k-th element. Full ordering available on demand.

Ask what your problem needs to retrieve. If it's "just the minimum, over and over as things flow in", heap wins. If it's "the closest element to x", "the k-th smallest for arbitrary k", or "everything in [lo, hi]", sorted list wins.

When to reach for a heap

• Streaming top-k. Maintain a k-sized heap; each push and pop-if-too-large is O(log k). Total O(n log k) — better than sorting the whole stream.
• Priority queue. Dijkstra, A*, task scheduling by priority. Standard-library heaps are optimised for exactly this.
• Median from a data stream. Two heaps — a max-heap for the lower half, a min-heap for the upper half — give O(log n) insert and O(1) median.
• Repeated "take the smallest/largest and process it" loops. Each iteration is O(log n), total O(n log n).

Canonical problems: LC 215 (Kth Largest), LC 295 (Find Median from Data Stream), LC 703 (Kth Largest in a Stream), LC 973 (K Closest Points to Origin).

When to reach for a sorted list

• Sliding-window median or k-th smallest where the window contents change arbitrarily. SortedList.add / .remove / [i] are all O(log n). Two-heaps also work for median, but they don't generalise — sorted list does.
• Nearest-neighbour queries on a moving set of values (LC 220 Contains Duplicate III). Sorted list gives predecessor and successor in O(log n) via bisect_left.
• Range queries — count or iterate elements in [lo, hi]. Heap can't do this; sorted list gives you irange(lo, hi) cheaply.
• When you need in-order iteration at any point. Heap iteration order is arbitrary — you'd have to pop everything (O(n log n)) to iterate sorted. Sorted list iterates in-order for free.

Side by side

Worked example — heap (LC 703 Kth Largest Element in a Stream)

Keep a running k-th largest as new numbers arrive.

Only the k-th largest matters at any moment. Keep a min-heap of size k; the root is the k-th largest.

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)     # O(n)
        while len(self.heap) > k:
            heapq.heappop(self.heap)  # trim to size k

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

Each add is O(log k). Sorted list would work too but at higher constant factor — heap is the right tool because you never care about anything except the current minimum of the k-element set.

Worked example — sorted list (LC 220 Contains Duplicate III)

Given an array, find if there exist indices i and j such that |nums[i] - nums[j]| ≤ t and |i - j| ≤ k.

Sliding window of size k, but the question inside the window is "does any current element lie within t of the new arrival?" — a nearest-neighbour query. Heap can't answer that. Sorted list does it with two bisect calls.

from sortedcontainers import SortedList

def containsNearbyAlmostDuplicate(nums, k, t):
    window = SortedList()
    for i, x in enumerate(nums):
        # Predecessor and successor of x in the current window
        idx = window.bisect_left(x)
        if idx > 0 and abs(window[idx - 1] - x) <= t:
            return True
        if idx < len(window) and abs(window[idx] - x) <= t:
            return True
        window.add(x)
        if len(window) > k:
            window.remove(nums[i - k])
    return False

Each iteration is O(log k). This problem is sortable by heap-flavoured reasoning, but the two-pointer / bucket approaches all require more code to match the sorted-list version's clarity.

Bottom line

Ask: can I answer the question with just the extremum?

• Yes — heap. O(log n) push/pop, O(1) peek, and heapify beats a sort for building.
• No, I need arbitrary lookups or in-order iteration — sorted list (SortedList / TreeSet / std::set). Uniform O(log n) at the cost of a bigger constant factor.

For heaps that need decrease-key, standard-library heaps come up short — push duplicates and skip stale entries on pop, or reach for a Fibonacci heap only if the interviewer explicitly asks. See the time-complexity-of-common-operations post for the per-language details on heapq, PriorityQueue, and std::priority_queue.

For the amortised O(log n) claim both structures cash in on, and the O(n) heapify fact that surprises most candidates, see the Big-O cheat sheet.