November 2024
Intermediate to advanced
416 pages
11h 11m
English
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 ...