Skip to content
Hello Python

Sort with a Heap Frontier

Practice ExerciseIntermediateMediumHeapHeap Sort

Checking your account…

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

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement heap_sort(values). Return a new ascending list using heapq; do not call sorted or list.sort.

Starter code

def heap_sort(values):
    pass
Test cases

mixed

{
  "args": [
    [
      5,
      1,
      3,
      1
    ]
  ]
}

Expected: [1,1,3,5]

ordered

{
  "args": [
    [
      1,
      2,
      3
    ]
  ]
}

Expected: [1,2,3]

Wizard outline
  1. Step 1: Protect the caller input

    Create an independent working list for the empty boundary. The output contract does not authorize mutation of values; this checkpoint establishes ownership before extraction exists.

  2. Step 2: Establish the heap invariant

    Expose the minimum at the root. heapify transforms the copy so the next global output is always at index zero.

  3. Step 3: Drain the ordered frontier

    Emit every minimum in ascending order. After each pop, the heap restores its invariant over exactly the unseen values.

Footguns and prerequisites
  • Heapifying the caller list mutates input unexpectedly.
  • Reading heap[0] repeatedly without popping duplicates one value.
  • functions
  • lists and tuples
  • control flow
Reviewed references
Recommended approach and implementation

Heapify a copy, then repeatedly pop the minimum into the result.

Why it works: The heap root is the smallest unseen value before every extraction. Removing all roots therefore emits the complete multiset in ascending order.

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