See also
ACPL: Histogram1D
ACPL: Histogram2D
BinaryHeap as array implemente priority queue. Good for way finding graph algorithmen like dijkstra.
See source code and more code examples at ACPL Binary Heap
#include <core/util/StringStream.hpp>
#include <core/util/BinaeryHeap.hpp>
using namespace acpl;
using ID = int;
int main() {
// We use a min-heap. The highest priority is the lowest number
BinaryHeap<double> heap;
std::map<ID, std::string_view> tasks;
// heap insert returns a ID assiciated with the priority
tasks.insert({heap.insert(3.0), "clear drains"});
tasks.insert({heap.insert(4.0), "feet cat"});
tasks.insert({heap.insert(5.0), "make tea"});
tasks.insert({heap.insert(1.0), "solve RC tasks"});
tasks.insert({heap.insert(2.0), "tax return"});
tasks.insert({heap.insert(10.0), "clean room"});
tasks.insert({heap.insert(99.0), "wash dog"});
std::cout << heap.size() << " tasks" << newline;
std::cout << "Most important: ";
auto firstToDo = heap.extract_minimum();
std::cout << tasks[firstToDo.second] << " with priority " << firstToDo.first << newline;
std::cout << heap.size() << " tasks left" << newline;
std::cout << "\nNext 3 tasks:" << newline;
for(int i=0; i < 3; i++) {
auto task = heap.extract_minimum();
std::cout << tasks[task.second] << " with priority " << task.first << newline;
}
std::cout <<"make task 'wash the dog' the new first with priority -1" << newline;
ID lastInsertedID = tasks.rbegin()->first;
heap.decrease_key(lastInsertedID, -1);
std::cout << "\nThe remaining tasks:" << newline;
while(not heap.empty()) {
auto task = heap.extract_minimum();
std::cout << tasks[task.second] << " with priority " << task.first << newline;
}
std::cout << heap.size() << " tasks left" << newline;
}
7 tasks Most important: solve RC tasks with priority 1 6 tasks left Next 3 tasks: tax return with priority 2 clear drains with priority 3 feet cat with priority 4 make task 'wash the dog' the new first with priority -1 The remaining tasks: wash dog with priority -1 make tea with priority 5 clean room with priority 10 0 tasks left