Algorithms For Dummies

Introducing priority queues

Later in this chapter, you see how to implement Prim’s and Kruskal’s algorithm 

for a minimum spanning tree, and Dijkstra’s algorithm for the shortest path in a 

graph using Python. However, before you can do that, you need a method to find 

the edges with the minimum weight among a set of edges. Such an operation 

implies ordering, and ordering elements costs time. It’s a complex operation, as 

described  in  Chapter  7.  Because  the  examples  repeatedly  reorder  edges,  a  data 

structure called the priority queue comes in handy.

Priority queues rely on heap tree-based data structures that allow fast element 

ordering when you insert them inside the heap. Like the magician’s magic hat, 

priority heaps store edges with their weights and are immediately ready to provide 

you with the inserted edge whose weight is the minimum among those stores.

---

CHAPTER 9