Build a max heap, move its largest root value to the end, then restore the heap property in the remaining prefix. Parent and child positions are calculated within the array; no separate tree is stored.

A heap-sort simulator with synchronized array and tree views

Play, step, or seek with the slider. The tree below is another view of the same array shown by the bars.

Best caseO(n log n)

AverageO(n log n)

Worst caseO(n log n)

Extra spaceO(1)

StableNo

Heap constructionO(n)

The array is the tree

Node i has children 2i+1 and 2i+2, and parent (i−1)//2. sift_down swaps a node with its larger child until the heap property holds. A sift traverses O(log n) levels, and repeated extraction gives O(n log n) sorting time.

Initial heap construction sifts down from the last parent toward the root. Most nodes are near the bottom and move only a short distance, so construction totals O(n), not O(n log n).

Coding exercises: heaps as priority queues

Priority queues are a more common application than manually implementing heap sort. Python's heapq is a min heap; negated numeric priorities can implement a max heap. Keep a size-k min heap to find the largest k values in O(n log k).

import heapq
h = []
for x in a:
    heapq.heappush(h, x)
    if len(h) > k:
        heapq.heappop(h)    # discard the heap minimum
# h contains the largest k values