Insertion and Deletion in MaxHeap

In this chapter, we will learn how to insert and delete an element in Max Heap.

Problem Statement:

Given a max heap with some elements, Implement a function to insert and delete an element.

Example:

Input: 
insert(98)
insert(87)
insert(86)
insert(44)
insert(40)
insert(32)
insert(33)
insert(20)
insert(21)
delete()     // it should return 98 in our case.
printHeap()  // it will print the current status of Max Heap.
insert(100)
printHeap()  // it will print the current status of Max Heap.

Output: 
98
[87, 44, 86, 21, 40, 32, 33, 20]
[100, 87, 86, 44, 40, 32, 33, 20, 21]

Code:

import java.util.*;

class Innoskrit {

    static List<Integer> maxHeap = new ArrayList<>();

    public static void swap(int index, int largestIndex) {
        int temp = maxHeap.get(index);
        maxHeap.set(index, maxHeap.get(largestIndex));
        maxHeap.set(largestIndex, temp);
    }

    public static void heapify(int index) {
        int size = maxHeap.size();
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        int largestIndex = index;

        if(left < size && maxHeap.get(left) > maxHeap.get(largestIndex)) {
            largestIndex = left;
        }
        if(right < size && maxHeap.get(right) > maxHeap.get(largestIndex)) {
            largestIndex = right;
        }

        if(largestIndex != index) {
            swap(index, largestIndex);
            heapify(largestIndex);
        }
    }

    public static void insert(int data) {
        maxHeap.add(data);
        int size = maxHeap.size();
        int index = size - 1;
        int parent = (index-1)/2;
        while(parent >= 0 && maxHeap.get(index) > maxHeap.get(parent)) {
            swap(index, parent);
            index = parent;
            parent = (index-1)/2;
        }
    }

    public static int delete() {
        int size = maxHeap.size();
        if(size == 0)
            return -1;
        int element = maxHeap.get(0);
        maxHeap.set(0, maxHeap.get(size - 1));
        maxHeap.remove(size - 1);
        heapify(0);
        return element;
    }
    
    public static void printHeap() {
        System.out.println(maxHeap);
    }

    public static void main(String[] args) {
        Innoskrit.insert(98);
        Innoskrit.insert(87);
        Innoskrit.insert(86);
        Innoskrit.insert(44);
        Innoskrit.insert(40);
        Innoskrit.insert(32);
        Innoskrit.insert(33);
        Innoskrit.insert(20);
        Innoskrit.insert(21);
        System.out.println(Innoskrit.delete());
        Innoskrit.printHeap();
        Innoskrit.insert(100);
        Innoskrit.printHeap();
    }
}
class Innoskrit:

    maxHeap = []

    def swap(index, largestIndex):
        temp = Innoskrit.maxHeap[index]
        Innoskrit.maxHeap[index] = Innoskrit.maxHeap[largestIndex]
        Innoskrit.maxHeap[largestIndex] = temp

    def heapify(index):
        size = len(Innoskrit.maxHeap)
        left = 2 * index + 1
        right = 2 * index + 2
        
        largestIndex = index

        if left < size and Innoskrit.maxHeap[left] > Innoskrit.maxHeap[largestIndex]:
            largestIndex = left

        if right < size and Innoskrit.maxHeap[right] > Innoskrit.maxHeap[largestIndex]:
            largestIndex = right

        if largestIndex != index:
            Innoskrit.swap(index, largestIndex)
            Innoskrit.heapify(largestIndex)

    def insert(data):
        Innoskrit.maxHeap.append(data)
        size = len(Innoskrit.maxHeap)
        index = size - 1
        parent = (index - 1)//2
        while parent >= 0 and Innoskrit.maxHeap[index] > Innoskrit.maxHeap[parent]:
            Innoskrit.swap(index, parent)
            index = parent
            parent = (index - 1)//2

    def delete():
        size = len(Innoskrit.maxHeap)
        if size == 0:
            return -1
        element = Innoskrit.maxHeap[0]
        Innoskrit.maxHeap[0] = Innoskrit.maxHeap[size - 1]
        Innoskrit.maxHeap.pop()
        Innoskrit.heapify(0)
        return element
    
    def printHeap():
        print(Innoskrit.maxHeap)

if __name__ == "__main__":
    Innoskrit.insert(98)
    Innoskrit.insert(87)
    Innoskrit.insert(86)
    Innoskrit.insert(44)
    Innoskrit.insert(40)
    Innoskrit.insert(32)
    Innoskrit.insert(33)
    Innoskrit.insert(20)
    Innoskrit.insert(21)
    print(Innoskrit.delete())
    Innoskrit.printHeap()
    Innoskrit.insert(100)
    Innoskrit.printHeap()
#include <bits/stdc++.h>
using namespace std;

class Innoskrit {
public:

    vector<int> maxHeap;
    
    void swap(int index, int largestIndex) {
        int temp = maxHeap[index];
        maxHeap[index] = maxHeap[largestIndex];
        maxHeap[largestIndex] = temp;
    }

    void heapify(int index) {
        int size = maxHeap.size();
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        int largestIndex = index;

        if(left < size && maxHeap[left] > maxHeap[largestIndex]) {
            largestIndex = left;
        }
        if(right < size && maxHeap[right] > maxHeap[largestIndex]) {
            largestIndex = right;
        }

        if(largestIndex != index) {
            swap(index, largestIndex);
            heapify(largestIndex);
        }
    }

    void insert(int data) {
        maxHeap.push_back(data);
        int size = maxHeap.size();
        int index = size - 1;
        int parent = (index - 1)/2;
        while(parent >= 0 && maxHeap[index] > maxHeap[parent]) {
            swap(index, parent);
            index = parent;
            parent = (index - 1)/2;
        }
    }

    int deleteElement() {
        int size = maxHeap.size();
        if(size == 0)
            return -1;
        int element = maxHeap[0];
        maxHeap[0] = maxHeap[size - 1];
        maxHeap.pop_back();
        heapify(0);
        return element;
    }
    
    void printHeap() {
        cout << "[";
        for(int i = 0; i < maxHeap.size(); i++) {
            cout << maxHeap[i];
            if(i != maxHeap.size() - 1) {
                cout << ", ";
            }
        }
            
        cout << "]" << endl;
    }
    
};

int main() {
    Innoskrit obj;
    obj.insert(98);
    obj.insert(87);
    obj.insert(86);
    obj.insert(44);
    obj.insert(40);
    obj.insert(32);
    obj.insert(33);
    obj.insert(20);
    obj.insert(21);
    cout << obj.deleteElement() << endl;
    obj.printHeap();
    obj.insert(100);
    obj.printHeap();
} 

Output:

98
[87, 44, 86, 21, 40, 32, 33, 20]
[100, 87, 86, 44, 40, 32, 33, 20, 21]

Time Complexity:

Insertion: O(log N)
Deletion: O(log N)

Space Complexity:

Insertion: O(1)
Deletion: O(log N)

Innoskrit

Innoskrit

We're building a next-level EdTech Startup.

Related Posts

Leave A Reply

Your email address will not be published.