Heap परिचय

एक heap trays के एक pile जैसा है एक pyramid में arranged जहां सबसे important item हमेशा top पर बैठता है, row by row left से right भरा जाता है।

In this page:

What is a Heap?
Complete Binary Tree
Parent and Child
Heap Property
Heap Practice

Syntax

markup

parent = (i - 1) // 2
left_child = 2 * i + 1
right_child = 2 * i + 2

What is a Heap?

एक heap एक complete binary tree है — मतलब हर level पूरी तरह filled है सिवाय शायद आखिरी के, जो left से right fill होता है — और वह completeness बिल्कुल वही है जो एक heap को node objects pointers के साथ उपयोग करने के बजाय एक plain array में efficiently store करना संभव बनाती है।

उदाहरण: What is a Heap?

#include <iostream>
using namespace std;
int main() {
    int heap[] = {50, 30, 40, 10, 20};
    cout << "Complete binary tree stored as array: every level full except last, filled left to right" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] heap = {50, 30, 40, 10, 20};
        System.out.println("Complete binary tree stored as array: every level full except last, filled left to right");
    }
}

heap = [50, 30, 40, 10, 20]
print("Complete binary tree stored as array: every level full except last, filled left to right")

#include <stdio.h>
int main() {
    int heap[] = {50, 30, 40, 10, 20};
    printf("Complete binary tree stored as array: every level full except last, filled left to right\n");
    return 0;
}

Complete Binary Tree

चूंकि एक heap हर level को left से right बिना gaps के भरता है, array indices और tree के parent/child relationships के बीच एक direct, predictable formula mapping है, इसलिए tree structure सिर्फ array positions से reconstruct किया जा सकता है।

उदाहरण: Complete Binary Tree

#include <iostream>
using namespace std;
int main() {
    int heap[] = {50, 30, 40, 10, 20};
    int i = 1;
    cout << "Parent of index " << i << " is index " << (i-1)/2 << " (predictable via formula, no pointers needed)" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int i = 1;
        System.out.println("Parent of index " + i + " is index " + (i-1)/2 + " (predictable via formula, no pointers needed)");
    }
}

i = 1
print("Parent of index", i, "is index", (i - 1) // 2, "(predictable via formula, no pointers needed)")

#include <stdio.h>
int main() {
    int i = 1;
    printf("Parent of index %d is index %d (predictable via formula, no pointers needed)\n", i, (i-1)/2);
    return 0;
}

Parent and Child

Array index i पर stored एक node के लिए, इसका left child index 2i+1 पर और इसका right child index 2i+2 पर बैठता है — ये formulas heap operations को pointers follow करने के बजाय simple arithmetic उपयोग करके tree navigate करने देते हैं।

उदाहरण: Parent and Child

#include <iostream>
using namespace std;
int main() {
    int i = 1;
    cout << "left child=" << 2*i+1 << " right child=" << 2*i+2 << " for parent index " << i << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int i = 1;
        System.out.println("left child=" + (2*i+1) + " right child=" + (2*i+2) + " for parent index " + i);
    }
}

i = 1
print("left child=", 2*i+1, "right child=", 2*i+2, "for parent index", i)

#include <stdio.h>
int main() {
    int i = 1;
    printf("left child=%d right child=%d for parent index %d\n", 2*i+1, 2*i+2, i);
    return 0;
}

Heap Property

एक max heap enforce करता है कि हर parent इसके children से बड़ा या बराबर है, जो गारंटी देता है कि पूरी structure में सबसे बड़ी value हमेशा root पर बैठती है; एक min heap इसका उल्टा enforce करता है, root पर सबसे छोटी value रखते हुए।

उदाहरण: Heap Property

#include <iostream>
using namespace std;
int main() {
    int heap[] = {50, 30, 40, 10, 20};
    cout << "Max heap: every parent >= children, so heap[0]=" << heap[0] << " is the largest value overall" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] heap = {50, 30, 40, 10, 20};
        System.out.println("Max heap: every parent >= children, so heap[0]=" + heap[0] + " is the largest value overall");
    }
}

heap = [50, 30, 40, 10, 20]
print("Max heap: every parent >= children, so heap[0]=", heap[0], "is the largest value overall")

#include <stdio.h>
int main() {
    int heap[] = {50, 30, 40, 10, 20};
    printf("Max heap: every parent >= children, so heap[0]=%d is the largest value overall\n", heap[0]);
    return 0;
}

Heap Practice

Heaps priority queues (जहां आपको हमेशा highest या lowest priority item तक fast access चाहिए) के पीछे standard structure हैं और heap sort का भी आधार हैं, क्योंकि heap के root को बार-बार हटाना sorted order में elements देता है।

उदाहरण: Heap Practice

#include <iostream>
using namespace std;
int main() {
    cout << "Heaps back priority queues: always fast access to the highest/lowest priority item" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Heaps back priority queues: always fast access to the highest/lowest priority item");
    }
}

print("Heaps back priority queues: always fast access to the highest/lowest priority item")

#include <stdio.h>
int main() {
    printf("Heaps back priority queues: always fast access to the highest/lowest priority item\n");
    return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Serialize and Deserialize Tree Next Lesson → Min Heap and Max Heap