From the READEM:
Heap with compile-time parameteric branching factor, also known as d-ary heap.
Note that there is a binary heap in the standard library if you do not want
to use this module:
std.PriorityQueue
Performance notes:
- Heaps with higher branching factors are faster in inserting element and slower in removing elements. If you are going to insert and then remove all elements a binary heap is already quite fast and a branching factor higher than 5 is probably going to be less optimal. The optimal branching factor is usually around 4.
- The branching factor here is compile time to enable the optimization of division by the compiler, see e.g: Montgomery modular multiplication.
- If case you need to pop the top element and insert a new one, or vice
versa, use the
replaceTop
member function to avoid paying the extra cost of “bubbling-up” the inserted element.
You must log in or register to comment.