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) {
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

We're building a next-level EdTech Startup.