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

Question

मैं ढेर & ढेर सॉर्टिंग का अध्ययन कर रहा हूं।
एक सरणी है: 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); 
    } 
} 

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

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

Answer 1

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

Answer 2

आइटम {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}।

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