Balanced priority queue (weighted queue)
In a regular priority queue entry with priority N is taken before all the entries with priority M (given N > M).
Sometimes, however, 3-priority entry should not beat one hundred of 1-priority items. It seems natural to introduce a double-linked list of weighted nodes, where newly inserted node can come in front of a limited number of nodes with a total weight less then a weight of a new node.
Illustration. Given a stream of nodes with weights:
[1a, 2, 1b, 3, 1c, 1d, 4, 1e]
weighted queue intermediate states would be:
[1a]
[2, 1a]
[2, 1a, 1b]
[2, 3, 1a, 1b]
[2, 3, 1a, 1b, 1c]
[2, 3, 1a, 1b, 1c, 1d]
[2, 3, 1a, 4, 1b, 1c, 1d]
[2, 3, 1a, 4, 1b, 1c, 1d, 1e]
In such queue priority “N” means skipping N items of priority 1.