Learn Computer Science
Developing a more interesting World
"Computer science is no more about computers than astronomy is about telescopes."
Edsger Dijkstra
Free beginner - intermediate level computer science tutorials
Priority Collections
Tutoring > Data Structures > Priority Collections
Usually in a queue, it's first come, first served. What if we could assign an order to elements in a queue based on how important they are? Using an ADT in the form of a priority queue, we can.
What is a priorty queue?
A priority queue is the same as a regular queue or stack other than it has a priority assigned to each element.
Elements with a higher priority are served (visited) before elements with a lower priority. This is a max-priority queue. A min-priority queue will visit the elements in ascending order of priority value. Elements with the same priority are served in the order that they appear in the queue.
So if we have this queue with these priorities: {1, 2, 3, 4, 5} we would visit the elements in this order:
5, 4, 3, 2, 1.
You could look at a stack or a queue as a kind of priority queue, with the priority of the top-most element (in a stack) and the priority of the first element put into the queue (in a queue) having the highest priority.
Binary heap trees
A heap tree is a complete binary tree that:
-
has a root of higher priority than it's childern (if a max-heap tree). OR
-
has a root of lower priority than it's children (if a min-heap tree).
-
the left and right sub-trees of the root are heap trees.
The heap tree's last (deepest level) does not have to be complete, that is, it doesn't have to be perfectly complete. The picture shows a complete binary max heap. Note that the last level is not complete, and the bigger the priority, the higher the node.
Binary heaps are produced using a binary tree.
Dijkstra's algorithm
Dijkstra's algorithm finds the shortest path between nodes in a graph and produces a shortest path tree.
Given a node in a graph, the algorthim finds the shortest path between that node and every other node in the graph, one node at a time.
This is guaranteed to find the shortest path and so is a solution guaranteed algorithm. It is also totally correct as it always produces the right outcome.
Dijkstra's algorithm can make use of a priority queue in the form of a heap tree. More on Dijkstra's algorithm in Graphs.