Heap, Stack, and Queue

Three core data structures implemented from scratch, the building blocks behind priority scheduling, undo systems, and task queues that show up everywhere in ML infrastructure.

Problem

Implement the following data structures:

1. Stack, LIFO using a linked list
2. Queue, FIFO using two stacks (amortized O(1) dequeue)
3. Min-Heap, a priority queue with insert and extract-min

Approach

Stack: a singly linked list where push and pop operate on the head. O(1) for both.

Queue via two stacks: enqueue pushes to an inbound stack. Dequeue pops from an outbound stack; when outbound is empty, reverse inbound into outbound. Each element moves at most twice, giving amortized O(1) per operation.

Min-heap: a complete binary tree stored in an array. After insertion, "float" the element up by swapping with its parent while it's smaller. After extraction, move the last element to the root and "sink" it down by swapping with the smaller child.

Implementation

Stack (Linked List)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        node = Node(data)
        node.next = self.top
        self.top = node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def peek(self):
        return self.top.data if self.top else None

Queue (Two Stacks)

class Queue:
    def __init__(self):
        self.inbound = []
        self.outbound = []

    def enqueue(self, data):
        self.inbound.append(data)

    def dequeue(self):
        if not self.outbound:
            while self.inbound:
                self.outbound.append(self.inbound.pop())
        return self.outbound.pop() if self.outbound else None

Min-Heap

class MinHeap:
    def __init__(self):
        self.heap = [0]  # index 0 unused; tree starts at index 1
        self.size = 0

    def insert(self, item):
        self.heap.append(item)
        self.size += 1
        self._float(self.size)

    def pop(self):
        if self.size == 0:
            return None
        root = self.heap[1]
        self.heap[1] = self.heap[self.size]
        self.size -= 1
        self.heap.pop()
        if self.size > 0:
            self._sink(1)
        return root

    def _float(self, k):
        while k // 2 > 0:
            if self.heap[k] < self.heap[k // 2]:
                self.heap[k], self.heap[k // 2] = self.heap[k // 2], self.heap[k]
            k //= 2

    def _sink(self, k):
        while k * 2 <= self.size:
            mc = self._min_child(k)
            if self.heap[k] > self.heap[mc]:
                self.heap[k], self.heap[mc] = self.heap[mc], self.heap[k]
            else:
                break
            k = mc

    def _min_child(self, k):
        if k * 2 + 1 > self.size:
            return k * 2
        return k * 2 if self.heap[k * 2] < self.heap[k * 2 + 1] else k * 2 + 1

Complexity

Structure	Insert	Remove	Peek
Stack	O(1)	O(1)	O(1)
Queue (two stacks)	O(1)	O(1) amortized	,
Min-Heap	O(log n)	O(log n)	O(1)

• Space: O(n) for all three.

Takeaway

Heaps power priority queues in beam search, A* pathfinding, and top-k retrieval. The two-stack queue is a common interview question, but it also shows up in real systems where you need FIFO semantics from LIFO primitives.

---

Back to Algorithms & Data Structures