In this chapter, we will learn how to insert and delete an element in Max Heap.
Table Of Contents
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:
Java
Python
C++
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
We're building a next-level EdTech Startup.
