Building a heap in linear time is a concept that often surprises those new to computer science and data structures, primarily because its naive approach, which involves repeated insertions, takes $O(n \log n)$ time. The key to achieving $O(n)$ complexity lies in using a bottom-up approach rather than a top-down one. This article delves into the technicalities of building a heap in $O(n)$ time complexity, providing examples and explanations that unveil the underlying efficiency of this approach.

Understanding the Basics

Before diving into the details, it's essential to comprehend what a heap is. A heap is a complete binary tree that satisfies the heap property, which can be of two types:

• Max-Heap: For each node i, the value of i is greater than or equal to the values of its children.
• Min-Heap: For each node i, the value of i is less than or equal to the values of its children.

In an array representation of a heap, for any element at index i:

• The left child is located at 2i + 1
• The right child is at 2i + 2
• The parent is at (i - 1) / 2

Heap Construction Approach

Naive Method: Insertion

A straightforward way to build a heap is to repeatedly insert elements into a heap one by one. This process generally involves the following steps:

1. Insertion: Insert the element at the end of the array (heap).
2. Heapify Up: Adjust the position of the new element upwards to maintain the heap property, which involves comparing the element with its parent and swapping if necessary.

For n elements, this gives us an $O(n \log n)$ complexity because each insertion can cause reordering up to the height of the tree, which is $O(\log n)$.

Efficient Method: Bottom-Up Heapify

The more efficient way uses a bottom-up approach:

1. Start from the last non-leaf node and perform the heapify operation on each node. Since leaf nodes are inherently heaps, they do not require heapifying.
2. Heapify each subtree, fixing the heap from the bottom up.

The important observation here is that not all heapify operations cost $O(\log n)$. Nodes at the bottom of the tree have smaller subtrees, leading to a more efficient heapify process for those nodes.

Mathematical Justification

The efficiency comes from the distribution of nodes across the tree levels. The lower levels contain the majority of nodes, but heapify costs less for those nodes because their subtrees are smaller. Here's the breakdown:

• Leaf nodes: Don’t need heapifying.
• Level i: Has at most $2^i$ nodes.
• Heapifying a node at height h: Takes $O(h)$ operations.

Combining these, the total cost $T(n)$ to build a heap can be expressed as the sum across all levels:

$T(n) = \sum_{i=0}^{h} \left \lceil \frac{n}{2^{i+1}} \right \rceil \cdot O(i)$

where $h$ is the height of the heap.

Considering that the number of leaves (or near leaves) dominates while their operations are cheaper:

• More nodes are at height 1, fewer at height 2, and so forth.
• The cost diminishes as you ascend the heap levels.

Simplifying this gives the linear complexity $O(n)$, which is a result of decreasing weights with increasing levels effectively balancing the overall cost.

Example

To clarify, consider an array of elements [4, 10, 3, 5, 1]. Building a max-heap using the bottom-up method:

1. Initial Array: [4, 10, 3, 5, 1]
2. Last Non-Leaf Node: Element at index 1 (value 10)
   • No change for heapify at index 1 since 10 is already a valid max-heap root for its subtree.
3. Heapify Node at Index 0:
   • Swap 4 with 10: [10, 4, 3, 5, 1]
   • Further heapifying is necessary at index 1. Swap 4 with 5: [10, 5, 3, 4, 1]

Final Max-Heap: [10, 5, 3, 4, 1]

Summary Table

Key Points:

1. Efficiency: Layers near the leaves have cheaper operations.
2. Array Representation: Facilitates the identification of parent-child relationships.
3. Bottom-Up: Fundamental in reducing complexity, balancing larger numbers of less-costly operations.

By leveraging the heap's structural properties and executing fewer costly operations at the upper levels, the bottom-up approach offers an efficient way to build a heap with a time complexity of $O(n)$.