Implement a Min-Priority Queue Without a Library Heap

Question

The candidate is asked to implement a min-priority queue from scratch without using any built-in heap libraries.

Codemia · Accepted Answer

To implement a min-priority queue, we need to support the following operations:
1. **Insert**: Add an element to the queue with a given priority.
2. **Extract-Min**: Remove and return the element with the lowest priority.
3. **Peek**: Return the element with the lowest priority without removing it.
4. **Decrease-Key**: Decrease the priority of a given element.

We can use a binary heap to implement the min-priority queue. A binary heap is a complete binary tree that satisfies the heap property, where each parent node is less than or equal to its children. This structure allows us to efficiently perform the required operations:
- **Insert**: O(log n)
- **Extract-Min**: O(log n)
- **Peek**: O(1)
- **Decrease-Key**: O(log n)

Here is a Python implementation of a min-priority queue using a binary heap:
```python
class MinPriorityQueue:
    def __init__(self):
        self.heap = []

def insert(self, key):
        self.heap.append(key)
        self._bubble_up(len(self.heap) - 1)

def extract_min(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        min_elem = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._bubble_down(0)
        return min_elem

def peek(self):
        return self.heap[0] if self.heap else None

def _bubble_up(self, index):
        while index > 0:
            parent_index = (index - 1) // 2
            if self.heap[index] < self.heap[parent_index]:
                self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
                index = parent_index
            else:
                break

def _bubble_down(self, index):
        size = len(self.heap)
        while index < size:
            left_child = 2 * index + 1
            right_child = 2 * index + 2
            smallest = index

if left_child < size and self.heap[left_child] < self.heap[smallest]:
                smallest = left_child
            if right_child < size and self.heap[right_child] < self.heap[smallest]:
                smallest = right_child
            if smallest != index:
                self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
                index = smallest
            else:
                break
```
This implementation includes the necessary methods to manage the heap structure effectively.

The time complexities for the operations in our min-priority queue are as follows:
- **Insert**: O(log n) due to the bubble-up process.
- **Extract-Min**: O(log n) because we need to bubble down the root after removal.
- **Peek**: O(1) since it only accesses the root element.
- **Decrease-Key**: O(log n) as it may require a bubble-up operation.

To ensure our min-priority queue works correctly, we should create test cases that cover various scenarios:
1. Insert elements and check if the minimum is correct after each insertion.
2. Extract the minimum and verify the order of extraction.
3. Test the peek operation to ensure it returns the correct minimum without removal.
4. Test edge cases, such as extracting from an empty queue.

Implement a Min-Priority Queue Without a Library Heap

Amazon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Amazon Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string