Core · Module 11 · Lesson 3 of 4

Heapify and heap sort

Building a heap by sifting down from the last parent to the root takes O(n), not O(n log n), because most nodes sit near the bottom. Repeatedly moving the maximum to the end then sorts the array in place.

ProAbout 14 minutes

By the end you can

Build a heap from an unsorted array in place, bottom-up
Explain why bottom-up heapify is O(n) while n separate pushes are O(n log n)
Sort an array with heap sort, and compare it with merge sort and quick sort

Builds on Sift-up and sift-down.

01 · A question first

Pushing n items into a heap one at a time costs O(n log n). Building the same heap from an unsorted array, by sifting down from the middle of the array backwards to the front, costs only O(n). How can the same result be cheaper to reach?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

Building a heap all at once
Bottom-up heapify
Why it is linear
Heap sort
Wider heaps
Partial sorting
Pseudocode & Multi-Language Implementations (C++, Java, Python)
Complexity Derivation, Edge Cases & Common Mistakes

See plans Already a member? Sign in

03 · Practice

Practice · medium · LeetCodeSort an arraySort an array of integers in O(n log n) without the built-in sort: implement merge sort, then quick sort with a random pivot, and compare.Practice · medium · LeetCodeKth largest element in an arrayFind the kth largest value in an unsorted array with a size-k heap or with quickselect, without fully sorting it.

Asked in interviews

Why is building a heap O(n) and not O(n log n)?

Something wrong with this lesson? Report a problem