-1
$\begingroup$

I want to implement a heap using the stack data structure. I have searched a lot on the internet. But I do not get any clue how to implement it.

Can you please help me to implement a heap using the stack data structure? The pseudo-code is well enough. I can implement the rest.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Sounds more challenging than the other way around. Please add, for the purpose of this question, the operations stack provides as well as those required from heap. Add property requirements as needed. $\endgroup$ – greybeard Nov 16 '19 at 9:17
  • 1
    $\begingroup$ Why do you want to do this? I'm finding it hard to see why you wouldn't just implement a heap as a heap or in an array, unless it's a homework exercise. $\endgroup$ – David Richerby Nov 16 '19 at 9:50
  • $\begingroup$ It is previous admission test question of my university which I want to solve $\endgroup$ – Sagor Nov 16 '19 at 12:51
  • $\begingroup$ Please mention which heap operations need to be implemented and which stack operations are available. It might not be possible to implement all the standard min-heap operations (including insert) if only one stack is available for storage. $\endgroup$ – Ashwin Ganesan Nov 18 '19 at 9:33
0
$\begingroup$

The question is a bit vague on the meaning of "using the stack data structure" but I'm going to take an educated guess on a possible implementation. I'll also be assuming that we are interested in a min-heap, that the stack support the push, pop, and top operations, and that the min-heap should support the make-heap, push, pop, and top operations.

The data structure consists of single stack $S$ that will contain the elements of the heap.

Make-heap$(A)$: To build a heap from a set of elements $A$, sort $A$ in nonincreasing order and push the elements one by one into $S$ (according to their order). In this way the last element to be pushed into the stack will be one of the minimums of $A$. This requires $O(|A| \log |A|)$ time.

Top: Return the top element of $S$ (in $O(1)$ time).

Pop: Pop the top element $x$ from $S$ (in $O(1)$ time). Return $x$.

Push$(x)$: To push a new element $x$ into the min-heap proceed as follows: create a new temporary stack $T$; while the top element $y$ of $S$ is smaller than $x$, pop $y$ from $S$ and push it into $T$; Finally, push $x$ into $S$ and iteratively pop the elements from $T$ while pushing them into $S$. When $T$ is empty you are done. Sadly, this requires $O(|S|)$ time in the worst case.

|cite|improve this answer
$\endgroup$

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.