HEAP

We can insert heap by heapify method of may using maxheap or minheap .

MaxHeap:

#include <iostream>
#include <vector>

using namespace std;

class MaxHeap {
private:
vector<int> heap;

// Helper function to maintain max heap property after insertion
void heapifyUp(int index) {
// Calculate parent index
int parent = (index — 1) / 2;

// While index is not the root and the current element is greater than its parent
if (index > 0 && heap[index] > heap[parent]) {
// Swap the current element with its parent
swap(heap[index], heap[parent]);
// Recursively heapify up the parent
heapifyUp(parent);
}
}

public:
// Function to insert a new element into the max heap
void insert(int value) {
// Add the new element at the end of the heap
heap.push_back(value);

// Heapify up to maintain max heap property
heapifyUp(heap.size() — 1);
}

// Utility function to print the heap
void printHeap() const {
for (int val : heap) {
cout << val << “ “;
}
cout << endl;
}
};

int main() {
MaxHeap maxHeap;

// Insert elements into the heap
maxHeap.insert(10);
maxHeap.insert(20);
maxHeap.insert(5);
maxHeap.insert(15);
maxHeap.insert(30);

// Print the heap after insertions
cout << “Max Heap after insertions: “;
maxHeap.printHeap();

return 0;
}

Explanation for Max Heap Insertion

• Insert Function: Adds the new element at the end of the vector and then calls heapifyUp to maintain the max heap property.
• Heapify Up (heapifyUp): Swaps the inserted element with its parent if the parent is smaller, repeating until the max heap property is restored.

MinHeap :

Get suhama’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

#include <iostream>
#include <vector>

using namespace std;

class MinHeap {
private:
vector<int> heap;

// Helper function to maintain min heap property after insertion
void heapifyUp(int index) {
// Calculate parent index
int parent = (index — 1) / 2;

// While index is not the root and the current element is smaller than its parent
if (index > 0 && heap[index] < heap[parent]) {
// Swap the current element with its parent
swap(heap[index], heap[parent]);
// Recursively heapify up the parent
heapifyUp(parent);
}
}

public:
// Function to insert a new element into the min heap
void insert(int value) {
// Add the new element at the end of the heap
heap.push_back(value);

// Heapify up to maintain min heap property
heapifyUp(heap.size() — 1);
}

// Utility function to print the heap
void printHeap() const {
for (int val : heap) {
cout << val << “ “;
}
cout << endl;
}
};

int main() {
MinHeap minHeap;

// Insert elements into the heap
minHeap.insert(10);
minHeap.insert(20);
minHeap.insert(5);
minHeap.insert(15);
minHeap.insert(30);

// Print the heap after insertions
cout << “Min Heap after insertions: “;
minHeap.printHeap();

return 0;
}

Explanation for Min Heap Insertion

• Insert Function: Adds the new element at the end of the vector and calls heapifyUp to maintain the min heap property.
• Heapify Up (heapifyUp): Swaps the inserted element with its parent if the parent is larger, repeating until the min heap property is restored.

TC o(log n) , SC o(n) for both min and max heap .

Suhama Mustafa