Editor

Python Program for Heap Sort

Intermediate · Searching and sorting

A max heap is a list arranged like a tree in which every parent is at least as big as its children, so the largest value is always at index 0. The children of index i sit at indexes 2i + 1 and 2i + 2. Heap sort builds a max heap, then keeps moving the largest value to the end of the list and repairing the heap, until everything is sorted.

Program

heap_sort.py
def heapify(a, size, root):
# Push a[root] down until it is bigger than both of its children
largest = root
left = 2 * root + 1
right = 2 * root + 2
if left < size and a[left] > a[largest]:
largest = left
if right < size and a[right] > a[largest]:
largest = right
if largest != root:
a[root], a[largest] = a[largest], a[root]
heapify(a, size, largest)
numbers = [12, 11, 13, 5, 6, 7]
print("Original list:", numbers)
n = len(numbers)
# Step 1: build a max heap, so the largest value is at index 0
for i in range(n // 2 - 1, -1, -1):
heapify(numbers, n, i)
print("Max heap:", numbers)
# Step 2: swap the largest to the end, then repair the heap that is left
for end in range(n - 1, 0, -1):
numbers[0], numbers[end] = numbers[end], numbers[0]
heapify(numbers, end, 0)
print(f"Moved {numbers[end]} to the end: heap {numbers[:end]}, sorted {numbers[end:]}")
print("Sorted list:", numbers)
Output
Original list: [12, 11, 13, 5, 6, 7]
Max heap: [13, 11, 12, 5, 6, 7]
Moved 13 to the end: heap [12, 11, 7, 5, 6], sorted [13]
Moved 12 to the end: heap [11, 6, 7, 5], sorted [12, 13]
Moved 11 to the end: heap [7, 6, 5], sorted [11, 12, 13]
Moved 7 to the end: heap [6, 5], sorted [7, 11, 12, 13]
Moved 6 to the end: heap [5], sorted [6, 7, 11, 12, 13]
Sorted list: [5, 6, 7, 11, 12, 13]

How it works

  1. heapify() compares a parent with its two children and swaps it with the bigger child if needed, then keeps going down from there.
  2. Step 1 calls heapify() on every parent, from the last parent back to the root, which turns the whole list into a max heap.
  3. In step 2, the root holds the largest value, so it is swapped with the last element of the heap, which is its final place.
  4. The heap is now one element shorter, and heapify() on the root restores it. The printout shows the heap part shrinking and the sorted part growing.
  5. Heap sort takes about n x log n steps and needs no extra list.

Another way to write it

Using the heapq module

Using the heapq module
import heapq
numbers = [12, 11, 13, 5, 6, 7]
heap = numbers.copy()
heapq.heapify(heap) # a min heap: the smallest value is at index 0
print("Min heap:", heap)
sorted_list = []
while heap:
sorted_list.append(heapq.heappop(heap)) # always removes the smallest
print("Sorted list:", sorted_list)
Output
Min heap: [5, 6, 7, 11, 12, 13]
Sorted list: [5, 6, 7, 11, 12, 13]

Python's heapq module keeps a min heap, so popping repeatedly gives the values from smallest to largest.

Try it yourself

Change both > signs in heapify() to < and see the list come out in descending order.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises