仅使用堆栈实现有效的优先级队列

Question

是否可以仅使用堆栈数据结构实现有效的优先级队列（与堆有效）？

使用堆实现的优先级队列的效率为：

• 获取min - $ o（1）$
• 提取物min - $ o（\ log n）$
• add - $ o（\ log n）$

是否有可能使用堆栈的相同复杂性进行操作？

我希望实现一个*（使用优先级队列到优先级排序节点）作为MINECraft内的路径限制算法，但MINECraft不允许随机访问，并且可以在它中实现的最有效的动态结构是堆栈。

Answer 1

不幸的是，这是不可能的。您从堆栈中提取项目的顺序只取决于它们被推动的顺序，而不管这些项目中的值如何;优先级队列需要以取决于项目值的顺序删除的项目。

Answer 2

您可以使用（二进制）堆数据结构进行这样一个优先级队列的完美表示，使用它可以实现堆栈和队列...

在优先级队列中，这是一个偏好的问题，而不是堆栈中的filo原理。

您可以在Cormen等人中找到所有这些。，算法简介，第3版。

好的，使用堆的优先级队列的实现与堆，max_heap或min_heap的属性有关，因此可以使用min_heap使用min_heap使用build_heap（）first，max_heafify（），compound_key（）的过程来实现Min_Proiry_Queue。，插入和删除。

注意（二进制）堆本身是一个数组对象，可以显示为几乎完整的二进制搜索树...

用于堆栈实现（有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

.

使用优先级队列（堆）实现队列，但优先级续达到另一个。