3
$\begingroup$

Is it possible to implement an efficient priority queue (as efficient as a heap) only using the stack data structure?

The usual efficiency for a priority queue which is implemented using a heap is :

  • get min - $O(1)$
  • extract min - $O(\log n)$
  • add - $O(\log n)$

Would it be possible to do something with the same complexity using only stacks?

I want to implement A* (which uses a priority queue to prioritize nodes) as a pathfinding algorithm inside Minecraft, but Minecraft doesn't allow random access, and the most efficent dynamic structure that can be implemented in it is a stack.

$\endgroup$
3
  • 2
    $\begingroup$ Can you share the motivation for why we'd want to do that? If you encountered this somewhere, what's the context or source where you encountered this task? $\endgroup$ – D.W. Apr 7 '20 at 19:25
  • 2
    $\begingroup$ I want to implement A* (which uses a priority queue to prioritize nodes) as a pathfinding algorithm inside Minecraft, but Minecraft doesn't allow random access, and the most efficent dynamic structure that can be implemented in it is a stack. $\endgroup$ – Command Master Apr 8 '20 at 7:01
  • $\begingroup$ Neat! Thanks for sharing that. $\endgroup$ – D.W. Apr 8 '20 at 17:07
2
$\begingroup$

Unfortunately, it's not possible. The order you extract items from the stack depends only on the order they're pushed, regardless of the values in those items; a priority queue needs items to be removed in an order that depends on the value of the items.

$\endgroup$
4
  • $\begingroup$ even if multiple stacks are allowed? $\endgroup$ – Command Master Apr 9 '20 at 4:53
  • $\begingroup$ @CommandMaster, you need to specify the model of computation (about what computation we're allowed to do, e.g., to decide which stack to push on), but given what information you've provided so far, I expect so, yes. $\endgroup$ – D.W. Apr 9 '20 at 6:31
  • $\begingroup$ If you have n stacks of size 1, and can use an index which stack to use, then obviously you can do anything that you can do with an array, including implementing a priority queue. $\endgroup$ – gnasher729 Apr 9 '20 at 16:00
  • $\begingroup$ @gnasher729, absolutely, but the poster said that the programming model doesn't allow random access, so that's not possible here. $\endgroup$ – D.W. Apr 9 '20 at 23:08
0
$\begingroup$

You can do such a perfect representation of priority queues using (binary) heaps data structure, using it you can implement stacks and queues...

In priority queues it's a matter of preference, not FILO principle like in stacks.

You can find all of this in Cormen et al., Introduction to Algorithms, 3rd edition.

okay, implementation of priority queues using heaps is related to the property of the heap, max_heap or min_heap so Min_priority_queue can be implemented using min_heap by using the procedures used for heaps like BUILD_HEAP() first, MAX_HEAPIFY(), INCREASE_KEY(), INSERTION and DELETION.

note that (binary)heap itself is an array object can be shown as a nearly complete binary search tree...

for stack implementation (there is psudo code)

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

To implement queue using priority queue(HEAP) the same but the priority decreases one after another.

$\endgroup$
3
  • $\begingroup$ Can you explain how to obtain such a representation? $\endgroup$ – Yuval Filmus Apr 9 '20 at 9:28
  • $\begingroup$ For stacks we keep adding elements in increasing priority as when you pop some element it will return the element with largest key... as follows $\endgroup$ – Mahmoud Kamal Apr 9 '20 at 20:34
  • $\begingroup$ How do you plan to implement efficiently without arrays or random access? Can you show pseudocode? Please don't answer in the comments -- edit your answer. Thank you! $\endgroup$ – D.W. Apr 9 '20 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.