Fila prioritária em .Net [fechado]

216

Estou procurando uma implementação .NET de uma fila de prioridade ou estrutura de dados de heap

As filas prioritárias são estruturas de dados que fornecem mais flexibilidade do que a classificação simples, porque permitem que novos elementos entrem no sistema em intervalos arbitrários. É muito mais econômico inserir um novo trabalho em uma fila prioritária do que reorganizar tudo em cada chegada.

A fila de prioridade básica suporta três operações principais:

  • Inserir (Q, x). Dado um item x com a chave k, insira-o na fila de prioridade Q.
  • Encontre-Mínimo (Q). Retorne um ponteiro para o item cujo valor da chave é menor que qualquer outra chave na fila de prioridade Q.
  • Excluir-mínimo (Q). Remova o item da fila de prioridade Q cuja chave é mínima

A menos que eu esteja procurando no lugar errado, não há um na estrutura. Alguém está ciente de uma boa ou devo fazer o meu próprio?

Doug McClean
fonte
34
Para sua informação, desenvolvi uma fila de prioridade C # altamente otimizada e fácil de usar, que pode ser encontrada aqui . Foi desenvolvido especificamente para aplicativos de busca de caminhos (A *, etc.), mas também deve funcionar perfeitamente para qualquer outro aplicativo. Gostaria de postar isso como resposta, mas a pergunta foi encerrada recentemente ...
BlueRaja - Danny Pflughoeft
1
ParallelExtensionsExtras tem uma ConcurrentPriorityQueue code.msdn.microsoft.com/ParExtSamples
VoteCoffee
Apresente descaradamente o PriorityQueue , como parte do esforço para portar a API simultânea java para .net para Spring.Net. É uma pilha e uma fila com suporte genérico completo. O binário pode ser baixado aqui .
Kenneth Xu
@ BlueRaja-DannyPflughoeft Você poderia adicionar uma resposta?
Mafu
1
Apenas para resumir. Não há estrutura de dados de heap no .net, nem no núcleo do .net agora. Embora Array.Sort usuários para grandes números. Existem implementações internas .
Artyom

Respostas:

44

Eu gosto de usar as classes OrderedBage OrderedSetno PowerCollections como filas prioritárias.

Ben Hoffstein
fonte
60
OrderedBag / OrderedSet faz mais trabalho do que o necessário, eles usam uma árvore vermelho-preta em vez de uma pilha.
21119 Dan Berindei
3
@DanBerindei: trabalho não é necessário se você precisa fazer correr cálculo (excluir itens antigos), montão suportam apenas apagar min ou max
Svisstack
69

Você pode gostar do IntervalHeap da C5 Generic Collection Library . Para citar o guia do usuário

A classe IntervalHeap<T>implementa a interface IPriorityQueue<T>usando um heap de intervalo armazenado como uma matriz de pares. As operações FindMin e FindMax, e o acessador de obtenção do indexador, levam o tempo O (1). As operações DeleteMin, DeleteMax, Add and Update e o acessador de conjunto do indexador levam tempo O (log n). Ao contrário de uma fila de prioridade comum, um heap de intervalo oferece operações mínimas e máximas com a mesma eficiência.

A API é bastante simples

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

Instale a partir do Nuget https://www.nuget.org/packages/C5 ou GitHub https://github.com/sestoft/C5/

jaras
fonte
3
Parece uma biblioteca muito sólida e vem com 1.400 testes de unidade.
ECC-Dan
2
Eu tentei usá-lo, mas tem falhas sérias. O IntervalHeap não possui um conceito interno de prioridade e obriga a implementar o IComparable ou o IComparer, tornando-o uma coleção classificada e não uma "Prioridade". Pior ainda, não existe uma maneira direta de atualizar a prioridade de alguma entrada anterior !!!
morteza khosravi
52

Aqui está minha tentativa de um heap .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;
    }
}

Alguns testes:

[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));
    }
}
Ohad Schneider
fonte
2
Eu recomendaria limpar o valor da pilha em ExtractDominating, para que ele não se prenda ao objeto referenciado por mais tempo que o necessário (possível vazamento de memória). Para tipos de valor, obviamente não é de interesse.
Wout
5
Bom, mas você não pode remover itens dele? Essa é uma operação importante para filas prioritárias.
precisa saber é o seguinte
Parece que o objeto subjacente é uma matriz. Isso não seria melhor como uma árvore binária?
Grunion Shaftoe
1
@OhadSchneider muito, muito legal, eu estava olhando min heap e tentei fazer o que você fez, tornando-o genérico e min ou max heap! grande trabalho
Gilad
1
O @ Gilad IEqualityComparer<T>não seria suficiente, pois isso apenas informa se dois itens são iguais, enquanto você precisa conhecer a relação entre eles (quem é menor / maior). É verdade que eu poderia ter usado IComparer<T>...
Ohad Schneider
23

Aqui está um que acabei de escrever, talvez não seja tão otimizado (apenas usa um dicionário classificado), mas simples de entender. você pode inserir objetos de tipos diferentes, para que não haja filas genéricas.

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
fonte
isso não permite várias entradas com a mesma prioridade?
Letseatlunch 16/04
2
faz. quando você chama o método Enfileirar, ele adiciona o item à fila dessa prioridade. (a parte na outra parte do método de enfileiramento.)
kobi7
5
O que você quer dizer com "não é realmente uma fila de prioridade no significado da ciência da computação"? O que faz você acreditar que essa não é uma fila de prioridade?
Mark Byers
14
-1 por não usar genéricos.
Cdggins
2
Um dos maiores benefícios do Heap / PriorityQueue é a complexidade O (1) da extração min / max, ou seja, a operação Peek. E aqui envolve a configuração do enumerador, loop for, etc. Por que !? Além disso, a operação "Enfileirar", em vez de ser O (logN) - outro recurso principal do heap, tem um furto O (longN) devido a "ContainsKey", um segundo (novamente O (longN)) para adicionar a entrada Fila (se necessário), um terceiro para recuperar a fila (a linha de armazenamento [prio]) e, finalmente, uma adição linear a essa fila. Isso é realmente insano à luz da implementação do algoritmo principal.
22816 Jonan Georgiev
9

Conforme mencionado nas Coleções Microsoft para .NET , a Microsoft escreveu (e compartilhou online) 2 classes internas PriorityQueue no .NET Framework. O código deles está disponível para teste.

EDIT: Como comentou @ mathusum-mut, há um bug em uma das classes PriorityQueue internas da Microsoft (a comunidade SO, é claro, forneceu correções para isso): Bug no PriorityQueue interno da Microsoft <T>?

açude
fonte
10
Um bug foi encontrado em uma das implementações aqui: stackoverflow.com/questions/44221454/...
MathuSum Mut
ohh! Eu posso ver que todas essas classes PriorityQueue<T>na fonte compartilhada da Microsoft estão marcadas com internalespecificador de acesso. Portanto, eles são usados ​​apenas pelas funcionalidades internas da estrutura. Eles não estão disponíveis para consumo geral apenas consultando windowsbase.dllum projeto C #. A única maneira é copiar a fonte compartilhada no próprio projeto dentro de um arquivo de classe.
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;
    }
}

fácil.

Shimou Dong
fonte
13
Às vezes eu vejo coisas assim for (var n2 = n / 2; n > 0 && comparer.Compare(v, heap[n2]) > 0; n = n2, n2 /= 2) heap[n] = heap[n2]; e se perguntam se valeu de um revestimento
1
@DustinBreakey personal style :)
Shimou Dong
3
mas definitivamente não é legível para os outros. Considere escrever um código que não deixe um ponto de interrogação flutuando sobre a cabeça do desenvolvedor.
Alzaimar 18/03/19
3

Use um tradutor de Java para C # na implementação Java (java.util.PriorityQueue) na estrutura Java Collections, ou use de forma mais inteligente o algoritmo e o código principal e conecte-o a uma classe C # de sua preferência, que adere à estrutura C # Collections API para filas ou pelo menos coleções.

JeeBee
fonte
Isso funciona, mas infelizmente o IKVM não suporta genéricos Java, então você perde a segurança do tipo.
Caracol mecânico
8
Não existe algo como "Java genéricos" quando você está lidando com bytecode Java compilado. O IKVM não pode suportá-lo.
Mark
3

AlgoKit

Eu escrevi uma biblioteca de código aberto chamada AlgoKit , disponível via NuGet . Contém:

  • Montes implícitos no dia-a-ar (ArrayHeap),
  • Montes binomiais ,
  • Emparelhar pilhas .

O código foi extensivamente testado. Definitivamente, recomendo que você experimente.

Exemplo

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);

Por que esses três montões?

A escolha ideal da implementação é fortemente dependente de entrada - como mostram Larkin, Sen e Tarjan em Um estudo empírico de base sobre filas de prioridade , arXiv: 1403.0252v1 [cs.DS] . Eles testaram pilhas d-árias implícitas, pilhas de emparelhamento, pilhas de Fibonacci, pilhas binomiais, pilhas d-árias explícitas, pilhas de emparelhamentos de classificação, pilhas de terremotos, pilhas de violação, pilhas fracas com descontração e pilhas estritas de Fibonacci.

O AlgoKit apresenta três tipos de pilhas que parecem ser mais eficientes entre as testadas.

Dica sobre a escolha

Para um número relativamente pequeno de elementos, você provavelmente estaria interessado em usar pilhas implícitas, especialmente pilhas quaternárias (4-ário implícito). No caso de operar em tamanhos de heap maiores, as estruturas amortizadas, como pilhas binomiais e pilhas de emparelhamento, devem ter um desempenho melhor.

Patryk Gołębiowski
fonte
1

Eu tive o mesmo problema recentemente e acabei criando um pacote NuGet para isso.

Isso implementa uma fila de prioridade padrão baseada em heap. Ele também tem todas as sutilezas habituais das coleções BCL: ICollection<T>e IReadOnlyCollection<T>implementação, costume IComparer<T>apoio, capacidade de especificar uma capacidade inicial e um DebuggerTypeProxypara fazer a coleta de mais fácil trabalhar com no depurador.

Há também uma versão Inline do pacote que apenas instala um único arquivo .cs no seu projeto (útil se você deseja evitar a dependência externa visível).

Mais informações estão disponíveis na página do github .

ChaseMedallion
fonte
1

Uma implementação simples de 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();
*/
Bharathkumar V
fonte
-3

A seguinte implementação de um PriorityQueueusos SortedSetda biblioteca do sistema.

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
fonte
6
SortedSet.Add falhará (e retornará falso) se você já tiver um item no conjunto com a mesma "prioridade" que o item que você está tentando adicionar. Portanto ... se A.Compare (B) == 0 e A já estiver na lista, sua função PriorityQueue.Enqueue falhará silenciosamente.
Joseph
Mente para explicar o que são T xe K key? Eu estou supondo que este é um truque para permitir duplicar T x, e eu preciso gerar uma chave única (por exemplo, UUID)?
Thariq Nugrohotomo