1-आरी ढेर प्रकार?

Question

कुछ समय पहले हमें एक सी प्रोग्राम लिखने के लिए एक असाइनमेंट दिया गया था जो डी-आरी अधिकतम-ढेर (एक ढेर जहां प्रत्येक नोड के बच्चों के लिए है) का उपयोग करके एन संख्याओं की एक सरणी टाइप करता है। कार्यक्रम को उपयोगकर्ता को डी के मान को इनपुट करने के लिए पूछना आवश्यक था, जो कि 2 और सरणी के आकार के बीच का मान था। जबकि मैं अपने प्रोग्राम की जांच कर रहा था, मैंने गलती से डी के मान के रूप में 1 दर्ज किया, और किसी भी तरह एल्गोरिदम 1-आरी ढेर का उपयोग करके सरणी को सही ढंग से क्रमबद्ध करने में सफल रहा, हालांकि इसे डी के सामान्य मानों से अधिक समय लगता था।

यह कैसे संभव है? एक 1-आरी ढेर एक ढेर भी नहीं है, यह सिर्फ एक सूची की तरह है, प्रत्येक नोड में केवल एक बच्चा होता है। क्या कोई यह समझा सकता है कि यह सॉर्टिंग कैसे हो सकती है?

Answer 1

एक 1-ary ढेर अभी भी एक ढेर है, और संतुष्ट सभी अपरिवर्तनशीलताओं कि एक ढेर प्रकार के लिए आवश्यक हैं:

• पहला तत्व सबसे बड़ा तत्व है।
• पर्कोलेशन शीर्ष तत्व को अपनी सही स्थिति में ले जा सकता है।

प्रैक्टिस में, 1-आरी ढेर एक पेड़ है जहां प्रत्येक नोड में एक बच्चा होता है - इसे एकल लिंक्ड सूची के रूप में भी जाना जाता है। इसके अलावा, ढेर बाधा का मतलब है कि बच्चे नोड माता-पिता नोड से छोटा है। तो, बस शब्दों में कहें, एक 1-आरी ढेर एक सिंगल लिंक्ड सूची है जो रिवर्स ऑर्डर में क्रमबद्ध है।

पहले स्थान पर ढेर का निर्माण एक सम्मिलन प्रकार के बराबर है (सूची में सभी वस्तुओं को एक-एक करके विभाजित करें)। एक बार ऐसा करने के बाद, पहले तत्व को हटाने से सभी का सबसे बड़ा तत्व पैदा होता है, और बाद में पिक्चरेशन प्रत्येक आइटम को सूची में एक स्तर तक ले जाता है।