DSA Heap Sort

How it works

Python’s heapq supplies a reviewed min-heap interface available in the course’s Python 3.12 environments. heapify builds the heap from the copied values, then each pop repairs the invariant after removing its root. This teaching implementation is a heap-based sorter using a standard-library primitive, not a hand-written in-place heapsort or a stable record sorter. Later priority-queue examples use the same invariant without removing every item at once.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as heap-sort.py and run python heap-sort.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

import heapq

def heap_sort(values):
    pending = list(values)
    heapq.heapify(pending)
    return [heapq.heappop(pending) for _ in range(len(pending))]

print(heap_sort([14, 5, 11, 5, 2]))
print(heap_sort([]))

Expected result

[2, 5, 5, 11, 14]
[]

The result is ordered even though intermediate heap storage is only partially ordered. Empty input performs no pops. A caller that only needs the next smallest task can keep the heap instead of paying to produce a completely sorted collection.

Time, space and assumptions

Heap construction is O(n), followed by n O(log n) removals, for O(n log n) total time. This copied-heap implementation uses O(n) storage; it is not the O(1)-auxiliary in-place variant.