Min Heap

Introduction

A min heap is a complete binary tree where each parent node is smaller than or equal to its children, ensuring that the smallest element is always at the root. It is commonly used in implementing priority queues.

Insertion in Min Heap

In a Min Heap, insertion adds a new element at the end of the array. Then, the element is moved up (bubbled up) by swapping with its parent until the smallest element stays at the top, maintaining the heap’s structure.

Check if Heap is Full

If size == totalSize, print "Full" and exit the function.

Insert the New Element at the End

Place val at arr[size].
Set index = size and increment size.

Bubble Up to Maintain Min-Heap Property.

While index > 0:

Compute parent = (index - 1) / 2.
If arr[parent] > arr[index]:
- Swap arr[parent] and arr[index].
- Set index = parent.
Else, stop moving up and return.

The element is correctly placed, and the heap maintains its min-heap property.

The smallest element is now at the root.

Implementation of Insertion in Min Heap

// insertiononminheap.cpp
#include <iostream>
using namespace std;
class MinHeap
{
int *arr;
int size;
int totalSize;

public:
MinHeap(int n)
{
    arr = new int[n];
    size = 0;
    totalSize = n;
}
void insert(int val)
{
    if (size == totalSize)
    {
        cout << "Full";
        return;
    }
    arr[size] = val;
    int index = size;
    size++;
    while (index > 0)
    {
        int parent = (index - 1) / 2;
        if (arr[parent] > arr[index])
        {
            swap(arr[parent], arr[index]);
            index = parent;
        }
        else
            return;
    }
}
void display()
{
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
}
};

int main()
{
MinHeap h(5);
h.insert(10);
h.insert(9);
h.insert(12);
h.insert(15);
h.insert(3);
//       10
//       / \
//     9    12
//    / \  
//   15  3 
h.display();
//        3
//       / \
//     9   12
//    / \
//   15  10
return 0;
}

print("We're Working")

console.log("We're Working");

Time Complexity: Insertion

In a Min Heap, inserting a new element involves placing it at the end of the array and then bubbling up to restore the heap property. In the worst case, the element is compared and swapped with parent nodes up to the root. Since the height of the heap is log n, the number of comparisons and swaps is proportional to log n, making the time complexity O(log n).

Time Complexity:O(logn)

Space Complexity: Insertion

Only a few variables are used during the operation.

Space Complexity:O(1)

Deletion in Min Heap

In a Min Heap, deletion removes the minimum element at the root. The last element is moved to the root to fill the gap. The heap is restored by bubbling down swapping the root with its smaller child until the min-heap property is reestablished, keeping the smallest element at the top.

Check if the heap is empty

If size == 0, return immediately since there are no elements to delete.

Replace the root with the last element

Set arr[0] = arr[size - 1].
Reduce the heap size by 1 (size--).

Heapify down to restore the min-heap property

Repeat the following steps until the current index (i) reaches a position where no more heapify steps are needed

Calculate the left and right child indices:
leftIdx = 2 * i + 1
rightIdx = 2 * i + 2

Compare the current element with its children

If the left child exists (leftIdx < size) and is smaller than the current element (arr[leftIdx] < arr[i]), swap them, and update i to leftIdx.
Otherwise, if the right child exists (rightIdx < size) and is smaller than the current element (arr[rightIdx] < arr[i]), swap them, and update i to rightIdx.
If neither child is smaller than the current element, stop the process.

The min-heap property is restored, and the minimum element has been removed from the heap.

The smallest element is now at the root.

Implementation of Deletion in Min Heap

// deletiononminheap.cpp
#include <iostream>
using namespace std;
class MinHeap
{
int *arr;
int size;
int totalSize;

public:
MinHeap(int n)
{
    arr = new int[n];
    size = 0;
    totalSize = n;
}
void insert(int val)
{
    if (size == totalSize)
    {
        cout << "Full";
        return;
    }
    arr[size] = val;
    int index = size;
    size++;
    while (index > 0)
    {
        int parent = (index - 1) / 2;
        if (arr[parent] > arr[index])
        {
            swap(arr[parent], arr[index]);
            index = parent;
        }
        else
            return;
    }
}
void deletion() {
if (size == 0) return;
arr[0] = arr[size - 1];
size--;
int i = 0;
while (i < size) {
    int leftIdx = 2 * i + 1;
    int rightIdx = 2 * i + 2;
    int smallest = i;
    if (leftIdx < size && arr[leftIdx] < arr[smallest]) {
        smallest = leftIdx;
    }
    if (rightIdx < size && arr[rightIdx] < arr[smallest]) {
        smallest = rightIdx;
    }
    if (smallest != i) {
        swap(arr[i], arr[smallest]);
        i = smallest;
    } else {
        return;
    }
}
}
void display()
{
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    cout<<endl;
}
};

int main()
{
MinHeap h(5);
h.insert(10);
h.insert(9);
h.insert(12);
h.insert(15);
h.insert(3);
//       10
//       / \
//     9    12
//    / \  
//   15  3 
h.display();
//        3
//       / \
//     9   12
//    / \
//   15  10
h.deletion();
h.display();
//        9
//       / \
//     10   12
//    / 
//   15  
return 0;
}

print("We're Working")

console.log("We're Working");

Time Complexity:Deletion

Replacing the root with last element : O(1).
Heapify down operation:O(logn)

Time Complexity: O(1)+O(logn)=O(logn)

Space Complexity:Deletion

Only a few variables are used during the operation.

Space Complexity:O(1)

Min Heap

On this page