Course contentsShow
← Computer Science
Lesson 778 of 2,87218. Sorting AlgorithmsFree lesson

Converting an Array into a Max-Heap

Building a max-heap from an unsorted array using the heapify process in linear time.

Converting an Array into a Max-Heap

What you'll learn: How to transform an ordinary unsorted array into a valid max-heap efficiently using the heapify process.

The Core Idea

A max-heap is a complete binary tree where every parent node is larger than its children. When you have an unsorted array, you need to rearrange elements so they satisfy the heap property. The clever trick is that you don't need to insert elements one by one—you can build the heap in-place by starting from the bottom and working upward.

How It Works

Think of building a heap like organizing a company hierarchy where managers must always have higher salaries than their subordinates. Instead of hiring everyone one-by-one, you start with everyone already present and just rearrange them.

The algorithm works backwards from the last non-leaf node (at index n/2 - 1) up to the root (index 0). For each node, you perform a "heapify-down" operation: if the node is smaller than either child, swap it with the larger child and continue down the tree until the heap property is restored.

Why start at n/2 - 1? All nodes after this index are leaves (no children), so they're already valid heaps by themselves. You only need to fix the internal nodes.

Linear Time Complexity

Here's the beautiful part: this process runs in O(n) time, not O(n log n)! Most nodes are near the bottom of the tree and only need a few comparisons, while only a handful of nodes near the top need to bubble down many levels. The math works out to linear time overall.

Building from the Bottom Up

The process ensures that when you heapify a node, all its subtrees are already valid heaps. This bottom-up approach guarantees correctness and efficiency.

Key Takeaway: Building a max-heap from an unsorted array takes O(n) time by heapifying from the last non-leaf node upward, making it faster than inserting elements one-by-one.