Skip to content
Hello Python
Algorithm1 Practice4 Interview

Heap Sort

Build a heap and repeatedly extract extrema for in-place O(n log n) sorting. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Heap Sort when the prompt's constraints and required operations match this shape: Build a heap and repeatedly extract extrema for in-place O(n log n) sorting.

Pybit demonstrates Heap Sort in a professional Python interview workspace.
On this page · Build a Max Heap In Place

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Heap Sort Code Labs

Build a Max Heap In Place

Heap sort first turns the array into a max heap. Bottom-up heapify starts at the last internal node because leaves already satisfy the heap property.

Swap the Root into Final Position

The root is the maximum remaining value. Swap it with the last position of the active heap, which grows a sorted suffix that will never be touched again.

Trace Max-Heap Construction

Reference
def heapify_trace(values):
    values=values.copy();trace=[];n=len(values)
    def sift(root,end):
        while 2*root+1<end:
            child=2*root+1
            if child+1<end and values[child+1]>values[child]:child+=1
            if values[root]>=values[child]:break
            values[root],values[child]=values[child],values[root];root=child
    for root in range(n//2-1,-1,-1):sift(root,n);trace.append(values.copy())
    return trace
Practice

Implement heapify_trace(values). Return array state after each bottom-up sift-down call.

Public tests

  • Sift internal nodes bottom up

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Restore the Shrinking Heap

After each root swap, sift the new root down only within the shortened heap boundary. Children in the sorted suffix are no longer heap members.

Heap Sort Values

Reference
def heap_sort(values):
    values=values.copy();n=len(values)
    def sift(root,end):
        while 2*root+1<end:
            child=2*root+1
            if child+1<end and values[child+1]>values[child]:child+=1
            if values[root]>=values[child]:break
            values[root],values[child]=values[child],values[root];root=child
    for root in range(n//2-1,-1,-1):sift(root,n)
    for end in range(n-1,0,-1):values[0],values[end]=values[end],values[0];sift(0,end)
    return values
Practice

Implement heap_sort(values). Return an ascending sorted copy using an in-place max heap.

Public tests

  • Move each max root into the suffix

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Heap Sort or Merge Sort

Heap sort guarantees O(n log n) with O(1) auxiliary array space but is not stable and has less cache-friendly access. Merge sort is stable and sequential but needs O(n) merge storage in standard arrays.

Explain It in an Interview

Say: “The active prefix is a max heap and the suffix is finalized ascending output. I move the root to the suffix and restore only the active heap.” State O(n) heapify plus O(n log n) extraction.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Heap Sort complete workflowO(n log n)O(n log n)Heapify a copy, then repeatedly pop the minimum into the result.

Space

O(n) for the focused Sort with a Heap Frontier implementation.

Assumptions

  • The heap root is the smallest unseen value before every extraction. Removing all roots therefore emits the complete multiset in ascending order.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Heap Sort invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The resolved region satisfies the target ordering relation.
  3. The unresolved region still contains every item not yet placed.
  4. Heapify one independent copy. Preserve this claim after every transition.
  5. Pop each minimum exactly once. Preserve this claim after every transition.

When To Use Or Avoid Heap Sort

Use It When

  • Use Heap Sort when this precondition is stated or can be proved: The comparison, key domain, stability need, and memory constraints match the selected ordering method.
  • Use it when this maintained state removes repeated work: The resolved region satisfies the target ordering relation.

Choose Another Tool When

  • Avoid Heap Sort when this precondition is absent: The comparison, key domain, stability need, and memory constraints match the selected ordering method.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The comparison, key domain, stability need, and memory constraints match the selected ordering method.

Avoid

def heap_sort(values):
    pass

Use instead

def heap_sort(values):
    import heapq
    heap = list(values)
    heapq.heapify(heap)
    ordered = []
    while heap:
        ordered.append(heapq.heappop(heap))
    return ordered

Where you will hit this: Sort with a Heap Frontier(opens in a new tab)

Breaking the state transition

Returns the heap array directly even though heap order is not total order.

Prevent it: Preserve this proof obligation: The resolved prefix, suffix, rank, digit pass, or bucket remains in its documented final relation.

Avoid

def heap_sort(values):
    import heapq
    out=list(values); heapq.heapify(out); return out

Use instead

def heap_sort(values):
    import heapq
    heap = list(values)
    heapq.heapify(heap)
    ordered = []
    while heap:
        ordered.append(heapq.heappop(heap))
    return ordered

Where you will hit this: Sort with a Heap Frontier(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n log n).

Avoid

def heap_sort(values):
    import heapq
    out=list(values); heapq.heapify(out); return out

Use instead

def heap_sort(values):
    import heapq
    heap = list(values)
    heapq.heapify(heap)
    ordered = []
    while heap:
        ordered.append(heapq.heappop(heap))
    return ordered

Where you will hit this: Car Fleet(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.