Implementando uma fila de prioridade eficiente usando apenas pilhas

Question

É possível implementar uma fila de prioridade eficiente (tão eficiente quanto um heap) usando apenas a estrutura de dados da pilha?

A eficiência usual para uma fila de prioridade implementada usando um heap é:

• pegue min - $O(1)$
• extrair min - $O(\logn)$
• adicionar - $O(\logn)$

Seria possível fazer algo com a mesma complexidade utilizando apenas pilhas?

Quero implementar A* (que usa uma fila de prioridade para priorizar nós) como um algoritmo de localização de caminhos dentro do Minecraft, mas o Minecraft não permite acesso aleatório, e a estrutura dinâmica mais eficiente que pode ser implementada nele é uma pilha.

Answer 1

Infelizmente, não é possível.A ordem que você extraia itens da pilha só depende da ordem em que são pressionadas, independentemente dos valores desses itens;Uma fila de prioridade precisa de itens a serem removidos em uma ordem que depende do valor dos itens.

Answer 2

Você pode fazer uma representação perfeita de filas de prioridade usando estrutura de dados heaps (binária), usando-a você pode implementar pilhas e filas ...

Nas filas prioritárias é uma questão de preferência, não do princípio FILO como nas pilhas.

Você pode encontrar tudo isso em Cormen et al., Introdução aos Algoritmos, 3ª edição.

ok, a implementação de filas de prioridade usando heaps está relacionada à propriedade do heap, max_heap ou min_heap, então Min_priority_queue pode ser implementado usando min_heap usando os procedimentos usados ​​para heaps como BUILD_HEAP() primeiro, MAX_HEAPIFY(), INCREASE_KEY(), INSERTION e ELIMINAÇÃO.

observe que o próprio heap (binário) é um objeto de matriz que pode ser mostrado como uma árvore de pesquisa binária quase completa ...

para implementação de pilha (há código psudo)

class Stack 
    Inner class Element 
       int priority   // priority of the element.
       Key element    // the element it self

    MAX_PRIORITY_QUEUE<Element> queue;
    next_priority = 0;

    void push(Key x) // value of the pushed element
        q.push(Element(next_priority++, x))

    Key pop() 
        // as popping some element the next push must take its place
        next_priority-- 
        return queue.pop().element

Para implementar a fila usando fila de prioridade (HEAP) é o mesmo, mas a prioridade diminui uma após a outra.