Implement a Min-Heap with Insert and Remove-Min

Question

Implement a Min-Heap data structure that includes methods for inserting an element and removing the minimum value.

Codemia · Accepted Answer

To implement a Min-Heap, we need to create a class that supports two main operations: **insert** and **remove-min**. The Min-Heap should maintain the property that the parent node is always less than or equal to its child nodes. Additionally, we should consider edge cases such as inserting into an empty heap and removing from a heap with only one element.

The Min-Heap can be represented as an array where for any element at index `i`, its left child is at `2*i + 1` and its right child is at `2*i + 2`. The insertion operation will add the new element at the end of the array and then 'bubble up' this element to restore the heap property. The remove-min operation will remove the root element, replace it with the last element in the array, and then 'bubble down' this element to restore the heap property.

Here is a Python implementation of the Min-Heap class:

```python
class MinHeap:
    def __init__(self):
        self.heap = []

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

def remove_min(self):
        if len(self.heap) == 0:
            return None
        min_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self._bubble_down(0)
        return min_val

def _bubble_up(self, index):
        parent = (index - 1) // 2
        while index > 0 and self.heap[index] < self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            index = parent
            parent = (index - 1) // 2

def _bubble_down(self, index):
        smallest = index
        left = 2 * index + 1
        right = 2 * index + 2

if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right

if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._bubble_down(smallest)
```

The time complexity for both the `insert` and `remove-min` operations is O(log n) due to the tree-like structure of the heap. Inserting an element requires bubbling it up to maintain the heap property, while removing the minimum element requires bubbling down the last element to restore the heap structure.

Using an array to implement the Min-Heap is space-efficient and allows for quick access to the parent and child nodes. However, if we were to use a linked structure, it could lead to increased overhead and complexity in managing pointers. This implementation is optimal for scenarios where frequent insertions and deletions are expected, such as in priority queues.

Implement a Min-Heap with Insert and Remove-Min

Pony.Ai

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

Pony.Ai 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