What are some other applications of a Heap?


#1

Question

In the context of this lesson, what are some other applications of a heap?

Answer

Heaps are typically used for tasks that require ordering or priority of items.

One application is in some graph algorithms, such as Dijkstra’s algorithm for shortest paths. To provide a brief explanation, a heap is used to implement a priority queue, which is utilized by the algorithm to get the shortest edge on each iteration and eventually find the shortest path between vertices.

Heaps are also applied in tasks requiring the smallest or largest value of a group of items using either a min-heap or max-heap, because these values will always be the first item of the heaps, and can be obtained very quickly.

For example, consider that you have a list of tasks that are each given an estimated time of completion in minutes. If you wanted to complete as many tasks in a period of time as possible, you would order the tasks based on a min-heap, so that the tasks with the least required completion time would be the first element. Each time you complete a task, you would remove the top element, and get the next element that is at the top of the heap.