Based on heap property there are two types of heap :
- Max-Heap : The key present at the any node must be greater than the keys present at both of it’s children.
- Min-Heap : The key present at the any node must be less than the keys present at both of it’s children.
How is Binary Heap represented?
- The root element will be at A[0]
- For ith node A[i] : Parent node = A [(i-1)/2], Left child node = A [(2*i) + 1], Right child node = A [(2*i)+2]. This property allows quick access-by-index which help us to manipulate the heap by swapping nodes. That’s why we also use heap to perform in-place sorting called Heap Sort.
Use it whenever you need quick access to the largest (or smallest) element , because that element will always be the first element in the array or at the root of the tree. So it's a good way to deal with incoming events or data where access to the smallest/largest are always required. That's why Priority Queues can be efficiently implemented using Binary Heap because it supports insert, delete and extract_max, decrease_Key operations in O(log n) time.
Heap Applications : Heap Sort, Priority Queue, Huffman Coding, Dijkstra Algorithms, Prims Algorithms, Selection Algorithms, Order statistics etc.
