All purpose of binary heap

Question

Definition:

A priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

Implementation:

To implement Priority queue, unsorted array, sorted array and binary heap data structure are the 3 implementation strategies .

To be specific, binary heap implementation strategy can be represented using array of keys,

or

each key as binary node having two children.

---

Question:

Apart from priority queue implementation, Are their any other applications of using binary heap data structure?

Answer 1

A binary heap can be used to extract (max or min) element in O(logn) time. This property can be exploited to be used in many algorithms to get better run-time.

For example, once I used it in k-merge sort algorithm to increase time efficiency of sorting step of the k-merge sort. In brief, it made binary heaps of the k-subarrays, and the sorting can be achieved in linear time which is better than usual sorting step of a merge sort.

It is also used in Dijkstra's algorithm, Prim's algorithm to decrease their run time.

You can also take a look here

Answer 2

Binary heaps have one other useful (and major) application: HeapSort. HeapSort has higher overhead than QuickSort but its worst case is O(n log n) vs. QuickSort's O(n*n). QuickSort can be improved upon to obtain a worst case of O(n log n) by switching to HeapSort once the interval is sufficiently short -- this is called IntroSort, and is what is used in the STL and the C++ standard library. See https://en.wikipedia.org/wiki/Introsort