Why this matters
Many programs keep a line of waiting items and always handle the most urgent one next. A route planner that finds the shortest road to every town works this way. It keeps a list of towns to visit, always takes the town with the smallest distance so far, and checks whether a road gives a shorter distance to any town still in the list.
The last step is the problem in this lesson. A town already waiting in the list may get a shorter distance. Its place in the line should move up, but the normal C++ tool for a line of urgent items cannot change an item that is already inside it.
This lesson shows how to build a heap that can change an item's priority. A heap is a tree stored in an array where the most urgent item sits at the top. The version here also remembers where each item is stored, so it can find an item and move it in O(log n) time. Big-O notation describes how work grows as the number of items n grows. O(log n) means that doubling the number of items adds only about one more step of work.
The lesson builds on the heap basics from the earlier lessons in this module: the array layout, sift-up and sift-down. Those are covered in the module's first two lessons, so here they are only recalled where needed.
The problem with a plain priority queue
C++ has std::priority_queue. It keeps items in a heap, and top() gives the largest item in constant time by default, so smallest-first needs std::greater. It has push() and pop(), but no way to change an item that is already inside.
Here is a small example. Three jobs wait in a queue with priorities: job A has 50, job B has 30 and job C has 40. A smaller number means more urgent, so B goes first. Now you learn that job A should have priority 10. The std::priority_queue cannot find A inside the heap and change its number. The usual workaround is lazy deletion: push a second entry (10, A) and leave the old entry (50, A) in the queue. Later, when the old entry comes out, the program sees that it is out of date and throws it away.
Lazy deletion works, but it has two costs. The queue holds more entries than there are jobs, and the program must check every popped entry to see whether it is stale. In a route planner with many roads, the queue can grow much larger than the number of towns.
An indexed heap avoids both costs. Each job appears once. When its priority drops, the program finds the job's slot and moves it up.
Counting the extra work on a real graph
The same five-node graph from Example 2 later in this lesson shows the cost. The program below runs Dijkstra with a plain std::priority_queue and lazy deletion. It counts the entries it pushes, the largest size the queue reaches and the stale entries it pops. A stale entry is one whose distance is larger than the best distance already known for its node.
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
struct Edge {
int to;
int weight;
};
int main() {
std::vector<std::vector<Edge>> graph(5);
graph[0] = {{1, 4}, {2, 1}};
graph[1] = {{3, 1}};
graph[2] = {{1, 2}, {3, 5}};
graph[3] = {{4, 3}};
using Entry = std::pair<int, int>; // (distance, node)
std::priority_queue<Entry, std::vector<Entry>, std::greater<>> pq;
std::vector<int> dist(5, std::numeric_limits<int>::max());
int pushes = 1;
int largest_heap = 1;
int stale_pops = 0;
dist[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) {
++stale_pops;
continue;
}
for (const Edge& e : graph[u]) {
int candidate = d + e.weight;
if (candidate < dist[e.to]) {
dist[e.to] = candidate;
pq.push({candidate, e.to});
++pushes;
if (static_cast<int>(pq.size()) > largest_heap) largest_heap = static_cast<int>(pq.size());
}
}
}
std::cout << "lazy approach: pushes " << pushes << ", largest heap size " << largest_heap
<< ", stale entries popped " << stale_pops << '\n';
for (int v = 0; v < 5; ++v) std::cout << "node " << v << " distance " << dist[v] << '\n';
return 0;
}The output is:
lazy approach: pushes 7, largest heap size 3, stale entries popped 2
node 0 distance 0
node 1 distance 3
node 2 distance 1
node 3 distance 4
node 4 distance 7The lazy queue received 7 pushes for 5 nodes. At its largest it held 3 entries, and it popped 2 stale entries that had to be skipped. The distances are the same as in Example 2.
The indexed heap does the same job with 5 pushes, one per node, plus 2 decrease_key calls. Its largest size is 2. You can check this by following Example 2 from the top: after node 0 is popped, the heap holds nodes 1 and 2. Node 2 is then popped, leaving only node 1, and node 3 is added, so the heap holds 2 nodes at most.
The gap is small on five nodes. On a larger map, every lowered distance adds another entry to the lazy queue, and that extra work is what the indexed heap avoids.
The idea: remember where each item sits
An indexed heap uses items that have numbers from 0 to n minus 1. A town number or a job number works well. Three arrays hold the state.
The first array, called heap_ in the code below, stores the item ids in heap order. Slot 0 is the top. The children of slot i sit in slots 2 times i plus 1 and 2 times i plus 2. The parent of slot i sits in slot (i minus 1) divided by 2, using whole-number division.
The second array, pos_, answers the question "where is item id stored?" It stores the slot number for each id. If pos_[3] is 0, then item 3 is at the top.
The third array, prio_, stores the priority of each id.
Keeping pos_ correct is the key rule. Every time two slots swap, the program must update pos_ for both items that moved.
Worked example: the array after four pushes
Start with an empty heap. Push item 0 with priority 50, item 1 with priority 30, item 2 with priority 40 and item 3 with priority 20. Each push adds the item at the end of the array, then moves it up while it is smaller than its parent. This is called sift-up.
After the four pushes the state is:
slot 0 1 2 3
id 3 1 2 0
prio 20 30 40 50
pos[0] = 3 pos[1] = 1 pos[2] = 2 pos[3] = 0As a tree, the same heap looks like this:
3 (20)
/ \
1 (30) 2 (40)
/
0 (50)Every parent is smaller than or equal to its children. The top item, id 3 with priority 20, is the most urgent.
Now call decrease_key(2, 10). The program looks up pos[2], which is 2, sets the priority of item 2 to 10, and sifts it up. Its parent is slot 0, which holds priority 20. Because 10 is smaller, the two slots swap. Item 2 is now at the top and pos is updated for both items. The new top is id 2.
The class
The full class is below. It is a complete, working header file. Save it as indexed_heap.hpp, because the examples below include it. Each method is short, and the comments explain only what is not obvious from the code.
#pragma once
#include <cstddef>
#include <limits>
#include <utility>
#include <vector>
class IndexedMinHeap {
public:
explicit IndexedMinHeap(std::size_t capacity)
: pos_(capacity, kAbsent), prio_(capacity, 0) {}
bool empty() const { return heap_.empty(); }
std::size_t size() const { return heap_.size(); }
bool contains(int id) const { return pos_[id] != kAbsent; }
int priority(int id) const { return prio_[id]; }
int top() const { return heap_[0]; }
void push(int id, int priority) {
prio_[id] = priority;
heap_.push_back(id);
pos_[id] = heap_.size() - 1;
sift_up(heap_.size() - 1);
}
int pop() {
int top_id = heap_[0];
swap_slots(0, heap_.size() - 1);
heap_.pop_back();
pos_[top_id] = kAbsent;
if (!heap_.empty()) sift_down(0);
return top_id;
}
void decrease_key(int id, int new_priority) {
prio_[id] = new_priority;
sift_up(pos_[id]);
}
private:
static constexpr std::size_t kAbsent = std::numeric_limits<std::size_t>::max();
std::vector<int> heap_;
std::vector<std::size_t> pos_;
std::vector<int> prio_;
bool less_at(std::size_t a, std::size_t b) const {
return prio_[heap_[a]] < prio_[heap_[b]];
}
void swap_slots(std::size_t a, std::size_t b) {
std::swap(heap_[a], heap_[b]);
pos_[heap_[a]] = a;
pos_[heap_[b]] = b;
}
void sift_up(std::size_t i) {
while (i > 0) {
std::size_t parent = (i - 1) / 2;
if (!less_at(i, parent)) break;
swap_slots(i, parent);
i = parent;
}
}
void sift_down(std::size_t i) {
std::size_t n = heap_.size();
while (true) {
std::size_t left = 2 * i + 1;
std::size_t right = left + 1;
std::size_t best = i;
if (left < n && less_at(left, best)) best = left;
if (right < n && less_at(right, best)) best = right;
if (best == i) break;
swap_slots(i, best);
i = best;
}
}
};The class uses std::size_t for slot numbers because a vector's size has that type. The value kAbsent marks an id that is not in the heap. std::numeric_limits gives the largest value of a type, so kAbsent is a number that no real slot can have.
The pop method swaps the top with the last slot, removes the last slot, marks the old top as absent, and then sifts the new top down. Sift-down moves an item toward the bottom by swapping it with its smaller child until neither child is smaller.
The decrease_key method is two lines. It stores the new priority and sifts up from the item's current slot. It does not check that the new priority is lower. That check is the caller's job, and the mistakes section shows what happens when it is missing.
Example 1: push, decrease, pop
The first program is the smallest useful test. It pushes four items, lowers one of them to the top, then pops everything in order.
#include <iostream>
#include "indexed_heap.hpp"
int main() {
IndexedMinHeap h(5);
h.push(0, 50);
h.push(1, 30);
h.push(2, 40);
h.push(3, 20);
std::cout << "top id " << h.top() << " priority " << h.priority(h.top()) << '\n';
h.decrease_key(2, 10);
std::cout << "after decrease_key(2, 10), top id " << h.top() << '\n';
while (!h.empty()) {
int priority = h.priority(h.top());
int id = h.pop();
std::cout << "pop id " << id << " priority " << priority << '\n';
}
return 0;
}The program is compiled with g++ -std=c++20 -Wall and run. The output is:
top id 3 priority 20
after decrease_key(2, 10), top id 2
pop id 2 priority 10
pop id 3 priority 20
pop id 1 priority 30
pop id 0 priority 50The first line matches the array state from the worked example above. The second line shows that the lowered item moved to the top. The pop order is by priority, not by the order of the pushes. Item 0 was pushed first, but it is popped last because its priority is the largest.
The variable priority is read before each pop() call. The method pop() removes the id from the heap, but the priority array still holds the old value. Reading it first keeps the code clear, and it avoids depending on what happens to prio_ after a pop.
Example 2: Dijkstra's shortest paths
Dijkstra's algorithm is the standard way to find the shortest distance from one start node to every other node in a graph with no negative road lengths. A graph is a set of nodes joined by edges. Here each node is a town and each edge is a road with a length.
The algorithm keeps a distance for each node. At the start, the start node has distance 0 and every other node has infinite distance, which here means the largest int. Then it repeats three steps. It pops the closest node from the heap. For each road from that node, it computes the distance through the popped node. If the new distance is shorter, it updates the node. The node is then either added to the heap, if it was not there, or moved up with decrease_key, if it was already waiting.
The example graph has five nodes, numbered 0 to 4, with these roads: 0 to 1 with length 4, 0 to 2 with length 1, 2 to 1 with length 2, 1 to 3 with length 1, 2 to 3 with length 5 and 3 to 4 with length 3.
#include <iostream>
#include <limits>
#include <vector>
#include "indexed_heap.hpp"
struct Edge {
int to;
int weight;
};
std::vector<int> dijkstra(const std::vector<std::vector<Edge>>& graph, int source,
int& decrease_calls) {
const int n = static_cast<int>(graph.size());
constexpr int kInf = std::numeric_limits<int>::max();
std::vector<int> dist(n, kInf);
IndexedMinHeap heap(n);
dist[source] = 0;
heap.push(source, 0);
while (!heap.empty()) {
int u = heap.pop();
for (const Edge& e : graph[u]) {
int candidate = dist[u] + e.weight;
if (candidate >= dist[e.to]) continue;
dist[e.to] = candidate;
if (heap.contains(e.to)) {
heap.decrease_key(e.to, candidate);
++decrease_calls;
} else {
heap.push(e.to, candidate);
}
}
}
return dist;
}
int main() {
std::vector<std::vector<Edge>> graph(5);
graph[0] = {{1, 4}, {2, 1}};
graph[1] = {{3, 1}};
graph[2] = {{1, 2}, {3, 5}};
graph[3] = {{4, 3}};
int decrease_calls = 0;
std::vector<int> dist = dijkstra(graph, 0, decrease_calls);
for (int v = 0; v < static_cast<int>(dist.size()); ++v) {
std::cout << "node " << v << " distance " << dist[v] << '\n';
}
std::cout << "decrease_key calls " << decrease_calls << '\n';
return 0;
}The output is:
node 0 distance 0
node 1 distance 3
node 2 distance 1
node 3 distance 4
node 4 distance 7
decrease_key calls 2Trace the two decrease calls by hand. Node 0 is popped first and pushes node 1 with distance 4 and node 2 with distance 1. Node 2 is popped next. The road from 2 to 1 gives distance 1 + 2 = 3, which is shorter than 4. Node 1 is already in the heap, so the program calls decrease_key(1, 3). That is the first decrease. Later, node 1 is popped with distance 3. The road from 1 to 3 gives 3 + 1 = 4, which is shorter than the 6 that node 3 received from node 2. Node 3 is already in the heap, so the second call is decrease_key(3, 4).
Without the indexed heap, each of those two updates would push a second copy of the node. The lazy approach would then pop stale copies later. Here the heap never holds two copies of the same node.
Notice that the code never needs a separate list of finished nodes. Each road has a length of zero or more, so a node that has already been popped can never get a shorter distance later. The check candidate >= dist[e.to] already skips it.
Example 3: many random operations
The third program is harder. It does 2000 random operations on a heap of 50 items: push an item that is not waiting, lower the priority of an item that is waiting, or pop the top. After each pop, it finds the smallest priority among the waiting items by scanning all of them, and it checks that the popped item had that priority. This is slow, but it is simple and it is a correct answer to compare against.
#include <iostream>
#include <limits>
#include <random>
#include <vector>
#include "indexed_heap.hpp"
int main() {
constexpr int kItems = 50;
constexpr int kOps = 2000;
std::mt19937 rng(12345);
std::uniform_int_distribution<int> pick_item(0, kItems - 1);
std::uniform_int_distribution<int> pick_priority(0, 1000);
std::uniform_int_distribution<int> pick_action(0, 2);
IndexedMinHeap heap(kItems);
std::vector<bool> live(kItems, false);
std::vector<int> prio(kItems, 0);
int pops = 0;
int decreases = 0;
bool all_matched = true;
for (int op = 0; op < kOps; ++op) {
int id = pick_item(rng);
int p = pick_priority(rng);
int action = pick_action(rng);
if (action == 0 && !live[id]) {
heap.push(id, p);
live[id] = true;
prio[id] = p;
} else if (action == 1 && live[id] && p <= prio[id]) {
heap.decrease_key(id, p);
prio[id] = p;
++decreases;
} else if (action == 2 && !heap.empty()) {
int expected = std::numeric_limits<int>::max();
for (int i = 0; i < kItems; ++i) {
if (live[i] && prio[i] < expected) expected = prio[i];
}
int popped = heap.pop();
if (!live[popped] || prio[popped] != expected) all_matched = false;
live[popped] = false;
++pops;
}
}
std::cout << "operations " << kOps << ", decrease_key calls " << decreases
<< ", pops " << pops << '\n';
std::cout << "every pop was a smallest priority: " << (all_matched ? "yes" : "no") << '\n';
std::cout << "items still in heap " << heap.size() << '\n';
return 0;
}The output on GCC 15 with the libstdc++ library is:
operations 2000, decrease_key calls 34, pops 576
every pop was a smallest priority: yes
items still in heap 8The random numbers come from a generator with a fixed seed, so the run repeats. The exact distribution numbers can differ between C++ libraries, so the counts may differ on another system. The line "every pop was a smallest priority: yes" should be the same everywhere, because it depends only on the heap being correct.
The check compares priorities, not ids. Two items can share a priority, and either one is a correct answer.
The third example also shows why the live array exists. The indexed heap does not check whether an id is already in it, so the program checks that itself before each push and each decrease. The mistakes section describes what happens without that check.
Common mistakes
Lowering a priority to a bigger number
The method decrease_key only sifts up. If the new number is larger, the item should move down, and decrease_key does not do that. Here is a program that makes this mistake.
#include <iostream>
#include "indexed_heap.hpp"
int main() {
IndexedMinHeap h(3);
h.push(0, 10);
h.push(1, 20);
h.push(2, 30);
h.decrease_key(0, 50);
std::cout << "top id " << h.top() << " priority " << h.priority(h.top()) << '\n';
std::cout << "id 1 priority " << h.priority(1) << '\n';
return 0;
}The output is:
top id 0 priority 50
id 1 priority 20The program runs without an error, but the answer is wrong. Item 0 now has priority 50 and still sits at the top, while item 1 with priority 20 should be the top. There is no error message, so this kind of bug is easy to miss. Use a separate method, such as increase_key, that sifts down, or check in the caller that the new value is lower.
Using an id that is out of range
The arrays are sized by the capacity passed to the constructor. An id of 7 in a heap of capacity 5 is outside the arrays. The next program asks about id 7.
#include <iostream>
#include "indexed_heap.hpp"
int main() {
IndexedMinHeap h(5);
h.push(0, 10);
std::cout << h.contains(7) << '\n';
return 0;
}Compiled with -D_GLIBCXX_ASSERTIONS, which asks the C++ library to check indexing, the program stops with this message. The text is shortened here at the start, and the key part is at the end:
Assertion '__n < this->size()' failed.Without that flag the check is missing, and the program reads memory outside the array. That behaviour is undefined, which means the C++ standard allows anything. The program may print a wrong answer or crash much later, far from the real mistake. Check ids against the capacity in the calling code, or use the assertion flag while testing.
Passing a string instead of an id
The ids must be integers. A common slip is to pass a name such as "a". The compiler stops with an error before the program runs.
#include "indexed_heap.hpp"
int main() {
IndexedMinHeap h(5);
h.push("a", 3);
return 0;
}The first lines of the compiler message are:
mistake_string.cpp:5:12: error: invalid conversion from 'const char*' to 'int' [-fpermissive]
5 | h.push("a", 3);
| ^~~
indexed_heap.hpp:18:19: note: initializing argument 1 of 'void IndexedMinHeap::push(int, int)'The fix is to map each name to an integer id first, using a std::unordered_map<std::string, int>, and pass the id to the heap.
Pushing an id that is already waiting
The class does not check whether an id is already in the heap. Calling push for an id that is waiting adds the id to heap_ a second time, and pos_ then points to only one of the two slots. Later calls to decrease_key or pop can then give wrong results. Call contains(id) first, and call decrease_key for a waiting id instead of push.
Forgetting to update pos during a swap
The most serious mistake is in the class itself. If swap_slots changes heap_ but not pos_, then decrease_key moves the wrong item. Nothing crashes, and the answers look plausible for a while. When you write a change to this class, run Example 3 again. Random tests like it catch this kind of bug quickly.
Practice
Exercise 1. Start with an empty IndexedMinHeap of capacity 3. Push id 0 with priority 5, id 1 with priority 3 and id 2 with priority 4. In what order do the ids come out of pop()?
Show the answer
The order is 1, 2, 0. The priorities are 3, 4 and 5, and pop() always returns the smallest.
Exercise 2. Start with the three pushes from exercise 1, but do not pop yet. Call decrease_key(0, 1). What is top() now, and why?
Show the answer
The top is id 0. Its priority is now 1, which is smaller than every other priority, so sift-up moves it from its slot to the top.
Exercise 3. Why does decrease_key call sift_up and not sift_down?
Show the answer
Lowering a priority can only make an item smaller than its parent. It can never make it larger than its children, so the only possible violation is with the parent above it. Sift-up is enough to fix that.
Exercise 4. In the mistake example that lowers id 0 to 50, the heap ends with id 0 at the top and priority 50. Explain why item 1 with priority 20 is not at the top.
Show the answer
decrease_key stored the bigger value 50 and then called sift_up. Sift-up does nothing here, because 50 is not smaller than anything. Item 0 was already at the top, so it stays there. The real fix is to move item 0 down, which decrease_key never does.
Exercise 5. Dijkstra's loop never pushes the same node twice. Explain why it is safe to skip the check for nodes that are already finished.
Show the answer
Every road length is zero or more. When a node is popped, its distance is the shortest possible. Any later road into that node gives a distance at least as large as the node's distance, so the check candidate >= dist[e.to] always skips it. The heap never needs to receive a finished node again.
Summary
- A plain
std::priority_queuecannot change an item that is already inside it, so programs usually push a duplicate instead. - An indexed heap stores the heap array, the slot of each id in
pos_, and each id's priority inprio_. decrease_keyfinds the item throughpos_, stores the new priority and sifts the item up in O(log n) time.- Every swap must update
pos_for both items, or the heap gives wrong answers. - The method does not check that the new priority is lower, so the caller must.
- Dijkstra's algorithm uses
decrease_keywhenever it finds a shorter road to a node that is already waiting.