B MODIFIABLE PRIORITY QUEUES
Several algorithms in this book, such as Dijkstra’s algorithm and A* search, use an augmented priority queue that allows the program to modify the priority of existing elements. For completeness, this appendix describes and provides the code for this data structure.
While many standard heap implementations support the addition and removal of items, they often do not support efficiently changing an item’s priority. We’ll provide a brief overview of heaps, then define a small extension to the standard priority queue that uses a dictionary to map each item’s location in the heap. This mapping allows us to efficiently ...
Get Graph Algorithms the Fun Way now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
