meaning - heap sort algorithm




ढेर का निर्माण करते समय, अद्वितीय ढेर है? (2)

मैं ढेर और ढेर छँटाई का अध्ययन कर रहा हूँ।
एक सरणी है: arr[8] = {6,9,3,1,8,7,2,11}
जब मैं ढेर का निर्माण करने की कोशिश कर रहा हूं, तो कोड और पेंसिल का उपयोग करके, मैं दो प्रकार के ढेर का सामना करना पड़ा।

कोड का उपयोग करते समय, MaxHeap: 11 9 7 6 8 3 2 1

सम्मिलन सिद्धांत का उपयोग करते समय, MaxHeap: 11 9 7 8 6 3 2 1


कोड जिसका मैं उपयोग कर रहा हूं:

int[] DoHeapSort(int[] value) {
    int length = value.length;

    for (int i = length / 2; i > 0; i--) {
        maxHeapify(value, i, length);
    }

    //print Heap
    for(int i = 0 ; i<value.length; i++)
        System.out.println(value[i]);

    return (value);
}


void maxHeapify(int[] array, int index, int heapSize) {
    int left = index * 2;
    int right = left + 1;
    int max = index;

    if (left <= heapSize && array[left - 1] > array[index - 1]) {
        max = left;
    }

    if (right <= heapSize && array[right - 1] > array[max - 1]) {
        max = right;
    }

    if (max != index) {
        swap(array, index - 1, max - 1);
        maxHeapify(array, max, heapSize);
    }
}

सिद्धांत, इस मामले में, ढेर के लिए एक और सरणी बनाएँ और क्रम में 6 से 11 डालें। (दूसरी ओर, कोड में जगह ढेर है)

मैक्सहैप दोनों के परिणाम ढेर सारे ढेर परिभाषा तब हीप अद्वितीय नहीं है? धन्यवाद


यह सही है। ढेर बाधा (जो यह है कि बच्चे अपने माता-पिता से अधिक नहीं हैं) पूरी तरह से ढेर को निर्दिष्ट नहीं करते हैं, इसलिए आमतौर पर एक संभव व्यवस्था से अधिक है


आइटम {1, 2, 3} पर विचार करें अधिकतम-ढेर के लिए दो वैध व्यवस्थाएं हैं:

    3              3
  /   \          /   \
 1     2        2     1

{3, 1, 2}      {3, 2, 1}

दोनों ही वैध अधिकतम-ढेर के लिए आवश्यक शर्तों को पूरा करते हैं।

एक पूर्ण ढेर को देखते हुए (अर्थात सभी स्तर पूर्ण हैं), आप किसी भी नोड के बच्चों को स्वैप कर सकते हैं और फिर भी एक वैध ढेर है। या, आम तौर पर, आप किसी भी नोड के बच्चों को तब तक स्वैप कर सकते हैं जब तक आप आकार संपत्ति बनाए रखेंगे

ध्यान दें कि "बच्चों को स्वैप करें" का मतलब है कि उस बच्चे पर लंगर डालने वाली संपूर्ण उप-योजना

बच्चों को गमागमन करने के अलावा, आप नोड्स को पुनर्व्यवस्थित कर सकते हैं।

उदाहरण के लिए, इस अधिकतम-ढेर पर विचार करें:

      10
    /    \
   9      8
  / \    / \
 7   6  5   4

अंतिम स्तर में नोड्स का क्रम अप्रासंगिक है; किसी भी पत्ती के नोड्स में से कोई एक या तो 8 या 9 का बच्चा हो सकता है। उन चार बच्चों के 24 संभव क्रमांतरण हैं।

अन्य व्यवस्था भी संभव है, उदाहरण के लिए: {10,9,6,7,8,5,4}

आपको कौन सी व्यवस्था मिलती है वह आपके सम्मिलन और हटाने के एल्गोरिदम की विशेषताओं पर निर्भर करती है, और सम्मिलन और निष्कासन के आदेश पर भी। या, एक सरणी से एक ढेर के निर्माण के मामले में (यानी ओ (एन) विधि), आप शुरू करते समय सरणी में आइटम का क्रम।





heap