Heap Sort

DSA · Heaps

Theory

Heap sort first builds a max-heap from the array, so the largest element sits at index 0. It then repeatedly swaps the root with the last unsorted element, shrinks the heap by one and sifts the new root down. After n-1 rounds the array is sorted in place. It always takes O(n log n) time and O(1) extra space, but it is not stable.

Why we use it

It guarantees O(n log n) with constant extra memory, unlike merge sort which needs O(n) memory.

When to use it

Use it when memory is tight and worst-case guarantees matter; in practice library sorts are usually faster.

How it works

  1. Build a max-heap from the array
  2. Swap root (max) with the last element
  3. Reduce heap size by 1
  4. Sift down the new root
  5. Heap size > 1? Yes: Repeat. No: Array is sorted.
  6. O(n log n), in place

Syntax

build max-heap (sift down from n//2 - 1 to 0)
for end from n-1 down to 1:
    swap arr[0], arr[end]
    sift_down(arr, 0, end)

Time: O(n log n)   Space: O(1)   Not stable

Example

def sift_down(a, i, size):
    while True:
        l, r, big = 2 * i + 1, 2 * i + 2, i
        if l < size and a[l] > a[big]: big = l
        if r < size and a[r] > a[big]: big = r
        if big == i: return
        a[i], a[big] = a[big], a[i]
        i = big

def heap_sort(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(a, 0, end)
    return a

print(heap_sort([12, 11, 13, 5, 6, 7]))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic