A priority queue can be implemented using many of the data structures that we've already studied (an array, a linked list, or a binary search tree (BST)). However, those data structures do not provide the most efficient operations. To make all of the operations very efficient, we'll use a new data structure called a heap.

Implementing priority queues using heaps

A priority queue is a data structure that stores priorities (comparable values) and perhaps associated information. A priority queue supports inserting new priorities and removing/returning the highest priority. When a priority queue is implemented using a heap, the worst-case times for both insert and removeMax are logarithmic in the number of values in the priority queue.

Examples:

  • Djikstra’s Algorithm
    • One of the fastest algorithms for solving this problem has a runtime of O(E*V*Log(V)), where E is the number of road segments, and V is the number of intersections.
    • The algorithm would take about 2 seconds to find the shortest path in a city with 10,000 intersections, and 20,000 road segments (there are usually about 2 road segments per intersection).