🔺 Heap Data Structure – Comprehensive Study Guide

A **Heap** is a **binary tree** that satisfies the **heap property**, where the parent node is either **greater** (Max-Heap) or **smaller** (Min-Heap) than its child nodes.

⚡ Why Use Heap?

✅ **Efficient priority queue operations in O(log n) time.**
🚀 **Used in Graph Algorithms like Dijkstra & Prim's MST.**
📡 **Used in scheduling tasks and memory management.**
🔄 **Provides an efficient sorting algorithm (Heap Sort).**

📌 Types of Heaps

📥 1. Min-Heap (Root is the Smallest Element)

Every parent node has a **value smaller** than its child nodes.

📤 2. Max-Heap (Root is the Largest Element)

Every parent node has a **value greater** than its child nodes.

🛠️ Heap Operations

📌 1. Insertion in Heap (O(log n))

New elements are added at the **end of the heap** and moved up to maintain heap order.


                void insert(vector& heap, int value) {
                    heap.push_back(value);
                    int index = heap.size() - 1;
            
                    while (index > 0) {
                        int parent = (index - 1) / 2;
                        if (heap[parent] > heap[index]) { // Swap for Min-Heap
                            swap(heap[parent], heap[index]);
                            index = parent;
                        } else {
                            break;
                        }
                    }
                }

📌 2. Deletion (Removing the Root) (O(log n))

The root is replaced by the last element, and heapify is applied.


                void deleteRoot(vector& heap) {
                    if (heap.empty()) return;
                    heap[0] = heap.back();
                    heap.pop_back();
                    heapify(heap, 0);
                }

📌 3. Heapify (O(log n))

Restores the heap property by pushing down elements.


                void heapify(vector& heap, int index) {
                    int left = 2 * index + 1;
                    int right = 2 * index + 2;
                    int smallest = index;
            
                    if (left < heap.size() && heap[left] < heap[smallest]) smallest = left;
                    if (right < heap.size() && heap[right] < heap[smallest]) smallest = right;
            
                    if (smallest != index) {
                        swap(heap[index], heap[smallest]);
                        heapify(heap, smallest);
                    }
                }

📌 4. Build-Heap from an Array (O(n))

Heapifies all non-leaf nodes.


                void buildHeap(vector& heap) {
                    for (int i = heap.size() / 2 - 1; i >= 0; i--) {
                        heapify(heap, i);
                    }
                }

📏 Heap Sort (O(n log n))

Heap Sort is an efficient **comparison-based sorting algorithm**.


                void heapSort(vector& arr) {
                    buildHeap(arr);
                    for (int i = arr.size() - 1; i > 0; i--) {
                        swap(arr[0], arr[i]);
                        heapify(arr, 0);
                    }
                }

📡 Heap in Graph Algorithms

📌 1. Dijkstra’s Algorithm (O(V + E log V))


                void dijkstra(vector>>& graph, int src) {
                    priority_queue, vector>, greater>> pq;
                    vector dist(graph.size(), INT_MAX);
            
                    pq.push({0, src});
                    dist[src] = 0;
            
                    while (!pq.empty()) {
                        int u = pq.top().second;
                        pq.pop();
            
                        for (auto edge : graph[u]) {
                            int v = edge.first, weight = edge.second;
                            if (dist[u] + weight < dist[v]) {
                                dist[v] = dist[u] + weight;
                                pq.push({dist[v], v});
                            }
                        }
                    }
                }

⏳ Time Complexity Analysis

Operation	Time Complexity
Insert	O(log n)
Delete	O(log n)
Heapify	O(log n)
Build Heap	O(n)
Heap Sort	O(n log n)

🌍 Real-World Applications of Heap

📡 **Priority Queues** – Used in **CPU scheduling, event-driven simulations.**
🔍 **Dijkstra’s Algorithm** – Finds **shortest path in graphs.**
🗂 **Memory Management** – Used in **garbage collection.**
📊 **Data Compression (Huffman Coding)** – Efficient text encoding.

🔺 Heap Data Structure – Comprehensive Study Guide

⚡ Why Use Heap?

📌 Types of Heaps

📥 **1. Min-Heap (Root is the Smallest Element)**

📤 **2. Max-Heap (Root is the Largest Element)**

🛠️ Heap Operations

📌 **1. Insertion in Heap (O(log n))**

📌 **2. Deletion (Removing the Root) (O(log n))**

📌 **3. Heapify (O(log n))**

📌 **4. Build-Heap from an Array (O(n))**