CZ
CalcyZone
Computer Science & Software CalcyZone Calculator

Heap Sort Visualizer (Step-by-Step)

Watch heap sort build a max-heap and extract elements, with animated bars and every swap explained.

Sorted
3, 9, 10, 27, 38, 43, 82
Swaps
15
Steps
18
Step 1 / 18

Start: build a max-heap.

Step-by-step working

  1. Build a max-heap bottom-up (sift-down from n/2 āˆ’ 1 to 0).
  2. Repeatedly swap the root with the last unsorted element and sift down.
  3. Press Play or Step to watch every swap.

Mathematical Formula

Build heap: for i = āŒŠn/2āŒ‹āˆ’1 ā€¦ 0, siftDown(i). Then for end = nāˆ’1 ā€¦ 1: swap(0, end), siftDown(0, end). Time O(n log n), space O(1).

Overview & Explanation

Heap sort turns the array into a binary max-heap, then repeatedly moves the root (maximum) to the end.

How It Works

  • Children of index i are 2i+1 and 2i+2.
  • Sift down swaps a node with its larger child until the heap property holds.
  • Each extraction shrinks the heap by one.

Practical Applications

  • Learning priority queues.
  • Interview preparation.

Example 1: 38, 27, 43, 3, 9, 82, 10

Seven elements.

1

Inputs

Array to sort (comma separated, max 40): 38, 27, 43, 3, 9, 82, 10

= entered
2

Step 1

Build a max-heap bottom-up (sift-down from n/2 āˆ’ 1 to 0).

3

Step 2

Repeatedly swap the root with the last unsorted element and sift down.

4

Step 3

Press Play or Step to watch every swap.

5

Sorted

Result

= 3, 9, 10, 27, 38, 43, 82

Example 2: already sorted 1..6

Heap sort still does O(n log n) work.

1

Inputs

Array to sort (comma separated, max 40): 1, 2, 3, 4, 5, 6

= entered
2

Step 1

Build a max-heap bottom-up (sift-down from n/2 āˆ’ 1 to 0).

3

Step 2

Repeatedly swap the root with the last unsorted element and sift down.

4

Step 3

Press Play or Step to watch every swap.

5

Sorted

Result

= 1, 2, 3, 4, 5, 6

How it's calculated & sources

Build heap: for i = āŒŠn/2āŒ‹āˆ’1 ā€¦ 0, siftDown(i). Then for end = nāˆ’1 ā€¦ 1: swap(0, end), siftDown(0, end). Time O(n log n), space O(1).

Frequently Asked Questions

Is heap sort stable?
No, equal elements may change relative order.
Why O(n) heap construction?
Most nodes are near the leaves and sift only a short distance; the sum is linear.
Heap sort vs quick sort?
Heap sort guarantees O(n log n) worst case; quick sort is usually faster in practice.

Related Calculators

computer-science

Quick Sort Visualizer & Partition Calculator

Step-by-step Quick Sort partition visualizer demonstrating pivot selection, left/right pointers, and recursion tree.

Use Calculator
computer-science

Merge Sort Visualizer

Interactive divide and conquer Merge Sort step generator showing array splitting and merging.

Use Calculator
computer-science

Shell Sort Visualizer (Step-by-Step)

Animate Shell sort with shrinking gaps and see each gapped insertion move.

Use Calculator
computer-science

Bubble Sort Visualizer & Step Calculator

Interactive step-by-step Bubble Sort execution visualizer with comparisons, swaps, and time complexity breakdown.

Use Calculator