We have a task for implementing a priority queue for task scheduling: #379. Discussion showed that a good option for our requirements would be a pairing heap.
There is an abandoned PR that implements it: #584. It implements PairingHeap class, but it's interface should be reworked, as described in PR discussions. The algorithm itself was not carefully reviewed yet.
Also, the class should be adjusted to the new approach that we used for containers: the code should be split into template class PairingHeap and non-template class PairingHeapImpl. Here is an example of this approach: 1, 2.
Benchmark part of the task is optional and can be skipped or done separately.
Please use the linked PR as a base branch unless you want to re-write the whole class from scratch.
We have a task for implementing a priority queue for task scheduling: #379. Discussion showed that a good option for our requirements would be a pairing heap.
There is an abandoned PR that implements it: #584. It implements PairingHeap class, but it's interface should be reworked, as described in PR discussions. The algorithm itself was not carefully reviewed yet.
Also, the class should be adjusted to the new approach that we used for containers: the code should be split into template class PairingHeap and non-template class PairingHeapImpl. Here is an example of this approach: 1, 2.
Benchmark part of the task is optional and can be skipped or done separately.
Please use the linked PR as a base branch unless you want to re-write the whole class from scratch.