Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में दो बाइनरी मैक्स हीप को मर्ज करना

समस्या कथन

दो बाइनरी मैक्स हीप सरणियों के रूप में दिए गए हैं, उन्हें एक मैक्स हीप में मर्ज करें।

Heap1[] = {20, 17, 15, 10}
Heap2[] = {19, 13, 7}
Result[] = {20, 19, 15, 13, 17, 7, 10}

एल्गोरिदम

1. परिणाम स्टोर करने के लिए एक सरणी बनाएं
2. दी गई दोनों सरणियों को एक-एक करके परिणाम सरणी में कॉपी करें
3. पूर्ण मर्ज किए गए मैक्स हीप के निर्माण के लिए हीप बनाएं (build heap)

C++ उदाहरण

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

void heapify(int *arr, int n, int idx) {
    if (idx >= n) return;
    int l = 2 * idx + 1, r = 2 * idx + 2, max = idx;
    if (l < n && arr[l] > arr[max]) max = l;
    if (r < n && arr[r] > arr[max]) max = r;
    if (max != idx) {
        swap(arr[max], arr[idx]);
        heapify(arr, n, max);
    }
}

void createMaxHeap(int *arr, int n) {
    for (int i = n / 2 - 1; i >= 0; --i)
        heapify(arr, n, i);
}

void mergeMaxHeaps(int *arr1, int n1, int *arr2, int n2, int *result) {
    merge(arr1, arr1 + n1, arr2, arr2 + n2, result);
    createMaxHeap(result, n1 + n2);
}

void displayHeap(int *arr, int n) {
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int heap1[] = {20, 17, 15, 10};
    int heap2[] = {19, 13, 7};
    int result[SIZE(heap1) + SIZE(heap2)];
    cout << "First max heap: " << endl;
    displayHeap(heap1, SIZE(heap1));
    cout << "Second max heap: " << endl;
    displayHeap(heap2, SIZE(heap2));
    mergeMaxHeaps(heap1, SIZE(heap1), heap2, SIZE(heap2), result);
    cout << "Merged max heap: " << endl;
    displayHeap(result, SIZE(result));
    return 0;
}

आउटपुट

First max heap: 20 17 15 10
Second max heap: 19 13 7
Merged max heap: 20 19 15 13 17 7 10
  1. C++ में RMQ का उपयोग करके बाइनरी ट्री में LCA खोजें C++ में RMQ का उपयोग करके बाइनरी ट्री में LCA खोजें

    अवधारणा यह लेख ट्री में दो नोड्स के LCA को खोजने की समस्या को RMQ समस्या में कम करके हल करने की एक विधि बताता है। लोएस्ट कॉमन एंसेस्टर (LCA) एक रूटेड ट्री T में दो नोड्स a और b का लोएस्ट कॉमन एंसेस्टर (LCA) उस नोड के रूप में परिभाषित किया जाता है जो रूट से सबसे दूर स्थित होता है और जिसके दोनों a और

  1. C++ में एक रेखा पर अधिकतम बिंदु C++ में एक रेखा पर अधिकतम बिंदु

    मान लीजिए हमारे पास एक 2D तल है। हमें उन अधिकतम बिंदुओं की संख्या ढूंढनी है जो एक ही सीधी रेखा पर स्थित हैं। तो यदि बिंदु इस तरह हैं -तो 4 बिंदु हैंइसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -n := बिंदुओं की संख्या, यदि n < 3, तो n लौटाएंans := 2i को 1 से n - 1 तक की रेंज मेंcount := 0इं

  1. C++ में दो बाइनरी ट्री को मर्ज करना C++ में दो बाइनरी ट्री को मर्ज करना

    मान लीजिए हमारे पास दो बाइनरी ट्री हैं और जब हम एक को दूसरे पर ओवरलैप करते हैं, तो कुछ नोड्स ओवरलैप होते हैं जबकि अन्य नहीं। हमें इन्हें एक नए बाइनरी ट्री में मर्ज करना है। मर्ज का नियम यह है कि यदि दो नोड्स ओवरलैप होते हैं, तो उनके मानों को जोड़कर मर्ज किए गए नोड का नया मान बनाया जाता है। अन्यथा,