C++ प्रोग्राम: मैक्स हीप इम्प्लीमेंटेशन

एक बाइनरी हीप एक पूर्ण बाइनरी ट्री है जो या तो मिन हीप या मैक्स हीप होता है। एक मैक्स बाइनरी हीप में, रूट पर की हीप में मौजूद सभी कीज़ में अधिकतम होनी चाहिए। यह गुण बाइनरी ट्री में सभी नोड्स के लिए रिकर्सिवली सत्य होना चाहिए। मिन बाइनरी हीप मिन हीप के समान है।

एल्गोरिदम

max_heap के लिए:

शुरुआत
    फ़ंक्शन max_heap() घोषित करें
    j, t को integer डेटाटाइप घोषित करें
    t = a[m] इनिशियलाइज़ करें
    j = 2 * m
    while (j <= n) करें
        if (j < n और a[j+1] > a[j]) तो
            j = j + 1
        if (t > a[j]) तो
            ब्रेक
        else if (t <= a[j]) तो
            a[j / 2] = a[j]
            j = 2 * j
    a[j/2] = t
    लौटाएं
समाप्ति

build_maxheap के लिए:

शुरुआत
    फ़ंक्शन build_maxheap(int* a, int n) घोषित करें
    k को integer डेटाटाइप घोषित करें
    for(k = n/2; k >= 1; k--)
        फ़ंक्शन max_heap(a, k, n) कॉल करें
समाप्ति

उदाहरण

#include <iostream>
#include <vector>
using namespace std;

void max_heap(vector& a, int m, int n) {
    int j, t;
    t = a[m];
    j = 2 * m;
    while (j <= n) {
        if (j < n && a[j+1] > a[j])
            j = j + 1;
        if (t > a[j])
            break;
        else if (t <= a[j]) {
            a[j / 2] = a[j];
            j = 2 * j;
        }
    }
    a[j/2] = t;
}

void build_maxheap(vector& a, int n) {
    for (int k = n/2; k >= 1; k--) {
        max_heap(a, k, n);
    }
}

int main() {
    int n;
    cout << "ऐरे के एलिमेंट्स की संख्या दर्ज करें: ";
    cin >> n;
    vector a(n + 1); // 1-आधारित इंडेक्सिंग
    
    for (int i = 1; i <= n; i++) {
        cout << "एलिमेंट " << i << " दर्ज करें: ";
        cin >> a[i];
    }
    
    build_maxheap(a, n);
    cout << "मैक्स हीप:\n";
    for (int i = 1; i <= n; i++) {
        cout << a[i] << endl;
    }
    return 0;
}

आउटपुट

ऐरे के एलिमेंट्स की संख्या दर्ज करें: 5
एलिमेंट 1 दर्ज करें: 7
एलिमेंट 2 दर्ज करें: 6
एलिमेंट 3 दर्ज करें: 2
एलिमेंट 4 दर्ज करें: 1
एलिमेंट 5 दर्ज करें: 4
मैक्स हीप:
7
6
2
1
4

आधुनिक C++: std::priority_queue (मैक्स हीप - डिफ़ॉल्ट)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // मैक्स हीप (डिफ़ॉल्ट)
    priority_queue maxHeap;
    
    maxHeap.push(7);
    maxHeap.push(6);
    maxHeap.push(2);
    maxHeap.push(1);
    maxHeap.push(4);
    
    cout << "मैक्स हीप एलिमेंट्स (सॉर्टेड क्रम में): ";
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    cout << endl;
    
    return 0;
}

आउटपुट

मैक्स हीप एलिमेंट्स (सॉर्टेड क्रम में): 7 6 4 2 1

मिन हीप vs मैक्स हीप

हीप सॉर्ट (मैक्स हीप का उपयोग करके)

void heapSort(vector& arr) {
    int n = arr.size() - 1; // 1-आधारित
    build_maxheap(arr, n);
    
    for (int i = n; i >= 2; i--) {
        swap(arr[1], arr[i]); // मैक्स को अंत में ले जाएं
        max_heap(arr, 1, i - 1); // कम हुए हीप पर हीपिफाई
    }
}