Implement a stack API using only a heap. A stack implements the following methods:

• push(item), which adds an element to the stack
• pop(), which removes and returns the most recently added element (or throws an error if there is nothing on the stack)

Recall that a heap has the following operations:

• push(item), which adds a new key to the heap
• pop(), which removes and returns the max value of the heap

To implement a stack using only a heap, you can use a max heap and maintain a counter to ensure that the order of elements is preserved. Here’s an example implementation in Python, Java, and JavaScript using the heapq module (Python), PriorityQueue (Java), and BinaryHeap (JavaScript):

Python:

import heapq
class MaxHeap:
    def __init__(self):
        self.heap = []
        self.counter = 0
    def push(self, item):
        heapq.heappush(self.heap, (-self.counter, item))
        self.counter += 1
    def pop(self):
        if not self.heap:
            raise IndexError("pop from an empty stack")
        _, item = heapq.heappop(self.heap)
        return item
class StackUsingHeap:
    def __init__(self):
        self.max_heap = MaxHeap()
    def push(self, item):
        self.max_heap.push(item)
    def pop(self):
        return self.max_heap.pop()
# Example usage:
stack = StackUsingHeap()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.pop())  # Output: 2
print(stack.pop())  # Output: 1

Java:

import java.util.PriorityQueue;
class MaxHeap {
    private PriorityQueue<Element> heap = new PriorityQueue<>((a, b) -> Integer.compare(b.counter, a.counter));
    private int counter = 0;
    public void push(int item) {
        heap.offer(new Element(item, counter++));
    }
    public int pop() {
        if (heap.isEmpty()) {
            throw new IndexOutOfBoundsException("pop from an empty stack");
        }
        return heap.poll().value;
    }
    private static class Element {
        int value;
        int counter;
        public Element(int value, int counter) {
            this.value = value;
            this.counter = counter;
        }
    }
}
class StackUsingHeap {
    private MaxHeap maxHeap = new MaxHeap();
    public void push(int item) {
        maxHeap.push(item);
    }
    public int pop() {
        return maxHeap.pop();
    }
}
// Example usage:
StackUsingHeap stack = new StackUsingHeap();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop());  // Output: 3
System.out.println(stack.pop());  // Output: 2
System.out.println(stack.pop());  // Output: 1

Javascript:

class MaxHeap {
    constructor() {
        this.heap = [];
        this.counter = 0;
    }
    push(item) {
        this.heap.push({ value: item, counter: this.counter++ });
        this.heap.sort((a, b) => b.counter - a.counter);
    }
    pop() {
        if (this.heap.length === 0) {
            throw new Error("pop from an empty stack");
        }
        return this.heap.pop().value;
    }
}
class StackUsingHeap {
    constructor() {
        this.maxHeap = new MaxHeap();
    }
    push(item) {
        this.maxHeap.push(item);
    }
    pop() {
        return this.maxHeap.pop();
    }
}
// Example usage:
const stack = new StackUsingHeap();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());  // Output: 3
console.log(stack.pop());  // Output: 2
console.log(stack.pop());  // Output: 1