PriorityQueue

Reference

Binary_Heap

Binary Heap

A Binary Heap is a Binary Tree with following properties.

• It’s a complete tree. This property makes them suitable to be stored in an array
• A Binary Heap is either Min Heap or Max Heap. (Recursively)

How is Binary Heap represent?

A Binary Heap is a Complete Binary Tree. A binary heap is typically represented as an array.

• The root element will be at Arr[0]

• Arr[(i-1)/2] : the parent node

• Arr[(2*i)+1] : the left child

• Arr[(2*i)+2] : the right child

Applications of Heaps:

1. Heap Sort: Heap Sort uses Binary Heap to sort an array in O(nLogn) time.
2. Priority Queue: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operation in O(logn) time.
3. Graph Algorithms: The priority queues are especially used in Graph Algorithms like Dijkstra's Shortest Path and Prim's Minimum Spanning Tree
4. Many problems can be efficiently solved using Heaps. See following. for example.
   1. K’th Largest Element in an array
   2. Sort an almost sorted array
   3. Merge K sorted Arrays

Operation on Min Heap

1. getMini()
2. extractMin()
3. decreaseKey()
4. insert()
5. delete()