The Creation of a Min-Heap

A first solution is to successively insert the elements into the heap starting initially from the heap consisting of a single element:

  void CreateHeap()
  {
    int i;
    for (i=0; i<n; i++)
        Insert(H,i,H[i]);
  }

Analyzing the complexity of the insertion procedure, we deduce that, in the worst case, the newly inserted value goes up to the root of the tree, so it requires O(h) elementary operations, where h is the height of the heap. A heap being a complete binary tree, its height h will be [log n], so inserting a node into a heap with n elements is of
O(log n).

Let's estimate the worst-case complexity of the heap construction procedure by successive insertions. If all those 2^i values on the level i go up to the root, we get complexity of O(n log n).

Introductory Notions

Min-Heap generator

Heap

Priority queue

Applications

Dictionary

A more efficient heap construction strategy is based on the idea of balancing. The appeal of the procedure Insert(H,n,x) can be interpreted as a combination of two heaps: a heap with n elements and a heap consisting only of the element x. We can build the heap with the root H[i] combining at each step two heaps with similar sizes, the heap with the root 2*i, the heap with the root 2*i+1 and with the element H[i];

  void CreateHeap()
  {
    int i;
    for (i=(n-1)/2; i>=0; i--)
            CombHeap(i, n);
  }

Algorithm complexity

We define h=[log n] heap height. For each node x from the level i, i=0->h-1, to build the heap with the root x they are done at most h-i decreases in value x in the tree. So, in the worst case the number of elementary operations performed by the algorithm to build a heap with n elements is O(n). The heap construction algorithm has thus become linear.