[API Proposal]: Add a DequeueEnqueue method to the PriorityQueue Type

[RyanThomas73]

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.

[ghost]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

Issue Details

---

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

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> : IEnumerable<T>
{
        /// <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.

Author:	RyanThomas73
Assignees:	-
Labels:	api-suggestion, area-System.Collections
Milestone:	-

[krwq]

Proposal looks good to me. Note we're not sure when this will get picked up by API review. Assuming it gets approved are you interested in creating PR with implementation and tests?

[krwq]

Schedule is here: https://apireview.net/ - if you offer help I can bump milestone to 8.0 to increase priority

[teo-tsirpanis]

Should we also have a TryDequeueEnqueue variant?

[RyanThomas73]

Should we also have a TryDequeueEnqueue variant?

It's an option. Seems like it could be ambiguous on what the behavior would be though; e.g. would it still enqueue if there was nothing to dequeue first? Also, unlike the DequeueEnqueue signature, I wouldn't expect a significant performance difference with checking using a sequential call to TryPeek first.

Proposal looks good to me. Note we're not sure when this will get picked up by API review. Assuming it gets approved are you interested in creating PR with implementation and tests?

Yes I can put together an implementation and tests PR.

[krwq]

Ok, you're now somewhere in the middle of the list up for review (I'm guessing it will take at most couple of weeks), you can update the proposal with TryDequeEnqueue and similar, make sure to be consistent with remainder of the APIs

[vslee]

Seems like it could be ambiguous on what the behavior would be though; e.g. would it still enqueue if there was nothing to dequeue first?

Perhaps TryDequeEnqueue() could take an additional bool parameter which specifies whether to enqueue if there was nothing to dequeue first?

[krwq]

another option is to simply throw, if you're calling that API rather than just enqueue you most likely have bug in your app

[eiriktsarpalis]

@RyanThomas73 for completeness, could you point out a couple of use cases/algorithms where using extract-then-insert is beneficial?

[eiriktsarpalis]

Should we also have a TryDequeueEnqueue variant?

This method seems redundant. A queue.Count > 0 check should suffice to verify that the operation will succeed.

[RyanThomas73]

@RyanThomas73 for completeness, could you point out a couple of use cases/algorithms where using extract-then-insert is beneficial?

Hi Eric. Expanding on my background information/example, one common use case is when the heap/priority queue needs to be kept within a fixed initial size/max size and the additional elements added in as the next min is dequeued.

public record ListNode(ListNode? Next, int Value);
ListNode producerOne = ... get producer data ...
ListNode producerTwo = ... get producer data ...

var initialElements = new List<(ListNode Element, int Priority)>();

// Limit the queue to the first 200 inputs from the producers
while (initialElements.Count <= 200 
    && (producerOne is not null || producerTwo is not null))
{
    // build initial elements, limited to the first 200 elements 
}

var priorityQueue = new PriorityQueue<ListNode, int>(initialElements);

while (priorityQueue.TryPeek(out var peekedElement, out _))
{
    // Each time we dequeue an element and have a next element to enqueue 
    // we want to use DequeueEnqueue which gives better performance than a Dequeue() followed by a sequential Enqueue()
    var minElement = peekedElement.Next != null
        ? priorityQueue.DequeueEnqueue(peekedElement.Next, peekedElement.Next.Value)
        : priorityQueue.Dequeue();
        
    // ... consumer logic that uses minElement ....
}

[vslee]

Should we also have a TryDequeueEnqueue variant?

This method seems redundant. A queue.Count > 0 check should suffice to verify that the operation will succeed.

What if the contents of the queue changes between the queue.Count > 0 check and the calling of DequeueEnqueue()?

[stephentoub]

What if the contents of the queue changes between the queue.Count > 0 check and the calling of DequeueEnqueue()?

Then a non-thread-safe collection is being mutated concurrently erroneously.

[RyanThomas73]

@krwq
Should I create a PR now or wait until the API proposal review has happened first?

@eiriktsarpalis
I was looking through the micro-benchmarks to see if there were PriorityQueue benchmarks for EnqueueDequeue(..); if so I figured I'd add corresponding benchmarks for the inverse DequeueEnqueue(..).

I was hoping you could clarify the intention of this benchmark:
https://github.com/dotnet/performance/blob/b905d2cc8fed5e40c5e2789365aab5f7c8eb5d38/src/benchmarks/micro/libraries/System.Collections/PriorityQueue/Perf_PriorityQueue.cs#L57.

Do you know if it is/was intended to serve as a sequential operations comparison for the K_Max_Elements() benchmark? If so should the sequential operations benchmark be updated to have the same fixed size k and loop/iterator ranges? Would there be value in moving the fixed queue size benchmarks into a separate benchmark class and defining the sequential dequeue/enqueue as the benchmark baseline?

[eiriktsarpalis]

Should I create a PR now or wait until the API proposal review has happened first?

Please wait until and if the API proposal has been approved.

Do you know if it is/was intended to serve as a sequential operations comparison for the K_Max_Elements() benchmark? If so should the sequential operations benchmark be updated to have the same fixed size k and loop/iterator ranges?

The two benchmarks are independent and aren't intended for direct comparison. The purpose of these benchmarks is detecting possible performance regressions, so we generally try to avoid changing them once they have been added.

[bartonjs]

Video

• We're unclear on how useful this method would be, but assuming there's value it looks good as proposed.

namespace System.Collections.Generic;

public class PriorityQueue<TElement, TPriority>
{
    public TElement DequeueEnqueue(TElement element, TPriority priority);
}

[eiriktsarpalis]

@RyanThomas73 API has been approved as proposed, feel free to open a PR contributing the implementation.