Heap Sort

Table of Contents +

Say you have a class of students. You want to line them up from shortest to tallest. One simple way is to keep finding the tallest person left. You send them to the back of the line. Then you look again. That is slow. You scan everyone each time. Heap sort uses the same idea but in a smarter way. It keeps the values in a structure called a heap. So finding the biggest one is fast every single time.

🎯 What Is Heap Sort?

Heap sort is a sorting method that uses a max-heap to sort an array. A max-heap is a special arrangement of values. The parent is always bigger than its children. So the biggest value sits right at the top.

Here is the plain idea. The largest value in a max-heap is always at the root. The root is the first element. So heap sort keeps grabbing that root and moving it to the end of the array. Then it fixes the heap and grabs the next largest. Do this again and again. The array ends up sorted.

If you have not seen heaps yet, read Introduction to Heap first. We will keep the heap part short here.

Note

A heap is usually stored in a plain array, not as a tree with pointers. For a node at index i, its left child is at 2*i + 1, its right child is at 2*i + 2, and its parent is at (i - 1) / 2. This little trick is why heap sort needs no extra space.

🌳 The Heapify Idea (Sift Down)

Before we sort, we need one helper. It is called heapify. People also call it “sift down”. The job is simple. Take one node that might be in the wrong spot. Push it down until the max-heap rule holds again.

Here is how sift down works on a node:

Look at the node and its two children.
Find the largest of the three.
If the node itself is already the largest, stop. Nothing to do.
Otherwise swap the node with that larger child.
The node moved down one level. So repeat the check from its new spot.

This keeps going until the node is bigger than both children. Or it reaches the bottom.

🪜 Steps to Heap Sort an Array

Now the full plan. We do it in two phases. Phase one builds the heap. Phase two pulls out the values one by one.

Phase 1 — Build a max-heap.

Start from the last node that has a child. Call sift down on each node, moving backwards to the root. After this, the whole array obeys the max-heap rule.

Phase 2 — Pull out the max, one by one.

The root (index 0) is the largest value. Swap it with the last item of the heap. That largest value is now in its final sorted spot. So shrink the heap by one.
After the swap, the new root may break the heap rule. Call sift down on the root to repair the heap.
Repeat step 2 and step 3 until the heap has only one element left. The array is now sorted in ascending order.

The nice part is that everything happens inside the same array. We never need a second array.

💻 Heap Sort in Code

Let us sort the array [12, 11, 13, 5, 6, 7]. We write a siftDown helper. We write a heapSort function that builds the heap and then pulls out the max each time. Then we print the result.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

# Push the node at index i down until the max-heap rule holds.
# n is the current size of the heap.
def sift_down(arr, n, i):
    while True:
        largest = i            # assume the node is the largest
        left = 2 * i + 1       # left child
        right = 2 * i + 2      # right child

        if left < n and arr[left] > arr[largest]:
            largest = left
        if right < n and arr[right] > arr[largest]:
            largest = right

        if largest == i:       # node is in the right place
            break

        # swap node with the larger child
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest            # move down and check again


def heap_sort(arr):
    n = len(arr)

    # Phase 1: build a max-heap from the last parent up to the root.
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)

    # Phase 2: pull the max out one by one.
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]   # move current max to the end
        sift_down(arr, end, 0)                # fix the shrunken heap


arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array:", arr)

The output of the above code will be:

Sorted array: [5, 6, 7, 11, 12, 13]

Tip

See the two phases in the code? The first loop builds the heap. The second loop swaps the root to the end and shrinks the heap. It fixes the root each time. That second loop is doing the actual sorting.

⏱️ Time and Space Complexity

Let us talk about cost. The good news is that heap sort stays fast no matter what the input looks like. Even if the array is already sorted or fully reversed, the time stays the same.

Building the heap takes O(n) time.
Each sift down after a swap takes O(log n) time. We do it n times. So the sorting phase is O(n log n).
Together the whole thing is O(n log n).

One thing to note. Heap sort is not stable. Stable means two equal values keep their original order. Heap sort can move equal values around because of the swaps. So their order may change.

Note

Heap sort uses O(1) extra space. It sorts inside the original array and only needs a couple of temporary variables for swapping. That makes it a true in-place sort.

Here is the full picture in one table.

Case	Time Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)
Space	O(1)

⚠️ Common Mistakes

A few slips trip up almost everyone the first time. Watch for these.

Starting the build-heap loop from the wrong index. It must start from n / 2 - 1, the last node that has a child, not from the end of the array.
Passing the full size n to sift down during the sorting phase. You must pass the shrinking size end. Otherwise you touch elements that are already sorted and placed.
Forgetting to fix the root after the swap. The new root almost always breaks the heap rule. So you must sift it down again.
Building a min-heap by mistake when you want ascending order. For ascending order you need a max-heap, where the parent is bigger than its children.

🧩 What You’ve Learned

✅ Heap sort first builds a max-heap, where the largest value sits at the root.

✅ It repeatedly swaps the root to the end of the array, shrinks the heap, then fixes the root with sift down.

✅ The sift down (heapify) helper pushes a node down until it is bigger than both its children.

✅ Heap sort runs in O(n log n) time in every case and uses only O(1) extra space.

✅ Heap sort is in-place but not stable, so equal values may not keep their original order.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Quick Sort
Introduction to Heap

Previous Quick Sort Next Counting Sort

Share & Connect

Share on LinkedIn