Learn C++ STL

Lesson 5 of 9 · priority_queue: The Biggest One Comes Out First

Module 7 · priority_queue: The Biggest One Comes Out First

Under the Hood: The Heap Inside a vector, the Sift Arithmetic and make_heap

ProReading

Kenji's lab scheduler keeps its maintenance tasks in a priority_queue of pointers. When the mouse starts failing, he raises its urgency from 2 to 9 through its pointer. The next pops still serve the printer at 7 and the projector at 6 before the mouse. Maria asks the question this lesson answers: "But why did the heap not notice?" To see why, we open the heap and read its vector.

Checking what this lesson needs for you…

What is inside Under the Hood: The Heap Inside a vector, the Sift Arithmetic and make_heap

  1. A priority_queue is a vector and three heap calls
  2. The tree is arithmetic on slot numbers
  3. A push climbs; a pop sends a hole down
  4. make_heap in O(n): most slots sit near the bottom
  5. Why there is no erase, no decrease-key and no iterator
  6. What it costs in memory
  7. The performance lab