What is a Heap ?
A heap is a partially ordered complete binary tree. To say that a heap is partially ordered is to say that there is some relationship between the value of a node and the values of its children. In a min-heap, the value of a node is less than or equal to the values of its children. In a max-heap, the value of a node is greater than or equal to the values of its children. Consequently, the smallest (largest) value in a min-heap (max-heap) is at the heap's root. The heap ADT appears below.
An array A that presents a heap with two attributes:
- length[A] : the number of elements in the array.
- heap‐size[A] : the number of elements in the heap stored with array A.
- length[A] ≥ heap‐size[A]
The following is a heap representation in an Array.
If a complete binary tree with n nodes is represented sequentially, then for any node with index i, 1 ≤i ≤n, we have
- A is the root of the tree
- the parent PARENT(i) is at [ i / 2 ] if i ≠1
- the left child LEFT(i) is at 2i
- the right child RIGHT(i) is at 2i+1
There are two kind of binary heaps: max‐heaps and min‐heaps.
MAX – Heap : In a max‐heap, the max‐heap property is that for every node i other than the root
A[PARENT(i) ] ≥ A[i].
The largest element in a max‐heap is stored at the root. The subtree rooted at a node contains values no larger than that contained at the node itself.
MIN– Heap : In a min‐heap, the min‐heap properties that for every node i other than the root, the smallest element in a min‐heap is at the root. The subtree rooted at a node contains values no smaller than that contained at the node itself.
A[PARENT(i) ] ≤ A[i]
Following are the Example of MAX & MIN Heap