mastorna.it
IT

Sorting algorithms · 4/7

Heapsort

Builds a max heap and moves maxima to the end.

Average timeΘ(n log n) SpaceΘ(1) StableNo In placeYes

How it works

The root holds the maximum. Swap it with the active end, shrink the heap, and restore the heap property.

Invariant: After each extraction the suffix is final and sorted, while the prefix is a max heap.

What is a heap

A binary heap is a complete binary tree satisfying a local ordering relation. “Complete” means that every level is full except possibly the last, which is filled from left to right. This shape guarantees Θ(log n) height.

Max-heap property

Every node is greater than or equal to its children. Therefore the maximum of the entire heap is always at root A[0]. Siblings and separate subtrees do not need to be ordered relative to one another.

Array representation

No pointers are needed: with zero-based indices, the children of A[i] are A[2i+1] and A[2i+2], while for i > 0 the parent of A[i] is A[⌊(i−1)/2⌋]. Indices beyond the current heap length are not part of the tree.

Example

The array [9, 7, 6, 4, 3, 1, 5, 2] represents a max heap: A[0]=9 dominates 7 and 6; A[1]=7 dominates 4 and 3; the same property holds for every other parent.

A heap and a BST are not the same thing. In a BST every key in the left subtree is smaller than the node and every key in the right subtree is larger; in a max heap only parents and children are compared. A heap finds the maximum quickly, but it does not support arbitrary ordered search.

Step-by-step visualization

The bar view shows swaps and the sorted region; the parallel representation links every array position to its corresponding max-heap node.

Use 2 to 16 values. This visualizer accepts values from 0 to 999.

Max heap: tree and array Children of A[i]: A[2i+1] and A[2i+2] · green: sorted position

Comparisons
0
Writes
0
Swaps
0
Pass / level
0
active comparison extracted maximum final

Pseudocode linked to the visualization

Heap sort

  1. heapSort(A)
  2. buildMaxHeap(A)
  3. for end ← length(A) − 1 downto 1
  4. swap A[0], A[end]
  5. siftDown(A, 0, end)

buildMaxHeap

  1. buildMaxHeap(A)
  2. for root ← ⌊length(A) / 2⌋ − 1 downto 0
  3. siftDown(A, root, length(A))

siftDown

  1. siftDown(A, root, end)
  2. while 2 · root + 1 < end
  3. left ← 2 · root + 1
  4. right ← left + 1
  5. largest ← root
  6. if A[left] > A[largest]: largest ← left
  7. if right < end and A[right] > A[largest]: largest ← right
  8. if largest = root: return
  9. swap A[root], A[largest]
  10. root ← largest

The highlighted line corresponds to the operation described by the visualizer. Index-management details are intentionally simplified.

Complexity analysis

Best caseΘ(n log n)

The standard extraction phase performs n−1 heap repairs, Θ(n log n).

Average caseΘ(n log n)

Build-heap is Θ(n); Θ(n log n) extraction dominates.

Worst caseΘ(n log n)

Heap height is always Θ(log n), so worst time stays Θ(n log n).

Auxiliary spaceΘ(1)

The iterative form uses Θ(1) auxiliary space. Long-distance swaps destroy stability.

Properties at a glance

Unstable

Stability concerns the relative order of elements with equal keys.

In place

This classification refers to the version shown on this page.

When to use it and what to avoid

A good choice when…

Useful for a Θ(n log n) guarantee with constant auxiliary space.

Common mistake

Bottom-up build-heap is Θ(n); n separate insertions would be Θ(n log n).