Binary Heap is an array object can be viewed as Complete Binary Tree. Each node of the Binary Tree corresponds to an element in an array.
The root of tree A [1] and gives index 'i' of a node that indices of its parents, left child, and the right child can be computed.
Representation of an array of the above figure is given below:
The index of 20 is 1
To find the index of the left child, we calculate 1*2=2
This takes us (correctly) to the 14.
Now, we go right, so we calculate 2*2+1=5
This takes us (again, correctly) to the 6.
Now, 4's index is 7, we want to go to the parent, so we calculate 7/2 =3 which takes us to the 17.
A binary heap can be classified as Max Heap or Min Heap
1. Max Heap: In a Binary Heap, for every node I other than the root, the value of the node is greater than or equal to the value of its highest child
Thus, the highest element in a heap is stored at the root. Following is an example of MAX-HEAP
2. MIN-HEAP: In MIN-HEAP, the value of the node is lesser than or equal to the value of its lowest child.
1. Maintaining the Heap Property: Heapify is a procedure for manipulating heap Data Structure. 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 probably violate the heap property i.e. A [i] < A [2i] or A [2i+1]. The procedure 'Heapify' manipulates the tree rooted as A [i] so it becomes a heap.
MAX-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 [r] > A[largest] 7. Then largest ← r 8. If largest ≠ i 9. Then exchange A [i] A [largest] 10. MAX-HEAPIFY (A, largest)
The maximum levels an element could move up are Θ (log n) levels. At each level, we do simple comparison which O (1). The total time for heapify is thus O (log n).
BUILDHEAP (array A, int n) 1 for i ← n/2 down to 1 2 do 3 HEAPIFY (A, i, n)
HEAP-SORT (A) 1. BUILD-MAX-HEAP (A) 2. For I ← length[A] down to Z 3. Do exchange A [1] ←→ A [i] 4. Heap-size [A] ← heap-size [A]-1 5. MAX-HEAPIFY (A,1)