Binary Heap

The binary heap data structure is an array that can be viewed as a complete binary tree. Each node of the binary tree corresponds to an element of the array. The array is completely filled on all levels except possibly lowest (lowest level is filled in left to right order and need not be complete).

There are two types of heap trees: Max heap tree and Min heap tree.

1. Max heap: In a heap, for every node i , the value of a node is greater than or equal to the value of its children.

A[PARENT (i)] ≥ A[i]. Thus, the largest element in a heap is stored at the root.

2. Min heap: In a heap, for every node i, the value of a node is less than or equal to the value of its children.

A[PARENT (i)]≤ A[i]. Thus, the smallest element in a heap is stored at the root.

 

The root of the tree A[1] and given index i of a node, the indices of its parent, left child and right child can be computed as follows:

  • PARENT (i): Parent of node i is at floor(i/2)
  • LEFT (i): Left child of node i is at 2i
  • RIGHT (i): Right child of node i is at (2i + 1)

Since a heap is a complete binary tree, it has a smallest possible height. A heap with N nodes always has O(log N) height. A heap is useful data structure when you need to remove the object with the highest (or lowest) priority. A common use of a heap is to implement a priority queue.

Heapify: Heapify is a procedure for manipulating heap data structures. It is given an array A and index i into the array. The subtree rooted at the children of A[i] are heap but node A[i] itself may possibly violate the heap property. A[i] < A[2i] or A[i] < A[2i +1]. The procedure ‘Heapify’ manipulates the tree rooted at A[i] so it becomes a heap.

 

Heapify (A, i)

  1. l ← left [i]
  2. r ← right [i]
  3. if l ≤ heap-size [A] and A[l] > A[i]
  4. then largest ← l
  5. else largest ← i
  6. if r ≤ heap-size [A] and A[i] > A[largest]
  7. then largest ← r
  8. if largest ≠ i
  9. then exchange A[i] ↔ A[largest]
  10. Heapify (A, largest)

Time complexity of Heapify algorithm is: O(log n)

Building a Heap: Heapify procedure can be used in a bottom-up fashion to convert an array A[1 . . n] into a heap. Since the elements in the subarray A[⎣n/2⎦+1 . . n] are all leaves, the procedure Build_Heap goes through the remaining nodes of the tree and runs ‘Heapify’ on each one. The bottom-up order of processing node guarantees that the subtree rooted at children are heap before ‘Heapify’ is run at their parent.

Build_Heap (A)

  1. heap-size (A) ← length [A]
  2. For i ← floor(length[A]/2) down to 1 do
  3. Heapify (A, i)

Time complexity of Build_Heap algorithm is: O(n) Heap of height h has the minimum number of elements when it has just one node at the lowest level.

Minimum nodes of Heap of a height h: The levels above the lowest level form a complete binary tree of height h -1 and 2h -1 nodes. Hence the minimum number of nodes possible in a heap of height h is 2hnodes.

Maximum nodes of Heap of a height h: Heap of height h, has the maximum number of elements when its lowest level is completely filled. In this case the heap is a complete binary tree of height h and hence has(2h+1 -1) nodes.

 

For Min heap tree of n-elements:

  • Insertion of an element: O(log n)
  • Delete minimum element: O(log n)
  • Remove an element: O(log n)
  • Find minimum element: O(1)

DecreaseKey(p,d) operation on heap:

  • This operation lowers the value of the element at position p by a positive amount d.
  • It is used to increase the priority of an element.
  • We have to find a new position of the element according to its new priority by percolating up.

IncreaseKey(p,d) operation on heap:

  • This operation increases the value of the element at position p by a positive amount d.
  • It is used to decrease the priority of an element.
  • We have to find a new position of the element according to its new priority by percolating down.

Remove(p) operation on heap:

  • With this operation an element p is removed from the queue.
  • This is done in two steps: Assigning the highest priority to p – percolate p up to the root.
  • Deleting the element in the root and filling the hole by percolating down the last element in the queue.

Heap Sort:

 

The heap sort combines the best of both merge sort and insertion sort. Like merge sort, the worst case time of heap sort is O(n log n) and like insertion sort, heap sort sorts in-place.

  • Given an array of n element, first we build the heap.
  • The largest element is at the root, but its position in sorted array should be at last. So, swap the root with the last element and heapify the tree with remaining n-1 elements.
  • We have placed the highest element in its correct position. We left with an array of n-1 elements. repeat the same of these remaining n-1 elements to place the next largest element in its correct position.
  • Repeat the above step till all elements are placed in their correct positions.

heapsort(A) {

BUILD_HEAP (A);

for (i = length (A); i>=2; i–){

exchange (A[1], A[i]);

heap-size [A] = heap-size [A] – 1;

Heapify (A, 1);

}

}

(OR)

heapsort(A) {

BUILD_HEAP (A); 

heapsize ← heap-size[A];

for (i = length (A); i>=2; i–){

A[heapsize] = Heap-Extract-Max (A);

heap-size [A] = heap-size [A] – 1;

}

}