[API Proposal]: Add a DequeueEnqueue method to the PriorityQueue Type #75070
Description
Background and motivation
When working with d-ary heap structures, insert-then-extract and extract-then-insert operations can be done which are generally more efficient than sequentially executing the separate insert/extract operations.
The existing PriorityQueue<TElement, TPriority> collection type has an existing method signature named EnqueueDequeue which is an optimized implementation of the insert-then-extract operation. It does not have an api method for the inverse extract-then-insert operation.
The term pop-push is sometimes used for the extract-then-insert implementation. The python implementation calls this heapreplace: https://docs.python.org/3/library/heapq.html#heapq.heapreplace
The optimized extract-then-insert operation is ideal for use cases where each dequeue operation is likely or guaranteed to be followed by an enqueue operation.
One example usage of the new method would be a scenario where the elements of the priority queue represent nodes from different linked lists. If each operation to dequeue the next element is always followed by inserting the next node that is pointed at, the optimized extract-then-insert would be the preferable choice.
API Proposal
namespace System.Collections.Generic;
public class PriorityQueue<TElement, TPriority>
{
/// <summary>
/// Removes the minimal element and then immediately adds the specified element with associated priority to the <see cref="PriorityQueue{TElement, TPriority}"/>,
/// </summary>
/// <param name="element">The element to add to the <see cref="PriorityQueue{TElement, TPriority}"/>.</param>
/// <param name="priority">The priority with which to associate the new element.</param>
/// <returns>The minimal element removed before performing the enqueue operation.</returns>
/// <remarks>
/// Implements an extract-then-insert heap operation that is generally more efficient
/// than sequencing Dequeue and Enqueue operations
/// </remarks>
public TElement DequeueEnqueue(TElement element, TPriority priority)
{
if (_size == 0)
throw new InvalidOperationException(SR.InvalidOperation_EmptyQueue);
(TElement Element, TPriority Priority) root = _nodes[0];
if (_comparer == null)
{
if (Comparer<TPriority>.Default.Compare(priority, root.Priority) > 0)
{
MoveDownDefaultComparer((element, priority), 0);
}
else
{
_nodes[0] = (element, priority);
}
}
else
{
if (_comparer.Compare(priority, root.Priority) > 0)
{
MoveDownCustomComparer((element, priority), 0);
}
else
{
_nodes[0] = (element, priority);
}
}
_version++;
return root.Element;
}
}API Usage
public record ListNode(ListNode? Next, int Value);
var priorityQueue = new PriorityQueue<ListNode, int>(initialElements);
while (priorityQueue.TryPeek(out var peekedElement, out _))
{
var minElement = peekedElement.Next != null
? priorityQueue.DequeueEnqueue(peekedElement.Next, peekedElement.Next.Value)
: priorityQueue.Dequeue();
// ... logic that uses minElement ....
}Alternative Designs
N/A
Risks
The new method implementation must be correctly optimized in order to achieve better performance than executing the Dequeue() and Enqueue(..) methods sequentially.