बाइनरी हीप की सरणी प्रतिनिधित्व

बाइनरी हीप क्या है?

एक बाइनरी हीप एक पूर्ण बाइनरी ट्री है जो हीप क्रम संपत्ति को संतुष्ट करता है।

हीप के प्रकार

सरणी प्रतिनिधित्व

बाइनरी हीप को सरणी में कुशलता से संग्रहीत किया जाता है:

• मूल सूचकांक: 0
• यदि नोड सूचकांक i पर है:
  • बायां बच्चा: 2i + 1
  • दायां बच्चा: 2i + 2
  • माता-पिता: (i - 1) / 2

उदाहरण: मिन हीप

ट्री:
        1
      /   \
     4     7
    / \   / \
   6   9 10  8

सरणी: [1, 4, 7, 6, 9, 10, 8]
इंडेक्स: 0  1  2  3  4  5  6

उदाहरण: मैक्स हीप

ट्री:
        11
      /    \
     8      9
    / \    / \
   6   4  5   1

सरणी: [11, 8, 9, 6, 4, 5, 1]
इंडेक्स: 0   1  2  3  4  5  6

C प्रोग्राम: हीप ऑपरेशन

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int arr[MAX_SIZE];
    int size;
} MinHeap;

void swap(int *a, int *b) {
    int temp = *a; *a = *b; *b = temp;
}

void heapify_up(MinHeap *h, int i) {
    while (i > 0 && h->arr[(i-1)/2] > h->arr[i]) {
        swap(&h->arr[i], &h->arr[(i-1)/2]);
        i = (i-1)/2;
    }
}

void heapify_down(MinHeap *h, int i) {
    int smallest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;
    
    if (left < h->size && h->arr[left] < h->arr[smallest])
        smallest = left;
    if (right < h->size && h->arr[right] < h->arr[smallest])
        smallest = right;
    
    if (smallest != i) {
        swap(&h->arr[i], &h->arr[smallest]);
        heapify_down(h, smallest);
    }
}

void insert(MinHeap *h, int val) {
    if (h->size == MAX_SIZE) return;
    h->arr[h->size] = val;
    h->size++;
    heapify_up(h, h->size - 1);
}

int extract_min(MinHeap *h) {
    if (h->size == 0) return -1;
    int min = h->arr[0];
    h->arr[0] = h->arr[h->size - 1];
    h->size--;
    heapify_down(h, 0);
    return min;
}

void print_heap(MinHeap *h) {
    for (int i = 0; i < h->size; i++)
        printf("%d ", h->arr[i]);
    printf("\n");
}

int main() {
    MinHeap h = {.size = 0};
    int vals[] = {10, 4, 7, 1, 8, 3, 9};
    
    for (int i = 0; i < 7; i++)
        insert(&h, vals[i]);
    
    printf("हीप: ");
    print_heap(&h);
    
    printf("निकाला गया मिन: %d\n", extract_min(&h));
    printf("हीप: ");
    print_heap(&h);
    
    return 0;
}

आउटपुट

हीप: 1 4 3 10 8 7 9
निकाला गया मिन: 1
हीप: 3 4 7 10 8 9

जटिलता

अनुप्रयोग

• प्राथमिकता कतार कार्यान्वयन
• हीप सॉर्ट - O(n log n) सॉर्टिंग
• डिज्क्स्ट्रा/प्रिम एल्गोरिदम
• मेडियन फाइंडिंग - दो हीप्स
• K सबसे बड़े/सबसे छोटे तत्व