In this chapter, we will learn how to insert and delete an element in Max Heap.
In this chapter, we will learn how to insert and delete an element in Max Heap.
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]
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]
Insertion: O(log N)
Deletion: O(log N)
Insertion: O(1)
Deletion: O(log N)
© 2022 - All Rights Reserved.