Implement Min Heap
The problem
You need to implement the Min Heap with the following given methods.
- insert (x) -> insert value x to the min heap
- getMin -> Output the minimum value from min heap
- exctractMin -> Remove the minimum element from the heap
- heapSize -> return the current size of the heap
- isEmpty -> returns if heap is empty or not
- changeKey (ind, val) -> update the value at given index to val (index will be given 0-based indexing)
- initializeHeap -> Initialize the heap
Input : operation = [ "initializeheap", "insert", "insert", "insert", "getMin", "heapSize", "isEmpty", "extractMin", "changeKey" , "getMin" ] nums = [ [4], [1], [10], [0, 16] ] Output : [ null, null, null, null, 1, 3, 0, null, null, 10 ] Explanation : In 1st operation we initialize the heap to empty heap. In 2nd, 3rd, 4th operation we insert 4, 1, 10 to the heap respectively. The heap after 4th operation will be -> [1, 4, 10]. In 5th operation we output the minimum element from the heap i.e. 1. In 6th operation we output the size of the current heap i.e. 3. In 7th operation we output whether the heap is empty or not i.e. false (0). In 8th operation we remove the minimum element from heap. So the ne heap becomes -> [4, 10]. In 9th operation we change the 0th index element to 16. So new heap becomes -> [16, 10]. After heapify -> [10, 16]. In 10th operation we output the minimum element of the heap i.e. 10.
Input : operation = [ "initializeheap", "insert", "insert", "extractMin", "getMin", "insert", "heapSize", "isEmpty", "extractMin", "changeKey" , "getMin" ] nums = [ [4], [1], [1], [0, 2] ] Output : [ null, null, null, null, 4, null, 2, 0, null, null, 2 ] Explanation : In 1st operation we initialize the heap to empty heap. In 2nd, 3rd operation we insert 4, 1 to the heap respectively. The heap after 4th operation will be -> [1, 4]. In 4th operation we remove the minimum element from heap. So the ne heap becomes -> [4]. In 5th operation we output the minimum element of the heap i.e. 4. In 6th operation we operation we insert 1 to the heap. The heap after 6th operation will be -> [1, 4]. In 7th operation we output the size of the current heap i.e. 2. In 8th operation we output whether the heap is empty or not i.e. false (0). In 9th operation we remove the minimum element from heap. So the ne heap becomes -> [4]. In 10th operation we change the 0th index element to 2. So new heap becomes -> [2]. In 11th operation we output the minimum element of the heap i.e. 2.
- 1 <= n <= 105
- -105 <= nums[i] <= 105
cpp
class Solution{
public:
void initializeHeap(){
}
void insert(int key){
}
void changeKey(int index, int new_val){
}
void extractMin(){
}
bool isEmpty(){
}
int getMin(){
}
int heapSize(){
}
};java
class Solution {
public void initializeHeap() {
}
public void insert(int key) {
}
public void changeKey(int index, int newVal) {
}
public void extractMin() {
}
public boolean isEmpty() {
}
public int getMin() {
}
public int heapSize() {
}
}python
class Solution:
def initializeHeap(self):
def insert(self, key):
def changeKey(self, index, new_val):
def extractMin(self):
def isEmpty(self):
def getMin(self):
def heapSize(self):javascript
class Solution {
initializeHeap() {
}
insert(key) {
}
changeKey(index, new_val) {
}
extractMin() {
}
isEmpty() {
}
getMin() {
}
heapSize() {
}
}csharp
public class Solution
{
public void initializeHeap() {
}
public void insert(int key) {
}
public void changeKey(int index, int new_val) {
}
public void extractMin() {
}
public bool isEmpty() {
}
public int getMin() {
}
public int heapSize() {
}
private void HeapifyUp(int index) {
}
}go
type MinHeap struct {
}
func (h *MinHeap) initializeHeap() {
}
func (h *MinHeap) insert(key int) {
}
func (h *MinHeap) changeKey(index, newVal int) {
}
func (h *MinHeap) extractMin() {
}
func (h *MinHeap) isEmpty() bool {
}
func (h *MinHeap) getMin() int {
}
func (h *MinHeap) heapSize() int {
}Stuck? Show a way to structure it+
- 01State the complete-binary-tree array mapping
- 02Implement insert with sift-up
- 03Implement peek and extract-min with empty checks
- 04Restore order with sift-down choosing the smaller child
Reference answer
Then expect these follow-ups
How would you implement decrease-key?
Tests: implementation extension
How can you build a heap in linear time?
Tests: complexity analysis
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question