make_heap का बिंदु क्या है?

Question

क्या कोई मुझे एसटीएल ढेर कार्यों जैसे make_heap बता सकता है? किसी ने कभी उनका इस्तेमाल क्यों किया? क्या कोई व्यावहारिक उपयोग है?

Answer 1

बनाए रखने यदि आप एक priority queue एक सूची से बाहर बनाना चाहते हैं करने के लिए उपयोग किया जाता है, ठीक है, आप make_heap उपयोग कर सकते हैं:

आंतरिक रूप से, एक ढेर एक पेड़ जहां है मानों के लिए प्रत्येक नोड लिंक अपने मूल्य से अधिक नहीं है। ढेर में हमेशा में सबसे अधिक मूल्य जा रहा है, make_heap द्वारा उत्पन्न बजाय पेड़ में एक तत्व स्मृति लेने वाली लिंक के द्वारा निर्धारित किया जा रहा है क्रम में अपनी पूर्ण स्थिति से निर्धारित होता है की विशिष्ट स्थिति, * पहले साथ ढेर।

ढेर जो अपने ढेर गुण को बनाए रखने के जोड़ सकते हैं या कार्यों का उपयोग करके लघुगणक समय में यह से तत्वों हटाने push_heap और pop_heap करने के लिए, अनुमति देते हैं।

Answer 2

वे का निर्माण और Heap data structure

Answer 3

उपरोक्त के अतिरिक्त, एसटीएल के छँटाई एल्गोरिथ्म introsort है, जो quicksort और heapsort का एक मिश्रण है (यह quicksort से अधिक सफल नहीं होता तो पूर्व प्रदर्शन अच्छा न हो heapsort के लिए)। make_heap एक ढेर संरचना बनाता है, जो हेरसोर्ट चलाने के लिए आवश्यक है, जो introsort के लिए आवश्यक है।

Answer 4

आपके प्रत्यक्ष प्रश्न का उत्तर एल्गोरिदम और डेटा संरचनाओं में एक वर्ग द्वारा किया जाएगा। कंप्यूटर विज्ञान में एल्गोरिदम में हीप का उपयोग पूरे स्थान पर किया जाता है। नीचे दिए गए make_heap फ़ंक्शन से उद्धरण के लिए, "एक ढेर एक पेड़ है जहां प्रत्येक नोड मूल्यों से लिंक होता है जो अपने मूल्य से अधिक नहीं होता है।" हालांकि एक ढेर के लिए बहुत से अनुप्रयोग हैं, जो मैं अक्सर उपयोग करता हूं वह खोज समस्याओं में होता है जब आप एन मानों की क्रमबद्ध सूची का ट्रैक रखना चाहते हैं।

जब मुझे पहली बार एसटीएल ढेर कार्यों का सामना करना पड़ा तो मुझे आपके साथ भ्रम था। मेरा सवाल हालांकि थोड़ा अलग था। मैंने सोचा "स्टडी :: वेक्टर के रूप में डेटा संरचनाओं के समान वर्ग में एसटीएल ढेर क्यों नहीं है?" मैंने सोचा था कि यह इस तरह काम करना चाहिए:

std::heap<int> my_heap; 
my_heap.heap_insert(7); 
my_heap.heap_insert(3); 

एसटीएल ढेर कार्यों के पीछे विचार यह है कि वे आप std :: वेक्टर सहित कई अलग अलग अंतर्निहित एसटीएल कंटेनर, से बाहर एक ढेर डेटा संरचना बनाने के लिए अनुमति देते हैं। यदि आप अपने कार्यक्रमों में कहीं और उपयोग के लिए कंटेनर को पास करना चाहते हैं तो यह वास्तव में उपयोगी हो सकता है। यह भी थोड़ा अच्छा है, क्योंकि आप अपने ढेर के अंतर्निहित कंटेनर का चयन कर सकते हैं यदि आप std :: vector के अलावा किसी अन्य चीज़ का उपयोग करना चुनते हैं।

template <class RandomAccessIterator> 
    void make_heap (RandomAccessIterator first, RandomAccessIterator last); 

इसका मतलब यह है भी विधि हस्ताक्षर में वैकल्पिक आप अलग अलग चीजें हैं जो आप कोशिश कर सकते हैं के बारे में और अधिक पढ़ सकते है, कि तुम एक ढेर एक तुलनित्र में विभिन्न कंटेनरों के बहुत सारे बना सकते हैं: तुम सब वास्तव में जरूरत है निम्नलिखित हैं make_heap फ़ंक्शन के लिए एसटीएल पृष्ठों में।

लिंक:

• Heap Data Structure
• make_heap function

Answer 5

आप std::push_heap() और std::pop_heap() के साथ std::make_heap() उपयोग करने के लिए एक सदिश या सरणी के शीर्ष पर एक द्विआधारी ढेर बनाए रखने के लिए अपेक्षा की जाती है; बाद के दो कार्य ढेर आविष्कार बनाए रखते हैं। आप इस तरह के एक ढेर को क्रमबद्ध करने के लिए std::heap_sort() का भी उपयोग कर सकते हैं। हालांकि यह सच है कि आप प्राथमिकता कतार के लिए std::priority_queue का उपयोग कर सकते हैं, यह आपको इसके अंदर आने की अनुमति नहीं देता है, जो शायद आप करना चाहते हैं। इसके अलावा, std::make_heap() और std::heap_sort() एक साथ सी ++ में हेपॉर्ट करने का एक बहुत ही सरल तरीका बनाते हैं।

Answer 6

एक [बाइनरी] ढेर बनाने के लिए अनिवार्य रूप से दो तरीके हैं: एक खाली ढेर बनाएं और प्रत्येक तत्व को एक बार में डालें, या मूल्यों की एक श्रृंखला लें और उन्हें स्वस्थ करें।

एक ढेर पर प्रत्येक पुश ऑपरेशन ओ (लॉगन) समय लेता है ताकि यदि आप एन आइटम को ढेर पर दबा रहे हैं तो यह ओ (एनएलओएनएन) समय लेगा। हालांकि मूल्यों की एक सरणी से एक बाइनरी ढेर बनाने के लिए केवल ओ (एन) समय लगता है।

इस प्रकार यह प्रत्येक तत्व को सरणी (या अन्य कंटेनर जो यादृच्छिक एक्सेस इटरेटर्स का समर्थन करता है) में डालने के लिए और अधिक समझ में आता है और उसके बाद डालने पर ढेर संरचना को बनाए रखने के लिए सरणी पर make_heap() को कॉल करता है।

Answer 7

std::make_heap अभ्यास में लगभग कभी भी उपयोग नहीं किया जाना चाहिए। हालांकि यह सच है कि ढेर प्राथमिकता कतारों के लिए उपयोगी हैं, यह स्पष्ट नहीं करता है कि आप संरचना को मैन्युअल रूप से बनाए रखना क्यों चाहते हैं। std::priority_queue में एक बहुत अधिक उपयोगी इंटरफ़ेस है यदि आपको केवल प्राथमिकता कतार है।

यदि आप सीधे make_heap और इसके भाई बहन का उपयोग करते हैं, तो आपको अंतर्निहित कंटेनर में बदलाव करने के लिए हर बार उनका उपयोग करना सुनिश्चित करना होगा। मैंने उन्हें दो या तीन बार और प्रत्येक बार का उपयोग किया है, जिनका उपयोग गलत तरीके से किया गया था।

मैंने केवल एक बार खुद ही ढेर ऑपरेशन का उपयोग किया है, क्योंकि मुझे थोड़ी देर के लिए प्राथमिकता कतार के रूप में वेक्टर का उपयोग करने की आवश्यकता है और फिर इसे सॉर्ट करें। आपको शायद std::make_heap की आवश्यकता नहीं होगी।

यदि आपको तत्वों को बदलने की क्षमता के साथ प्राथमिकता कतार की आवश्यकता है, तो आप std::set का उपयोग कर सकते हैं। आप क्रमश: *s.begin() या *s.rbegin() के साथ सबसे छोटा या सबसे बड़ा तत्व प्राप्त कर सकते हैं और पुराने मान को हटाकर और नया डालने से तत्व अपडेट कर सकते हैं।