🎓 A1Learner
🔍

DSA Ordered Data in Python

Python ships no balanced tree for ordered data in its standard library. A sorted list plus the bisect module is the usual stand-in, searching fast but paying shifting elements on every insert.

Search is cheap, insertion shifts

bisect_left reports where each target belongs in the sorted list. Inserting 20 at index 4 must shift the two elements behind it.

import bisect

data = [3, 8, 12, 19, 25, 31]
for target in (12, 20, 40):
    pos = bisect.bisect_left(data, target)
    print("target", target, "lands at index", pos)
pos = bisect.bisect_left(data, 20)
print("shifts to insert 20:", len(data) - pos)
bisect.insort(data, 20)
print("after insert:", data)

A heap is not an ordered structure

The heap list printed here is not sorted past its first element. Only repeated pops reveal the full order.

import heapq

heap = []
for v in (9, 4, 7, 1, 8):
    heapq.heappush(heap, v)
print("heap list inside:", heap)
print("smallest at index 0:", heap[0])
print("rest in sorted order:", heap[1:] == sorted(heap[1:]))
print("pops in order:", [heapq.heappop(heap) for _ in range(5)])

Shifts add up

Eight inserts into a growing sorted list shift elements one slot at a time. The total reaches twelve shifts for these eight values.

import bisect

data = []
total_shifts = 0
for v in (50, 20, 80, 10, 40, 30, 70, 60):
    pos = bisect.bisect_left(data, v)
    total_shifts += len(data) - pos
    data.insert(pos, v)
    print("insert", v, "at", pos, "shifts:", len(data) - 1 - pos)
print("data:", data)
print("total shifts:", total_shifts)

Example

import bisect


def counted_search(data, target):
    lo, hi = 0, len(data)
    probes = 0
    while lo < hi:
        mid = (lo + hi) // 2
        probes += 1
        if data[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo, probes


stream = [(i * 37) % 101 for i in range(120)]
queries = [10, 25, 50, 77, 99] * 20

kept = []
shifts = 0
search_probes = 0
for v in stream:
    pos = bisect.bisect_left(kept, v)
    shifts += len(kept) - pos
    kept.insert(pos, v)
for q in queries:
    _, probes = counted_search(kept, q)
    search_probes += probes
print("bisect list inserts shifts:", shifts)
print("bisect list search probes:", search_probes)
print("bisect list total:", shifts + search_probes)

raw = []
processed = 0
rebuild_probes = 0
for v in stream:
    raw.append(v)
for q in queries:
    fresh = sorted(raw)
    processed += len(raw)
    _, probes = counted_search(fresh, q)
    rebuild_probes += probes
print("rebuild elements processed:", processed)
print("rebuild search probes:", rebuild_probes)
print("rebuild total:", processed + rebuild_probes)
print("same answers:", kept == sorted(raw))

Key points

  • The bisect module finds the insertion point of a value in a sorted list by binary search
  • Inserting into a list shifts every element after the insertion point one slot right
  • heapq guarantees only that index zero holds the smallest value
  • A heap cannot answer rank or range questions because its other elements are not in order
  • Python ships no balanced BST, which is why the bisect list is the common stand-in

In this example, 120 values are inserted and 100 searches run under both strategies. The bisect list pays 3566 shifts while inserting, then answers every search with a few probes, 680 in total. The rebuild strategy processes 12000 elements by sorting a fresh copy for every search. Keeping the list sorted wins this search-heavy workload, and both strategies agree on the final data.

Note

the bisect functions never check that the list is sorted, so keeping it sorted is the caller's job.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Why can a heap not replace a sorted list for the question asking for the fifth smallest value?