🦄 Crystal Heap: Min-Heap Core

Difficulty: Intermediate Tags: heap, priority-queue, data-structures Series: Data Structures I

Problem

Implement a min-heap - a special data structure where the smallest element is always at the top!

Your heap must support three operations: - push(x): Add a new value to the heap - pop(): Remove and return the smallest value - top(): See the smallest value (without removing it)

Given a list of operations, return the outputs from all pop and top operations in order.

What's a Heap?

A heap is like a priority line where the most important (smallest, in a min-heap) person is always at the front, no matter when they arrived!

Input

data = {
    'ops': list  # List of operations
}

Operations: - ['push', x] - add value x to heap - ['pop'] - remove and return minimum value - ['top'] - return minimum value (don't remove)

Output

list[int]  # Results from pop and top operations, in order

Constraints

• Number of operations ≤ 100,000
• Implement using an array-based heap with sift-up/sift-down
• All operations must be O(log n) or better

Examples

Example 1: Basic Heap Operations

Input:  {'ops': [['push', 3], ['push', 1], ['top'], ['pop'], ['top']]}
Output: [1, 1, 3]

Step-by-step:

1. push(3)   → Heap: [3]           Min: 3
2. push(1)   → Heap: [1, 3]        Min: 1
3. top()     → Return 1            (output: 1)
4. pop()     → Remove 1, return 1  (output: 1)
               Heap: [3]           Min: 3
5. top()     → Return 3            (output: 3)

Final output: [1, 1, 3]

Example 2: Multiple Elements

Input:  {'ops': [['push', 5], ['push', 2], ['push', 7], ['pop'], ['top']]}
Output: [2, 5]

Step-by-step:

1. push(5)   → Heap: [5]
2. push(2)   → Heap: [2, 5]        (2 bubbles to top)
3. push(7)   → Heap: [2, 5, 7]
4. pop()     → Remove 2, return 2  (output: 2)
               Heap: [5, 7]
5. top()     → Return 5            (output: 5)

Final output: [2, 5]