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.

1. Length [A],number of elements in array
2. Heap-Size[A], number of elements in a heap stored within array A.

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.

1. PARENT (i)  
2.     Return floor (i/2)  
3. LEFT (i)  
4.     Return 2i  
5. RIGHT (i)  
6.     Return 2i+1  

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.

Heap Property:

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

1. A [PARENT (i) ≥A[i]  

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. A [PARENT (i) ≤A[i]  

Heapify Method:

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)

Analysis:

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).

Building a Heap:

BUILDHEAP (array A, int n)
 1 for i ← n/2 down to 1
 2 do
 3 HEAPIFY (A, i, n)

HEAP-SORT ALGORITHM:

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)