Ebook Data structures and algorithms in C++: Part 2

Part 2 book “Data structures and algorithms in C++” has contents: Heaps and priority queues, hash tables, maps, and skip lists, search trees, sorting, sets, and selection, strings and dynamic programming, graph algorithms, memory management and B-Trees. | i i “main” — 2011/1/13 — 9:10 — page 321 — #343 i i Chapter 8 Heaps and Priority Queues Contents The Priority Queue Abstract Data Type . . . . . . . . Keys, Priorities, and Total Order Relations . . . . . . Comparators . . . . . . . . . . . . . . . . . . . . . . The Priority Queue ADT . . . . . . . . . . . . . . . A C++ Priority Queue Interface . . . . . . . . . . . . Sorting with a Priority Queue . . . . . . . . . . . . . The STL priority queue Class . . . . . . . . . . . . . Implementing a Priority Queue with a List . . . . . . A C++ Priority Queue Implementation using a List . Selection-Sort and Insertion-Sort . . . . . . . . . . . Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . The Heap Data Structure . . . . . . . . . . . . . . . Complete Binary Trees and Their Representation . . Implementing a Priority Queue with a Heap . . . . . C++ Implementation . . . . . . . . . . . . . . . . . Heap-Sort . . . . . . . . . . . . . . . . . . . . . . . Bottom-Up Heap Construction . . . . . . . . . . Adaptable Priority Queues . . . . . . . . . . . . . . . A List-Based Implementation . . . . . . . . . . . . . Location-Aware Entries . . . . . . . . . . . . . . . . Exercises . . . . . . . . . . . . . . . . . . . . . . . . . ⋆ 322 322 324 327 328 329 330 331 333 335 337 337 340 344 349 351 353 357 358 360 361 i i i i i i “main” — 2011/1/13 — 9:10 — page 322 — #344 i i 322 Chapter 8. Heaps and Priority Queues The Priority Queue Abstract Data Type A priority queue is an abstract data type for storing a collection of prioritized elements that supports arbitrary element insertion but supports removal of elements in order of priority, that is, the element with first priority can be removed at any time. This ADT is fundamentally different from the position-based data structures such as stacks, queues, deques, lists, and even .