Min Heap और Max Heap

एक max heap में सबसे बड़ा number top पर है और एक min heap में सबसे छोटा, tallest या shortest kid के prizes के दो अलग pyramids जैसा।

In this page:

Max Heap
Min Heap
Root Element
Compare Heaps
Practice

Syntax

markup

import heapq
min_heap = []
heapq.heappush(min_heap, value)
smallest = heapq.heappop(min_heap)

# max heap: store negated values
heapq.heappush(max_heap, -value)

Max Heap

एक max heap में, हर parent node की value इसके दोनों children की values से बड़ी या बराबर है, जो recursively गारंटी देता है कि पूरी structure में सबसे बड़ी single value root पर बैठती है।

उदाहरण: Max Heap

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> maxHeap;
    maxHeap.push(10); maxHeap.push(30); maxHeap.push(20);
    cout << "Max heap top: " << maxHeap.top() << endl;
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(10); maxHeap.add(30); maxHeap.add(20);
        System.out.println("Max heap top: " + maxHeap.peek());
    }
}

import heapq
max_heap = []
for v in [10, 30, 20]:
    heapq.heappush(max_heap, -v)
print("Max heap top:", -max_heap[0])

#include <stdio.h>
int main() {
    int heap[] = {30, 10, 20};
    printf("Max heap top: %d\n", heap[0]);
    return 0;
}

Min Heap

एक min heap में, हर parent node की value इसके दोनों children की values से छोटी या बराबर है, जो recursively गारंटी देता है कि पूरी structure में सबसे छोटी single value root पर बैठती है।

उदाहरण: Min Heap

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(10); minHeap.push(30); minHeap.push(20);
    cout << "Min heap top: " << minHeap.top() << endl;
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(10); minHeap.add(30); minHeap.add(20);
        System.out.println("Min heap top: " + minHeap.peek());
    }
}

import heapq
min_heap = []
for v in [10, 30, 20]:
    heapq.heappush(min_heap, v)
print("Min heap top:", min_heap[0])

#include <stdio.h>
int main() {
    int heap[] = {10, 30, 20};
    printf("Min heap top: %d\n", heap[0]);
    return 0;
}

Root Element

इन properties के कारण, root हमेशा एक max heap में current highest-priority element तक, या एक min heap में current lowest-priority element तक immediate access देता है, structure के किसी और हिस्से को scan किए बिना।

उदाहरण: Root Element

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> maxHeap;
    maxHeap.push(5); maxHeap.push(15);
    cout << "Root gives O(1) access to highest priority: " << maxHeap.top() << endl;
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(5); maxHeap.add(15);
        System.out.println("Root gives O(1) access to highest priority: " + maxHeap.peek());
    }
}

import heapq
max_heap = []
for v in [5, 15]:
    heapq.heappush(max_heap, -v)
print("Root gives O(1) access to highest priority:", -max_heap[0])

#include <stdio.h>
int main() {
    int heap[] = {15, 5};
    printf("Root gives O(1) access to highest priority: %d\n", heap[0]);
    return 0;
}

Compare Heaps

दोनों heap types structurally identical हैं — वही complete binary tree, वही array storage, वही parent/child index formulas — insertions और removals के दौरान heap property maintain करने के लिए उपयोग किए comparison की direction में ही अलग।

उदाहरण: Compare Heaps

#include <iostream>
using namespace std;
int main() {
    cout << "Same structure and formulas, only the comparison direction differs (>= for max, <= for min)" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Same structure and formulas, only the comparison direction differs (>= for max, <= for min)");
    }
}

print("Same structure and formulas, only the comparison direction differs (>= for max, <= for min)")

#include <stdio.h>
int main() {
    printf("Same structure and formulas, only the comparison direction differs (>= for max, <= for min)\n");
    return 0;
}

Practice

उन्हीं values के set से एक max heap और एक min heap दोनों बनाना और उनकी resulting shapes को side by side compare करना यह देखने का एक तेज़ तरीका है कि values एक जैसे structure उपयोग करने के बावजूद genuinely अलग tree arrangements में end होती हैं।

उदाहरण: Practice

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (int v : {4, 9, 1, 7}) { maxHeap.push(v); minHeap.push(v); }
    cout << "Same input, max top=" << maxHeap.top() << " min top=" << minHeap.top() << endl;
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int v : new int[]{4,9,1,7}) { maxHeap.add(v); minHeap.add(v); }
        System.out.println("Same input, max top=" + maxHeap.peek() + " min top=" + minHeap.peek());
    }
}

import heapq
values = [4, 9, 1, 7]
max_heap = []
min_heap = []
for v in values:
    heapq.heappush(max_heap, -v)
    heapq.heappush(min_heap, v)
print("Same input, max top=", -max_heap[0], "min top=", min_heap[0])

#include <stdio.h>
int main() {
    int values[] = {4,9,1,7};
    int maxV = values[0], minV = values[0];
    for (int i=1;i<4;i++){ if(values[i]>maxV) maxV=values[i]; if(values[i]<minV) minV=values[i]; }
    printf("Same input, max top=%d min top=%d\n", maxV, minV);
    return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Heap Introduction Next Lesson → Heap Sort