Indian Computing Olympiad

Heaps

Building a heap

One way to construct a heap from a list or array is to insert the elements one at a time. This takes n log n time, since we insert n elements and each insert takes log n time.

A more efficient way is to work bottom up. Suppose we write out the contents of the array in the form of a binary tree. For example, if we start with 7 5 6 15 2 1 18, the tree is

                    --7--
                   /     \
                  5       6
                 / \     / \
               15   2   1   18
      

Notice that the nodes at the bottom level satisfy the heap property, since they don't have any children. Starting at these "leaf" nodes, we work up the tree, combining heaps at the next level.

Each lowest level node (index greater than n div 2) is a singleton heap. For each node at level at second lowest level, we locally adjust the values into 3 element heaps. At the next level, we combine two 3 element heaps with a new root into 7 element heaps. Each higher level has 1/2 the number of nodes.

First step:

                  5            2            6            1
                 / \    ==>   / \          / \    ==>   / \
               15   2       15   5        1   18       6   18
      

Second step:

         --7--                --1--                  --1--
        /     \              /     \                /     \
       2       1    ==>     2       7     ==>      2       6
      / \     / \          / \     / \            / \     / \
    15   5   6   18      15   5   6   18        15   5   7   18
      

What is the complexity?

Naively, it looks like n log n since we fix the heap n/2 times and each fix takes log n.

To fix the heap at the root of n nodes, we need to make a heap at each of its children (trees of size n/2) and then fix the root (walk down upto log n steps flipping values).

Notice that later steps take more operations but there are only half as many corrections to make. Overall, if you add up the operations, it turns out to be O(n).