Heap and Priority Queue

Based on heap property there are two types of heap :

1. Max-Heap: The key present at the any node must be greater than the keys present at both of it’s children.
2. 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.