Heap

A heap is a tree-based data structure that satisfies the heap property, which specifies the ordering of the elements in the heap. There are two types of heaps: a max-heap, where the parent nodes are larger than their child nodes, and a min-heap, where the parent nodes are smaller than their child nodes.

Operations of a Heap:

Insert: Inserts a new element into the heap by adding it as the last leaf node and then restoring the heap property by repeatedly swapping the new element with its parent node until the heap property is satisfied.

Delete: Removes the root element from the heap and restores the heap property by replacing the root with the last element in the heap and then repeatedly swapping the new root with its child nodes until the heap property is satisfied.

Peek: Returns the value of the root element without removing it from the heap.

Heapify: Given an array of elements, converts it into a heap by repeatedly applying the insert operation on each element.

Real-life applications of Heap:

Heap Sort: Heap sort is a sorting algorithm that uses a heap to sort an array of elements in ascending or descending order.

Priority Queue: A priority queue can be implemented using a heap, where the element with the highest priority is always at the root of the heap.

Dijkstra's Shortest Path Algorithm: Dijkstra's algorithm uses a priority queue implemented using a min-heap to find the shortest path between two nodes in a graph.

Operating System Memory Management: Operating systems use a heap data structure to allocate and deallocate memory blocks.

Event-Driven Simulation: In event-driven simulation, events are stored in a priority queue implemented using a heap, where the next event to be processed is always at the root of the heap.


#include <iostream>
using namespace std;

class MaxHeap {
private:
    int *heapArr;
    int heapSize;
    int maxCapacity;

public:
    MaxHeap(int capacity) {
        heapArr = new int[capacity];
        heapSize = 0;
        maxCapacity = capacity;
    }

    void insert(int value) {
        if (heapSize >= maxCapacity) {
            cout << "Heap overflow error!" << endl;
            return;
        }
        heapArr[heapSize] = value;
        heapifyUp(heapSize);
        heapSize++;
    }

    void remove() {
        if (heapSize == 0) {
            cout << "Heap underflow error!" << endl;
            return;
        }
        heapArr[0] = heapArr[heapSize - 1];
        heapSize--;
        heapifyDown(0);
    }

    int peek() {
        if (heapSize == 0) {
            cout << "Heap is empty!" << endl;
            return -1;
        }
        return heapArr[0];
    }

private:
    void heapifyUp(int index) {
        int parent = (index - 1) / 2;
        if (parent >= 0 && heapArr[index] > heapArr[parent]) {
            swap(heapArr[index], heapArr[parent]);
            heapifyUp(parent);
        }
    }

    void heapifyDown(int index) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int largest = index;
        if (leftChild < heapSize && heapArr[leftChild] > heapArr[largest]) {
            largest = leftChild;
        }
        if (rightChild < heapSize && heapArr[rightChild] > heapArr[largest]) {
            largest = rightChild;
        }
        if (largest != index) {
            swap(heapArr[index], heapArr[largest]);
            heapifyDown(largest);
        }
    }
};

int main() {
    MaxHeap heap(10);
    heap.insert(5);
    heap.insert(3);
    heap.insert(8);
    heap.insert(2);
    heap.insert(10);
    heap.insert(7);

    cout << "Max value in heap: " << heap.peek() << endl;

    heap.remove();

    cout << "Max value in heap after remove: " << heap.peek() << endl;

    return 0;
}


// OUTPUT :

// Max value in heap: 10
// Max value in heap after remove: 8

In this example, we define a class MaxHeap that has three private variables: heapArr (an integer array), heapSize (an integer representing the current number of elements in the heap), and maxCapacity (an integer representing the maximum capacity of the heap). The MaxHeap class has three public member functions: insert, remove, and peek, which insert an element into the heap, remove the root element from the heap, and return the root element of the heap (i.e., the maximum element), respectively.

The MaxHeap class also has two private member functions: heapifyUp and heapifyDown, which restore the heap property by moving an element up the heap (i.e., from a child node to its parent node) or down the heap (i.e., from a parent node to its child nodes), respectively.

PRACTICE PROBLEMS :

Kth Largest Element in an Array

Last Stone Weight