Max Heap

A binary tree where each parent is larger than its children.

Introduction

A max heap is a complete binary tree where each parent node is larger than or equal to its children, ensuring that the largest element is always at the root. It is often used to efficiently retrieve the largest element in priority queues.

Insertion in Max Heap

In a Max 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 largest 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 Max-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 max-heap property.

Implementation Insertion in Max Heap

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

public:
MaxHeap(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()
{
MaxHeap h(5);
h.insert(10);
h.insert(9);
h.insert(12);
h.insert(15);
h.insert(3);
//       10
//       / \
//     9    12
//    / \  
//   15  3 
h.display();
//       15
//       / \
//     12   10
//    / \   
//   9  3  
}

Time Complexity:Insertion

In a Max 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 needs to be compared and swapped with parent nodes up to the root. The height of a binary heap with n elements is log n, making the number of comparisons and swaps proportional to log n. Hence, the complexity is 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 Max Heap

In a Max Heap, deletion typically involves removing the maximum element which is always located at the root. After removal, the last element in the heap is moved to the root position to fill the vacancy. The heap property is then restored by moving the element at root down (bubbling down) through swaps with its larger child until the max-heap structure is reestablished, ensuring the largest element remains 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 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 greater than the current element (arr[leftIdx] < arr[i]), swap them, and update i to leftIdx.
Otherwise, if the right child exists ( ) and is greater than the current element (arr[rightIdx] < arr[i]), swap them, and update i to rightIdx.
If neither child is greater than the current element, stop the process.

The heap property is restored, and the maximum element has been removed from the heap.

Implementation Deletion in Max Heap

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

public:
MaxHeap(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;
        if(leftIdx<size && arr[i]<arr[leftIdx]){
            swap(arr[i],arr[leftIdx]);
            i=leftIdx;
        }
        else if(rightIdx<size && arr[i]<arr[rightIdx]){
            swap(arr[i],arr[rightIdx]);
            i=rightIdx;
        }
        else return;
    }
}
void display()
{
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    cout<<endl;
}
};
int main()
{
MaxHeap h(5);
h.insert(10);
h.insert(9);
h.insert(12);
h.insert(15);
h.insert(3);
//       10
//       / \
//     9    12
//    / \   / \
//   15  3  2 20
h.display();
// Max Heap
//       15
//       / \
//     12   10
//    / \   
//   9  3  
h.deletion();
h.display();
// Max Heap After Deletion
 //       12
//       / \
//     9   10
//    / 
//   3  
}

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