Building Heaps from an array of keys

Introduction

In the last post we learnt the basics of the heap data structure, its array and tree representations. We also learnt about the heap property and its significance.

In the process of learning we understood that a given node can be disturbed and the heap property needs to be restored using the Heapify operation.

Here in this post, we will try building heaps from an array of keys.

Building Heaps

Let us think about the easiest way to build a heap. Assume we are given the below array A:arrhp - Copy

This clearly is not satisfying the max heap property because the root (value of A[1]) is not the largest in the array. Also for each index i the key at A[i] is not larger than keys at A[2i] and A[2i+1].

What would make this array a heap?

Some re-arrangements of course, if we can rearrange elements in such a way that the max heap property is satisfied, we will get a max heap out of this array. The algorithm is pretty simple and we will prove that it works.

  • What is the total number of leaves in the heap with N nodes?
    • Its N/2 + (1/2) or we can say,  floor(N/2) + 1.
    • This is a simple maths, in any binary tree the number of leaves is one more than the number of internal nodes.
    • Say there are K internal nodes, hence there will be K+1 leaves. In this case K+K+1  = N
    • Which implies that K = N/2 – 1/2 and hence K+1 which is the number of leaves would be equal to N/2 + 1/2
  • Therefore in the above array keys from index N/2 + 1 to N are all leaves.
  • Now all the leaves can be considered as max heaps with just one node and the node is the root of the max heap. This is a trivial statement.
  • Now starting from index i,, such that 1<= i <=N/2, are all the internal nodes.
  • We can just test if the internal nodes satisfy the max heap property.
    • If yes, we don’t need to do anything on this node and move to test another node.
    • If the property is not satisfied, we need to heapify that node to restore the max heap property.
  • By the end of the loop where we reach index i = 1 and restore the max heap property at that node, the algorithm completes.

Let us perform a dry run on this and try to fix the above array.

Here is the array again for convenience and its corresponding tree representation.

img1