Unveiling Heap

Introduction

Heap is a complete binary tree Data Structure ie every node should have a value greater than or equal to its descendants. Depending on the type of heap there are Max Heap or Min Heap. Max Heap can be defined as a binary tree where the root node is the largest value and every parent node has a higher value than its children. Whereas, a Min Heap is where the root node has the minimum value and every parent node has a lesser value than its children. The height of a heap is always log(n) as it is a complete binary tree.

Why Heap?

If you're looking for a data structure that offers efficient insertions and deletions, along with quick access to the minimum or maximum element, the heap may be a perfect choice. Also known as a priority queue, the heap is a tree-based data structure that organizes its elements in a way that always keeps the largest or smallest element at the top. The operations of inserting, deleting, and finding the minimum or maximum element in a heap can all be performed in O(log n) time, where n is the number of elements in the heap. It requires less memory compared to other data structures, such as linked lists or arrays, as it stores elements in a complete binary tree structure. The heap-sort algorithm is an efficient sorting algorithm that has a worst-case time complexity of O(n log n).

If a Node is at index i, then:

Its left child is at 2*i

Its right child is at 2*i+1

Its parent is at the floor value of i/2

Insertion in Heap

void Insert(int A[],int n){
    int i = n ; 
    int temp = A[i];  //ele to be inserted

    while(i>1 && temp>A[i/2]){    
        A[i] = A[i/2];   
        i=i/2;
    }
    A[i] = temp; 
}

Deletion in Heap

Only the root element can be deleted from the heap.

int Delete(int A[],int n){
    int i , j , x , temp ,val;
    val = A[1];    //root element
    x = A[n];
    A[1] = A[n];
    A[n] = val ;
    i = 1,j=i*2;    

    while(j<n-1){
        if(A[j+1]>A[j])  //comparing left and right child of the node
            j = j+1;   
        if(A[i]<A[j]){       //comparing the parent and the largest child
            temp = A[i];
            A[i] = A[j];
            A[j] = temp ; 
            i = j ; 
            j = 2*j; 
        }
        else break ; 
    }
    return val ; 
}

Heapify

Heapify is an operation that is related to the creation of the Heap where the direction of adjustment is different. Here we start from the last element of the array and adjust it every time a new element is added.

void Heapify(int A[], int n){
  // # of leaf elements: (n+1)/2, index of last leaf element's parent= (n/2)-1
    for (int i=(n/2)-1; i>=0; i--){

        int j = 2 * i + 1;  // Left child for current i

        while(j < n-1){
            // Compare left and right children of current i
            if (A[j] < A[j+1]){
                j = j+1;
            }

            // Compare parent and largest child
            if (A[i] < A[j]){
                swap(A, i, j);
                i = j;
                j = 2 * i + 1;
            } else {
                break;
            }
        }
    }
}

Heap as Priority Queue

Heap is the best data structure for implementing the Priority queue.

priority_queue<int> maxheap;

priority_queue<int,vector<int>,greater<int>> minheap;

Conclusion

Overall Heap data structure has various applications in itself. It is commonly used in the implementation of priority queues, heap sort algorithms and various graph algorithms. It is well-suitable for insertion, deletion, and retrieving and has Space and Time efficiency. Additionally, heaps are easy to implement and are used in a variety of algorithms and data structures.