Приоритетная очередь в .Net [закрыто]

216

Я ищу .NET реализацию приоритетной очереди или структуры данных кучи

Приоритетные очереди - это структуры данных, которые обеспечивают большую гибкость, чем простая сортировка, поскольку они позволяют новым элементам входить в систему через произвольные интервалы. Гораздо более выгодно вставить новое задание в приоритетную очередь, чем пересортировать все при каждом поступлении.

Очередь с основным приоритетом поддерживает три основные операции:

  • Вставка (Q, X). Получив элемент x с ключом k, вставьте его в очередь приоритетов Q.
  • Найти-Minimum (Q). Вернуть указатель на элемент, значение ключа которого меньше, чем любой другой ключ в очереди приоритетов Q.
  • Удаление-Минимум (Q). Удалить элемент из очереди приоритетов Q, ключ которого минимален

Если я не смотрю в неправильном месте, там нет ни одного в структуре. Кто-нибудь знает о хорошем, или я должен свернуть свой собственный?

Даг МакКлин
источник
34
К вашему сведению, я разработал простую в использовании, высоко оптимизированную очередь приоритетов C #, которую можно найти здесь . Он был разработан специально для приложений поиска пути (A * и т. Д.), Но должен отлично работать и для любого другого приложения. Я бы опубликовал это как ответ, но вопрос недавно был закрыт ...
BlueRaja - Дэнни Пфлюгофт
1
ParallelExtensionsExtras имеет код
VoteCoffee,
Бесстыдно представить PriorityQueue , как часть усилий по переносу параллельного API Java на .net для Spring.Net. Это и куча, и очередь с полной общей поддержкой. Двоичный файл можно скачать здесь .
Кеннет Сюй
@ BlueRaja-DannyPflughoeft Не могли бы вы добавить ответ?
Мафу
1
Просто подведу итог. В .net нет ни структуры данных кучи, ни ядра .net. Хотя пользователи Array.Sort это для больших количеств. Существуют внутренние реализации .
Артём

Ответы:

44

Мне нравится , используя OrderedBagи OrderedSetклассы в PowerCollections в качестве приоритетных очередей.

Бен Хоффштейн
источник
60
OrderedBag / OrderedSet выполняют больше работы, чем необходимо, они используют красно-черное дерево вместо кучи.
Дэн Бериндей
3
@DanBerindei: не нужно работать, если вам нужно выполнить текущий расчет (удалить старые элементы), куча поддерживает только удаление min или max
Svisstack
69

Вам может понравиться IntervalHeap из библиотеки C5 Generic Collection . Цитировать руководство пользователя

Класс IntervalHeap<T>реализует интерфейс IPriorityQueue<T>с использованием интервальной кучи, хранящейся в виде массива пар. Операции FindMin и FindMax, а также метод доступа get индексатора занимают время O (1). Операции DeleteMin, DeleteMax, Add и Update и метод set-accessor индексатора занимают время O (log n). В отличие от обычной очереди приоритетов, интервальная куча предлагает как минимальные, так и максимальные операции с одинаковой эффективностью.

API достаточно прост

> var heap = new C5.IntervalHeap<int>();
> heap.Add(10);
> heap.Add(5);
> heap.FindMin();
5

Установите из Nuget https://www.nuget.org/packages/C5 или GitHub https://github.com/sestoft/C5/

Jaras
источник
3
Это выглядит очень солидной библиотекой и включает 1400 модульных тестов.
ECC-Dan
2
Я пытался использовать его, но у него есть серьезные недостатки. IntervalHeap не имеет встроенной концепции приоритета и вынуждает вас реализовать IComparable или IComparer, делая его отсортированной коллекцией, а не «Приоритетом». Что еще хуже, нет прямого способа обновить приоритет какой-либо предыдущей записи !!!
Мортеза Хосрави
52

Вот моя попытка .NET кучи

public abstract class Heap<T> : IEnumerable<T>
{
    private const int InitialCapacity = 0;
    private const int GrowFactor = 2;
    private const int MinGrow = 1;

    private int _capacity = InitialCapacity;
    private T[] _heap = new T[InitialCapacity];
    private int _tail = 0;

    public int Count { get { return _tail; } }
    public int Capacity { get { return _capacity; } }

    protected Comparer<T> Comparer { get; private set; }
    protected abstract bool Dominates(T x, T y);

    protected Heap() : this(Comparer<T>.Default)
    {
    }

    protected Heap(Comparer<T> comparer) : this(Enumerable.Empty<T>(), comparer)
    {
    }

    protected Heap(IEnumerable<T> collection)
        : this(collection, Comparer<T>.Default)
    {
    }

    protected Heap(IEnumerable<T> collection, Comparer<T> comparer)
    {
        if (collection == null) throw new ArgumentNullException("collection");
        if (comparer == null) throw new ArgumentNullException("comparer");

        Comparer = comparer;

        foreach (var item in collection)
        {
            if (Count == Capacity)
                Grow();

            _heap[_tail++] = item;
        }

        for (int i = Parent(_tail - 1); i >= 0; i--)
            BubbleDown(i);
    }

    public void Add(T item)
    {
        if (Count == Capacity)
            Grow();

        _heap[_tail++] = item;
        BubbleUp(_tail - 1);
    }

    private void BubbleUp(int i)
    {
        if (i == 0 || Dominates(_heap[Parent(i)], _heap[i])) 
            return; //correct domination (or root)

        Swap(i, Parent(i));
        BubbleUp(Parent(i));
    }

    public T GetMin()
    {
        if (Count == 0) throw new InvalidOperationException("Heap is empty");
        return _heap[0];
    }

    public T ExtractDominating()
    {
        if (Count == 0) throw new InvalidOperationException("Heap is empty");
        T ret = _heap[0];
        _tail--;
        Swap(_tail, 0);
        BubbleDown(0);
        return ret;
    }

    private void BubbleDown(int i)
    {
        int dominatingNode = Dominating(i);
        if (dominatingNode == i) return;
        Swap(i, dominatingNode);
        BubbleDown(dominatingNode);
    }

    private int Dominating(int i)
    {
        int dominatingNode = i;
        dominatingNode = GetDominating(YoungChild(i), dominatingNode);
        dominatingNode = GetDominating(OldChild(i), dominatingNode);

        return dominatingNode;
    }

    private int GetDominating(int newNode, int dominatingNode)
    {
        if (newNode < _tail && !Dominates(_heap[dominatingNode], _heap[newNode]))
            return newNode;
        else
            return dominatingNode;
    }

    private void Swap(int i, int j)
    {
        T tmp = _heap[i];
        _heap[i] = _heap[j];
        _heap[j] = tmp;
    }

    private static int Parent(int i)
    {
        return (i + 1)/2 - 1;
    }

    private static int YoungChild(int i)
    {
        return (i + 1)*2 - 1;
    }

    private static int OldChild(int i)
    {
        return YoungChild(i) + 1;
    }

    private void Grow()
    {
        int newCapacity = _capacity*GrowFactor + MinGrow;
        var newHeap = new T[newCapacity];
        Array.Copy(_heap, newHeap, _capacity);
        _heap = newHeap;
        _capacity = newCapacity;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return _heap.Take(Count).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

public class MaxHeap<T> : Heap<T>
{
    public MaxHeap()
        : this(Comparer<T>.Default)
    {
    }

    public MaxHeap(Comparer<T> comparer)
        : base(comparer)
    {
    }

    public MaxHeap(IEnumerable<T> collection, Comparer<T> comparer)
        : base(collection, comparer)
    {
    }

    public MaxHeap(IEnumerable<T> collection) : base(collection)
    {
    }

    protected override bool Dominates(T x, T y)
    {
        return Comparer.Compare(x, y) >= 0;
    }
}

public class MinHeap<T> : Heap<T>
{
    public MinHeap()
        : this(Comparer<T>.Default)
    {
    }

    public MinHeap(Comparer<T> comparer)
        : base(comparer)
    {
    }

    public MinHeap(IEnumerable<T> collection) : base(collection)
    {
    }

    public MinHeap(IEnumerable<T> collection, Comparer<T> comparer)
        : base(collection, comparer)
    {
    }

    protected override bool Dominates(T x, T y)
    {
        return Comparer.Compare(x, y) <= 0;
    }
}

Некоторые тесты:

[TestClass]
public class HeapTests
{
    [TestMethod]
    public void TestHeapBySorting()
    {
        var minHeap = new MinHeap<int>(new[] {9, 8, 4, 1, 6, 2, 7, 4, 1, 2});
        AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray());

        minHeap = new MinHeap<int> { 7, 5, 1, 6, 3, 2, 4, 1, 2, 1, 3, 4, 7 };
        AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray());

        var maxHeap = new MaxHeap<int>(new[] {1, 5, 3, 2, 7, 56, 3, 1, 23, 5, 2, 1});
        AssertHeapSort(maxHeap, maxHeap.OrderBy(d => -d).ToArray());

        maxHeap = new MaxHeap<int> {2, 6, 1, 3, 56, 1, 4, 7, 8, 23, 4, 5, 7, 34, 1, 4};
        AssertHeapSort(maxHeap, maxHeap.OrderBy(d => -d).ToArray());
    }

    private static void AssertHeapSort(Heap<int> heap, IEnumerable<int> expected)
    {
        var sorted = new List<int>();
        while (heap.Count > 0)
            sorted.Add(heap.ExtractDominating());

        Assert.IsTrue(sorted.SequenceEqual(expected));
    }
}
Охад Шнайдер
источник
2
Я бы порекомендовал очистить значение кучи в ExtractDominating, чтобы оно не удерживало указанный объект дольше, чем необходимо (потенциальная утечка памяти). Для типов значений это, очевидно, не имеет значения.
Wout
5
Хорошо, но вы не можете удалить предметы из него? Это важная операция для приоритетных очередей.
Том Ларкворти
Похоже, базовый объект является массивом. Разве это не было бы лучше как бинарное дерево?
Груньон Шафто
1
@OhadSchneider очень, очень круто, я просто смотрел на минимальную кучу и пытался сделать то, что вы сделали, сделав его универсальным, а минимальную или максимальную кучу! отличная работа
Гилад
1
@Gilad IEqualityComparer<T>будет недостаточно, поскольку это скажет вам только, равны ли два элемента, в то время как вам нужно знать отношение между ними (кто меньше / больше). Это правда, что я мог бы использовать, IComparer<T>хотя ...
Охад Шнайдер
23

вот тот, который я только что написал, возможно, он не так оптимизирован (просто использует отсортированный словарь), но прост для понимания. Вы можете вставлять объекты разных видов, поэтому нет общих очередей.

using System;
using System.Diagnostics;
using System.Collections;
using System.Collections.Generic;

namespace PrioQueue
{
    public class PrioQueue
    {
        int total_size;
        SortedDictionary<int, Queue> storage;

        public PrioQueue ()
        {
            this.storage = new SortedDictionary<int, Queue> ();
            this.total_size = 0;
        }

        public bool IsEmpty ()
        {
            return (total_size == 0);
        }

        public object Dequeue ()
        {
            if (IsEmpty ()) {
                throw new Exception ("Please check that priorityQueue is not empty before dequeing");
            } else
                foreach (Queue q in storage.Values) {
                    // we use a sorted dictionary
                    if (q.Count > 0) {
                        total_size--;
                        return q.Dequeue ();
                    }
                }

                Debug.Assert(false,"not supposed to reach here. problem with changing total_size");

                return null; // not supposed to reach here.
        }

        // same as above, except for peek.

        public object Peek ()
        {
            if (IsEmpty ())
                throw new Exception ("Please check that priorityQueue is not empty before peeking");
            else
                foreach (Queue q in storage.Values) {
                    if (q.Count > 0)
                        return q.Peek ();
                }

                Debug.Assert(false,"not supposed to reach here. problem with changing total_size");

                return null; // not supposed to reach here.
        }

        public object Dequeue (int prio)
        {
            total_size--;
            return storage[prio].Dequeue ();
        }

        public void Enqueue (object item, int prio)
        {
            if (!storage.ContainsKey (prio)) {
                storage.Add (prio, new Queue ());
              }
            storage[prio].Enqueue (item);
            total_size++;

        }
    }
}
kobi7
источник
это не позволяет несколько записей с одинаковым приоритетом, хотя?
Letseatlunch
2
оно делает. когда вы вызываете метод Enqueue, он добавляет элемент в очередь с таким приоритетом. (часть в else в методе enqueue.)
kobi7
5
Что вы подразумеваете под «это не совсем приоритетная очередь в смысле информатики»? Что из этого заставляет вас верить, что это не приоритетная очередь?
Марк Байерс
14
-1 за неиспользование дженериков.
cdiggins
2
Одним из самых больших преимуществ Heap / PriorityQueue является сложность O (1) минимального / максимального извлечения, то есть операция Peek. И здесь речь идет о настройке перечислителя, цикле for и т. Д. Почему !? Кроме того, операция «Enqueue» вместо того, чтобы быть O (logN) - еще одна ключевая особенность кучи, имеет один O (longN) свайп из-за «ContainsKey», второй (снова O (longN)), чтобы добавить запись очереди (если необходимо), третий для фактического извлечения очереди (строка хранилища [prio]) и, наконец, линейное добавление в эту очередь. Это действительно безумно в свете реализации основного алгоритма.
Джонан Георгиев
10

Я нашел его Джулиана Бакнолла в его блоге здесь - http://www.boyet.com/Articles/PriorityQueueCSharp3.html

Мы немного изменили его, чтобы элементы с низким приоритетом в очереди со временем «всплыли», чтобы они не страдали от голода.

Дункан
источник
9

Как упоминалось в Microsoft Collections for .NET , Microsoft написала (и поделилась в сети) 2 внутренних класса PriorityQueue в .NET Framework. Их код доступен для тестирования.

РЕДАКТИРОВАТЬ: Как заметил @ mathusum-mut, есть ошибка в одном из внутренних классов Microsoft PriorityQueue (сообщество SO, конечно, предоставило исправления для него): Ошибка во внутреннем PriorityQueue <T> от Microsoft?

водослив
источник
10
Ошибка была обнаружена в одной из реализаций здесь: stackoverflow.com/questions/44221454/…
MathuSum Mut
ооо! Я вижу, что все эти классы PriorityQueue<T>в общем источнике Microsoft помечены internalспецификатором доступа. Поэтому они используются только внутренними функциональными возможностями фреймворка. Они не доступны для общего потребления, просто ссылаясь windowsbase.dllна проект C #. Единственный способ - скопировать общий источник в сам проект внутри файла класса.
RBT
7
class PriorityQueue<T>
{
    IComparer<T> comparer;
    T[] heap;
    public int Count { get; private set; }
    public PriorityQueue() : this(null) { }
    public PriorityQueue(int capacity) : this(capacity, null) { }
    public PriorityQueue(IComparer<T> comparer) : this(16, comparer) { }
    public PriorityQueue(int capacity, IComparer<T> comparer)
    {
        this.comparer = (comparer == null) ? Comparer<T>.Default : comparer;
        this.heap = new T[capacity];
    }
    public void push(T v)
    {
        if (Count >= heap.Length) Array.Resize(ref heap, Count * 2);
        heap[Count] = v;
        SiftUp(Count++);
    }
    public T pop()
    {
        var v = top();
        heap[0] = heap[--Count];
        if (Count > 0) SiftDown(0);
        return v;
    }
    public T top()
    {
        if (Count > 0) return heap[0];
        throw new InvalidOperationException("优先队列为空");
    }
    void SiftUp(int n)
    {
        var v = heap[n];
        for (var n2 = n / 2; n > 0 && comparer.Compare(v, heap[n2]) > 0; n = n2, n2 /= 2) heap[n] = heap[n2];
        heap[n] = v;
    }
    void SiftDown(int n)
    {
        var v = heap[n];
        for (var n2 = n * 2; n2 < Count; n = n2, n2 *= 2)
        {
            if (n2 + 1 < Count && comparer.Compare(heap[n2 + 1], heap[n2]) > 0) n2++;
            if (comparer.Compare(v, heap[n2]) >= 0) break;
            heap[n] = heap[n2];
        }
        heap[n] = v;
    }
}

легко.

Шиму Донг
источник
13
Иногда я вижу такие вещи, как for (var n2 = n / 2; n > 0 && comparer.Compare(v, heap[n2]) > 0; n = n2, n2 /= 2) heap[n] = heap[n2]; и задаюсь вопросом, стоило ли это одной подкладки
1
@DustinBreakey личный стиль :)
Shimou Dong
3
но определенно не читается для других. Подумайте о написании кода, который не оставляет вопросительный знак плавающим над головой разработчика.
alzaimar
3

Используйте транслятор с Java на C # в реализации Java (java.util.PriorityQueue) в платформе Java Collections или более разумно используйте алгоритм и основной код и вставьте его в собственный класс C #, который соответствует структуре C # Collections API для очередей или хотя бы коллекций.

JeeBee
источник
Это работает, но, к сожалению, IKVM не поддерживает дженерики Java, поэтому вы теряете безопасность типов.
Механическая улитка
8
Не существует такого понятия, как «дженерики Java», когда вы имеете дело с скомпилированным байт-кодом Java. IKVM не может поддержать это.
Марк
3

AlgoKit

Я написал библиотеку с открытым исходным кодом под названием AlgoKit , доступную через NuGet . Это содержит:

  • Неявные d-арные кучи (ArrayHeap),
  • Биноминальные кучи ,
  • Спаривание кучи .

Код был тщательно протестирован. Я определенно рекомендую вам попробовать.

пример

var comparer = Comparer<int>.Default;
var heap = new PairingHeap<int, string>(comparer);

heap.Add(3, "your");
heap.Add(5, "of");
heap.Add(7, "disturbing.");
heap.Add(2, "find");
heap.Add(1, "I");
heap.Add(6, "faith");
heap.Add(4, "lack");

while (!heap.IsEmpty)
    Console.WriteLine(heap.Pop().Value);

Почему эти три кучи?

Оптимальный выбор реализации сильно зависит от ввода - как Ларкин, Сен и Тарьян показывают в эмпирическом исследовании приоритетных очередей , arXiv: 1403.0252v1 [cs.DS] . Они проверили неявные кучи d-ary, кучи спаривания, кучи Фибоначчи, кучи биномиального типа, кучи d-ary, кучи спаривания рангов, кучи землетрясений, кучи нарушений, слабые кучи с ослабленным рангом и строгие кучи Фибоначчи.

AlgoKit имеет три типа кучи, которые оказались наиболее эффективными среди протестированных.

Подсказка на выбор

Для относительно небольшого числа элементов вам, вероятно, будет интересно использовать неявные кучи, особенно четвертичные кучи (неявные 4-х разрядные). В случае работы с кучами больших размеров амортизированные структуры, такие как биномиальные кучи и пары кучи, должны работать лучше.

Патрик Голембиовски
источник
1

Недавно у меня возникла та же проблема, и в итоге я создал пакет NuGet для этого.

Это реализует стандартную очередь приоритетов на основе кучи. Он также имеет все обычные тонкости коллекций BCL: ICollection<T>и IReadOnlyCollection<T>реализацию, пользовательскую IComparer<T>поддержку, возможность указать начальную емкость, аDebuggerTypeProxy сделать коллекцию легче работать с в отладчике.

Также есть Inline версия пакета, которая просто устанавливает один файл .cs в ваш проект (полезно, если вы хотите избежать использования внешне видимых зависимостей).

Более подробная информация доступна на странице GitHub .

ChaseMedallion
источник
1

Простая реализация Max Max Heap.

https://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/MaxHeap.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace AlgorithmsMadeEasy
{
    class MaxHeap
    {
        private static int capacity = 10;
        private int size = 0;
        int[] items = new int[capacity];

        private int getLeftChildIndex(int parentIndex) { return 2 * parentIndex + 1; }
        private int getRightChildIndex(int parentIndex) { return 2 * parentIndex + 2; }
        private int getParentIndex(int childIndex) { return (childIndex - 1) / 2; }

        private int getLeftChild(int parentIndex) { return this.items[getLeftChildIndex(parentIndex)]; }
        private int getRightChild(int parentIndex) { return this.items[getRightChildIndex(parentIndex)]; }
        private int getParent(int childIndex) { return this.items[getParentIndex(childIndex)]; }

        private bool hasLeftChild(int parentIndex) { return getLeftChildIndex(parentIndex) < size; }
        private bool hasRightChild(int parentIndex) { return getRightChildIndex(parentIndex) < size; }
        private bool hasParent(int childIndex) { return getLeftChildIndex(childIndex) > 0; }

        private void swap(int indexOne, int indexTwo)
        {
            int temp = this.items[indexOne];
            this.items[indexOne] = this.items[indexTwo];
            this.items[indexTwo] = temp;
        }

        private void hasEnoughCapacity()
        {
            if (this.size == capacity)
            {
                Array.Resize(ref this.items,capacity*2);
                capacity *= 2;
            }
        }

        public void Add(int item)
        {
            this.hasEnoughCapacity();
            this.items[size] = item;
            this.size++;
            heapifyUp();
        }

        public int Remove()
        {
            int item = this.items[0];
            this.items[0] = this.items[size-1];
            this.items[this.size - 1] = 0;
            size--;
            heapifyDown();
            return item;
        }

        private void heapifyUp()
        {
            int index = this.size - 1;
            while (hasParent(index) && this.items[index] > getParent(index))
            {
                swap(index, getParentIndex(index));
                index = getParentIndex(index);
            }
        }

        private void heapifyDown()
        {
            int index = 0;
            while (hasLeftChild(index))
            {
                int bigChildIndex = getLeftChildIndex(index);
                if (hasRightChild(index) && getLeftChild(index) < getRightChild(index))
                {
                    bigChildIndex = getRightChildIndex(index);
                }

                if (this.items[bigChildIndex] < this.items[index])
                {
                    break;
                }
                else
                {
                    swap(bigChildIndex,index);
                    index = bigChildIndex;
                }
            }
        }
    }
}

/*
Calling Code:
    MaxHeap mh = new MaxHeap();
    mh.Add(10);
    mh.Add(5);
    mh.Add(2);
    mh.Add(1);
    mh.Add(50);
    int maxVal  = mh.Remove();
    int newMaxVal = mh.Remove();
*/
Бхараткумар V
источник
-3

Следующая реализация PriorityQueueиспользует SortedSetиз системной библиотеки.

using System;
using System.Collections.Generic;

namespace CDiggins
{
    interface IPriorityQueue<T, K> where K : IComparable<K>
    {
        bool Empty { get; }
        void Enqueue(T x, K key);
        void Dequeue();
        T Top { get; }
    }

    class PriorityQueue<T, K> : IPriorityQueue<T, K> where K : IComparable<K>
    {
        SortedSet<Tuple<T, K>> set;

        class Comparer : IComparer<Tuple<T, K>> {
            public int Compare(Tuple<T, K> x, Tuple<T, K> y) {
                return x.Item2.CompareTo(y.Item2);
            }
        }

        PriorityQueue() { set = new SortedSet<Tuple<T, K>>(new Comparer()); }
        public bool Empty { get { return set.Count == 0;  } }
        public void Enqueue(T x, K key) { set.Add(Tuple.Create(x, key)); }
        public void Dequeue() { set.Remove(set.Max); }
        public T Top { get { return set.Max.Item1; } }
    }
}
cdiggins
источник
6
SortedSet.Add завершится ошибкой (и вернет false), если у вас уже есть элемент в наборе с таким же «приоритетом», как у элемента, который вы пытаетесь добавить. Итак ... если A.Compare (B) == 0 и A уже есть в списке, ваша функция PriorityQueue.Enqueue завершится сбоем.
Джозеф
Имейте в виду, чтобы объяснить, что есть T xи K key? Я предполагаю, что это хитрость для разрешения дублирования T x, и мне нужно сгенерировать уникальный ключ (например, UUID)?
Тарик Нугрохотомо