Implement Min Heap

Heaps Theory and Implementation Medium

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

Constraints

1 <= n <= 10⁵
-10⁵ <= nums[i] <= 10⁵

Hints

The heap is usually stored in an array. An empty list can represent an initial empty heap.
Add x to the end of the array. The smallest element is always at index 0. Swap the root (minimum element) with the last element. Return the length of the array representing the heap. Return True if the array is empty, otherwise False.

Company Tags

Epic Systems MongoDB Docker Swiggy Epic Games DoorDash Uber Boston Consulting Group Medtronic Morgan Stanley Bloomberg Freshworks GE Healthcare AMD Snowflake Twilio Reddit Johnson & Johnson Bain & Company American Express Instacart Lyft ARM Broadcom Roche Google Microsoft Amazon Meta Apple Netflix Adobe

Editorial

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/4j8fTseaBmA/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Pre-requisites: Heap theory, Heapify Algorithm

Approach:

The goal is to implement a minimum heap data structure that will provide different operations to the user. The idea to use a list/array to store the elements in an order that follows the min-heap property. An array stores a complete binary tree without using extra pointers for child links. It allows calculating parent and child positions with simple index arithmetic and keeps all elements close together for faster memory access, making it both space-efficient and quick to update or reorder elements. Here's how different function can be implemented:

1. Insert(val):

The element can be added at the back of the list. Since, this element may not follow the min-heap property, it can be heapified upwards.

2. Get Minimum():

The minimum value will always be stored at the 0th index as the array follows the min-heap property.

3. Extract Minimum():

If the smallest value (located at 0th index) is removed directly, all the elements in the array will need to be shifted by one index ahead making it a costly operation. Instead, the smallest value can be swapped with the element at last index. The value at the last index (currently storing the smallest value) can be popped out from the back of the array/list.

Since, the element at the 0th index does not follow the min-heap property (because it was swapped), we must heapify it downwards.

4. Heap Size():

The size of the array/list can be returned directly as the heap size.

5. Is Empty():

If the size of the array is zero, the heap can be marked as empty.

6. Change Key(ind, val):

The value at particular index can be easily updated in the list. This updated value might disturb the min-heap property of the array, so it needs to be heapified upwards or downwards accordingly.

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    vector<int> arr; // list to store the min-heap
    int count; // to store the count of elements in min-heap
    
    // Function to recursively heapify the array upwards
    void heapifyUp(vector<int> &arr, int ind) {
        int parentInd = (ind - 1)/2; 

        // If current index holds smaller value than the parent
        if(ind > 0 && arr[ind] < arr[parentInd]) {
            // Swap the values at the two indices
            swap(arr[ind], arr[parentInd]);

            // Recursively heapify the upper nodes
            heapifyUp(arr, parentInd);
        } 

        return;
    }
    
    // Function to recursively heapify the array downwards
    void heapifyDown(vector<int> &arr, int ind) {
        int n = arr.size(); // Size of the array

        // To store th index of smallest element
        int smallestInd = ind; 

        // Indices of the left and right children
        int leftChildInd = 2*ind + 1, rightChildInd = 2*ind + 2;
        
        // If the left child holds smaller value, update the smallest index
        if(leftChildInd < n && arr[leftChildInd] < arr[smallestInd]) 
            smallestInd = leftChildInd;

        // If the right child holds smaller value, update the smallest index
        if(rightChildInd < n && arr[rightChildInd] < arr[smallestInd]) 
            smallestInd = rightChildInd;

        // If the smallest element index is updated
        if(smallestInd != ind) {
            // Swap the largest element with the current index
            swap(arr[smallestInd] , arr[ind]);

            // Recursively heapify the lower subtree
            heapifyDown(arr, smallestInd);
        }

        return; 
    }
    
public:
    // Method to intialize the min-heap data structure
    void initializeHeap(){
        arr.clear();
        count = 0;
    }
    
    // Method to insert a given value in the min-heap
    void insert(int key){
        // Insert the value at the back of the list 
        arr.push_back(key);
        
        // Heapify upwards
        heapifyUp(arr, count);
        count = count+1; // Increment the counter;
        
        return;
    }
        
    // Method to change the value at a given index in min-heap
    void changeKey(int index, int new_val){
        // If the current value is replaced with a smaller value
        if(arr[index] > new_val) {
            arr[index] = new_val;
            heapifyUp(arr, index);
        }

        // Else if the current value is replaced with a larger value
        else {
            arr[index] = new_val;
            heapifyDown(arr, index);
        }

        return;
    }
    
    // Method to extract the minimum value from the min-heap
    void extractMin(){
        int ele = arr[0]; // minimum value in the heap
        
        // Swap the top value with the value at last index
        swap(arr[0], arr[count-1]); 
        
        arr.pop_back(); // Pop the minimum value from the list
        count = count - 1; // Decrement the counter
        
        // Heapify the root value downwards
        heapifyDown(arr, 0);
    }
    
    // Method to return if the min-heap is empty
    bool isEmpty(){
        return (count == 0);
    }
    
    // Method to return the minimum value in the min-heap
    int getMin(){
        // Returning the value stored at the root
        return arr[0];
    }
    
    // Method to return the size of min-heap
    int heapSize(){
        return count;
    }
};

// Driver code
int main() {
    // Creating an object of the Solution class
    Solution heap;

    // Initializing a min heap data structure 
    heap.initializeHeap();
    
    // Performing different operations
    heap.insert(4); cout << "Inserting 4 in the min-heap\n";
    heap.insert(5); cout << "Inserting 5 in the min-heap\n";
    heap.insert(10); cout << "Inserting 10 in the min-heap\n";
    cout << "Minimum value in the min-heap is: " << heap.getMin() << "\n";
    cout << "Size of min-heap is: " << heap.heapSize() << "\n";
    cout << "Is heap empty: " << heap.isEmpty() << "\n";
    cout << "Extracting minimum value from the heap\n"; heap.extractMin();
    cout << "Changing value at index 0 to 10\n"; heap.changeKey(0, 10);
    cout << "Minimum value in the min-heap is: " << heap.getMin();
    
    return 0;
}
import java.util.*;

class Solution {
    private List<Integer> arr; // list to store the min-heap
    private int count; // to store the count of elements in min-heap
    
    // Constructor
    public Solution() {
        arr = new ArrayList<>();
        count = 0;
    }
    
    // Function to recursively heapify the array upwards
    private void heapifyUp(List<Integer> arr, int ind) {
        int parentInd = (ind - 1)/2; 

        // If current index holds smaller value than the parent
        if(ind > 0 && arr.get(ind) < arr.get(parentInd)) {
            // Swap the values at the two indices
            int temp = arr.get(ind);
            arr.set(ind, arr.get(parentInd));
            arr.set(parentInd, temp);

            // Recursively heapify the upper nodes
            heapifyUp(arr, parentInd);
        } 

        return;
    }
    
    // Function to recursively heapify the array downwards
    private void heapifyDown(List<Integer> arr, int ind) {
        int n = arr.size(); // Size of the array

        // To store the index of smallest element
        int smallestInd = ind; 

        // Indices of the left and right children
        int leftChildInd = 2*ind + 1;
        int rightChildInd = 2*ind + 2;
        
        // If the left child holds smaller value, update the smallest index
        if(leftChildInd < n && arr.get(leftChildInd) < arr.get(smallestInd)) 
            smallestInd = leftChildInd;

        // If the right child holds smaller value, update the smallest index
        if(rightChildInd < n && arr.get(rightChildInd) < arr.get(smallestInd)) 
            smallestInd = rightChildInd;

        // If the smallest element index is updated
        if(smallestInd != ind) {
            // Swap the largest element with the current index
            int temp = arr.get(smallestInd);
            arr.set(smallestInd, arr.get(ind));
            arr.set(ind, temp);

            // Recursively heapify the lower subtree
            heapifyDown(arr, smallestInd);
        }

        return; 
    }
    
    // Method to intialize the min-heap data structure
    public void initializeHeap(){
        arr.clear();
        count = 0;
    }
    
    // Method to insert a given value in the min-heap
    public void insert(int key){
        // Insert the value at the back of the list 
        arr.add(key);
        
        // Heapify upwards
        heapifyUp(arr, count);
        count = count+1; // Increment the counter;
        
        return;
    }
        
    // Method to change the value at a given index in min-heap
    public void changeKey(int index, int new_val){
        // If the current value is replaced with a smaller value
        if(arr.get(index) > new_val) {
            arr.set(index, new_val);
            heapifyUp(arr, index);
        }
        // Else if the current value is replaced with a larger value
        else {
            arr.set(index, new_val);
            heapifyDown(arr, index);
        }

        return;
    }
    
    // Method to extract the minimum value from the min-heap
    public void extractMin(){
        int ele = arr.get(0); // minimum value in the heap
        
        // Swap the top value with the value at last index
        int temp = arr.get(count - 1);
        arr.set(count - 1, arr.get(0));
        arr.set(0, temp);
        
        arr.remove(count - 1); // Pop the minimum value from the list
        count = count - 1; // Decrement the counter
        
        // Heapify the root value downwards
        if(count > 0) {
            heapifyDown(arr, 0);
        }
    }
    
    // Method to return if the min-heap is empty
    public boolean isEmpty(){
        return (count == 0);
    }
    
    // Method to return the minimum value in the min-heap
    public int getMin(){
        // Returning the value stored at the root
        return arr.get(0);
    }
    
    // Method to return the size of min-heap
    public int heapSize(){
        return count;
    }
}

class Main {
    public static void main(String[] args) {
        // Creating an object of the Solution class
        Solution heap = new Solution();

        // Initializing a min heap data structure 
        heap.initializeHeap();
        
        // Performing different operations
        heap.insert(4); System.out.println("Inserting 4 in the min-heap");
        heap.insert(5); System.out.println("Inserting 5 in the min-heap");
        heap.insert(10); System.out.println("Inserting 10 in the min-heap");
        System.out.println("Minimum value in the min-heap is: " + heap.getMin());
        System.out.println("Size of min-heap is: " + heap.heapSize());
        System.out.println("Is heap empty: " + heap.isEmpty());
        System.out.println("Extracting minimum value from the heap");
        heap.extractMin();
        System.out.println("Changing value at index 0 to 10");
        heap.changeKey(0, 10);
        System.out.println("Minimum value in the min-heap is: " + heap.getMin());
    }
}
class Solution:
    def __init__(self):
        self.arr = []  # list to store the min-heap
        self.count = 0  # to store the count of elements in min-heap

    # Function to recursively heapify the array upwards
    def heapifyUp(self, arr, ind):
        parentInd = (ind - 1)//2 

        # If current index holds smaller value than the parent
        if ind > 0 and arr[ind] < arr[parentInd]:
            # Swap the values at the two indices
            arr[ind], arr[parentInd] = arr[parentInd], arr[ind]

            # Recursively heapify the upper nodes
            self.heapifyUp(arr, parentInd)

        return

    # Function to recursively heapify the array downwards
    def heapifyDown(self, arr, ind):
        n = len(arr)  # Size of the array

        # To store the index of smallest element
        smallestInd = ind 

        # Indices of the left and right children
        leftChildInd = 2*ind + 1
        rightChildInd = 2*ind + 2

        # If the left child holds smaller value, update the smallest index
        if leftChildInd < n and arr[leftChildInd] < arr[smallestInd]:
            smallestInd = leftChildInd

        # If the right child holds smaller value, update the smallest index
        if rightChildInd < n and arr[rightChildInd] < arr[smallestInd]:
            smallestInd = rightChildInd

        # If the smallest element index is updated
        if smallestInd != ind:
            # Swap the largest element with the current index
            arr[smallestInd], arr[ind] = arr[ind], arr[smallestInd]

            # Recursively heapify the lower subtree
            self.heapifyDown(arr, smallestInd)

        return

    # Method to intialize the min-heap data structure
    def initializeHeap(self):
        self.arr.clear()
        self.count = 0

    # Method to insert a given value in the min-heap
    def insert(self, key):
        # Insert the value at the back of the list
        self.arr.append(key)

        # Heapify upwards
        self.heapifyUp(self.arr, self.count)
        self.count += 1  # Increment the counter

        return

    # Method to change the value at a given index in min-heap
    def changeKey(self, index, new_val):
        # If the current value is replaced with a smaller value
        if self.arr[index] > new_val:
            self.arr[index] = new_val
            self.heapifyUp(self.arr, index)
        # Else if the current value is replaced with a larger value
        else:
            self.arr[index] = new_val
            self.heapifyDown(self.arr, index)

        return

    # Method to extract the minimum value from the min-heap
    def extractMin(self):
        ele = self.arr[0]  # minimum value in the heap

        # Swap the top value with the value at last index
        self.arr[0], self.arr[self.count - 1] = self.arr[self.count - 1], self.arr[0]

        # Pop the minimum value from the list
        self.arr.pop()
        self.count -= 1  # Decrement the counter

        # Heapify the root value downwards
        if self.count > 0:
            self.heapifyDown(self.arr, 0)

    # Method to return if the min-heap is empty
    def isEmpty(self):
        return (self.count == 0)

    # Method to return the minimum value in the min-heap
    def getMin(self):
        # Returning the value stored at the root
        return self.arr[0]

    # Method to return the size of min-heap
    def heapSize(self):
        return self.count


# Driver code
def main():
    # Creating an object of the Solution class
    heap = Solution()

    # Initializing a min heap data structure
    heap.initializeHeap()

    # Performing different operations
    heap.insert(4); print("Inserting 4 in the min-heap")
    heap.insert(5); print("Inserting 5 in the min-heap")
    heap.insert(10); print("Inserting 10 in the min-heap")
    print("Minimum value in the min-heap is:", heap.getMin())
    print("Size of min-heap is:", heap.heapSize())
    print("Is heap empty:", heap.isEmpty())
    print("Extracting minimum value from the heap")
    heap.extractMin()
    print("Changing value at index 0 to 10")
    heap.changeKey(0, 10)
    print("Minimum value in the min-heap is:", heap.getMin())


if __name__ == "__main__":
    main()
class Solution {
    constructor() {
        this.arr = []; // list to store the min-heap
        this.count = 0; // to store the count of elements in min-heap
    }
    
    // Function to recursively heapify the array upwards
    heapifyUp(arr, ind) {
        let parentInd = Math.floor((ind - 1) / 2);

        // If current index holds smaller value than the parent
        if (ind > 0 && arr[ind] < arr[parentInd]) {
            // Swap the values at the two indices
            [arr[ind], arr[parentInd]] = [arr[parentInd], arr[ind]];

            // Recursively heapify the upper nodes
            this.heapifyUp(arr, parentInd);
        }
        return;
    }
    
    // Function to recursively heapify the array downwards
    heapifyDown(arr, ind) {
        let n = arr.length; // Size of the array

        // To store the index of smallest element
        let smallestInd = ind; 

        // Indices of the left and right children
        let leftChildInd = 2 * ind + 1;
        let rightChildInd = 2 * ind + 2;
        
        // If the left child holds smaller value, update the smallest index
        if (leftChildInd < n && arr[leftChildInd] < arr[smallestInd]) {
            smallestInd = leftChildInd;
        }

        // If the right child holds smaller value, update the smallest index
        if (rightChildInd < n && arr[rightChildInd] < arr[smallestInd]) {
            smallestInd = rightChildInd;
        }

        // If the smallest element index is updated
        if (smallestInd !== ind) {
            // Swap the largest element with the current index
            [arr[smallestInd], arr[ind]] = [arr[ind], arr[smallestInd]];
            
            // Recursively heapify the lower subtree
            this.heapifyDown(arr, smallestInd);
        }

        return;
    }
    
    // Method to intialize the min-heap data structure
    initializeHeap() {
        this.arr = [];
        this.count = 0;
    }
    
    // Method to insert a given value in the min-heap
    insert(key) {
        // Insert the value at the back of the list 
        this.arr.push(key);
        
        // Heapify upwards
        this.heapifyUp(this.arr, this.count);
        this.count = this.count + 1; // Increment the counter;
        
        return;
    }
        
    // Method to change the value at a given index in min-heap
    changeKey(index, new_val) {
        // If the current value is replaced with a smaller value
        if (this.arr[index] > new_val) {
            this.arr[index] = new_val;
            this.heapifyUp(this.arr, index);
        }
        // Else if the current value is replaced with a larger value
        else {
            this.arr[index] = new_val;
            this.heapifyDown(this.arr, index);
        }

        return;
    }
    
    // Method to extract the minimum value from the min-heap
    extractMin() {
        let ele = this.arr[0]; // minimum value in the heap
        
        // Swap the top value with the value at last index
        [this.arr[0], this.arr[this.count - 1]] = [this.arr[this.count - 1], this.arr[0]];
        
        this.arr.pop(); // Pop the minimum value from the list
        this.count = this.count - 1; // Decrement the counter
        
        // Heapify the root value downwards
        if (this.count > 0) {
            this.heapifyDown(this.arr, 0);
        }
    }
    
    // Method to return if the min-heap is empty
    isEmpty() {
        return (this.count === 0);
    }
    
    // Method to return the minimum value in the min-heap
    getMin() {
        // Returning the value stored at the root
        return this.arr[0];
    }
    
    // Method to return the size of min-heap
    heapSize() {
        return this.count;
    }
}

// Driver code
function main() {
    // Creating an object of the Solution class
    let heap = new Solution();

    // Initializing a min heap data structure 
    heap.initializeHeap();
    
    // Performing different operations
    heap.insert(4); console.log("Inserting 4 in the min-heap");
    heap.insert(5); console.log("Inserting 5 in the min-heap");
    heap.insert(10); console.log("Inserting 10 in the min-heap");
    console.log("Minimum value in the min-heap is: " + heap.getMin());
    console.log("Size of min-heap is: " + heap.heapSize());
    console.log("Is heap empty: " + heap.isEmpty());
    console.log("Extracting minimum value from the heap");
    heap.extractMin();
    console.log("Changing value at index 0 to 10");
    heap.changeKey(0, 10);
    console.log("Minimum value in the min-heap is: " + heap.getMin());
}

// Run the driver code
main();

Complexity Analysis:

Considering there are maximum N elements inserted in the heap data structure,

Time Complexity:

Insert(val): Inserting and Heapifying upwards contribute to O(logN) time.
Get Minimum(): Constant time operation, i.e., O(1).
Extract Minimum(): Involves Heapifying downwards contributing to O(logN) time.
Heap Size(): Constant time operation, i.e., O(1).
Is Empty(): Constant time operation, i.e., O(1).
Change Key(ind, val): Involves heapifying which takes O(logN) time.

Space Complexity: O(N), because of the array used to store the elements.

Code

Problem List