एसएलएल के साथ एक न्यूनतम ढेर बनाए रखने के लिए आसान तरीका? उपयोगकर्ता परिभाषित संरचना के लिए

Question

, जैसा कि मैं समझता हूं, यह आसान है। बस ऑपरेटर < अधिभारित करें। हालांकि, int/float आदि के लिए .., क्या मुझे वास्तव में int के लिए ऑपरेटर < अधिभारित करने की आवश्यकता है?

 #include <iostream> 
     #include <algorithm> 
     #include <vector> 
     using namespace std; 

     bool comp(const int& a, const int& b) 
     { 
      return a<b?false:true; 
     } 

     int main() 
     { 
     int myints[] = {10,20,30,5,15}; 
     vector<int> v(myints,myints+5); 
     vector<int>::iterator it; 
     make_heap(v.begin(), v.end(), comp); 
     cout << "initial min heap : " << v.front() << endl; 
     for (unsigned i=0; i<v.size(); i++) cout << " " << v[i]; 
     cout<<endl; 

     pop_heap (v.begin(),v.end()); 
     v.pop_back(); 
     for (unsigned i=0; i<v.size(); i++) cout << " " << v[i]; 
     cout<<endl; 
     } 

परिणाम हैं::

 initial min heap : 5 
     5 10 30 20 15 
     30 10 15 20 

अब pop_heap, push_heap सही ढंग से न्यूनतम-ढेर बनाए रखने नहीं होगा यहाँ मैं क्या करने की कोशिश की है? क्या यह हासिल करने का कोई आसान तरीका है? धन्यवाद!

संपादित करें: क्षमा करें, मैंने मैन्युअल रूप से मैन्युअल रूप से जांच नहीं की है। हां, pop_heap या push_heap को comp पास करने से चाल चलनी चाहिए। हालांकि, आपका क्या मतलब है, मुझे बाहरी तुलनित्र का उपयोग नहीं करना चाहिए? यदि यह सही तरीका नहीं है, तो इसे प्राप्त करने का आम तरीका क्या है?

Answer 1

आपको int (आप वास्तव में नहीं कर सकते) के लिए अधिभार लोड करने की आवश्यकता नहीं है। यदि आप बाहरी तुलनित्र का उपयोग करते हैं, तो आपको उसी Comparator comp से pop_head पर भी गुजरना चाहिए।

* संपादित करें: *

रूप ildjarn ने कहा, अपनी तुलना ऑपरेटर एक सख्त-कमजोर आदेश संबंध को लागू नहीं करता है।

a < b ? false : true; --> a >= b 
b < a ? true : false; --> a > b 

Answer 2

उपयोग std::greater<int>() तुलनित्र (make_heap, push_heap, pop_heap सभी के लिए) के रूप में। () महत्वपूर्ण हैं - std::greater<int> एक फ़ैक्टर क्लास फ़ंक्शन नहीं है, इसलिए आपको इसका एक उदाहरण चाहिए।

Answer 3

उत्तर अच्छे हैं, इसलिए मैं बस एक छोटा सा उदाहरण जोड़ना चाहता था।

array<int, 10> A{5,2,8,3,4,1,9,12,0,7}; 

और आप एक min heap बनाना चाहते हैं: आप निम्नलिखित सरणी है कहो। ऐसा करने का सबसे तेज़ तरीका make_heap एल्गोरिदम का उपयोग करना है। हालांकि, यह डिफ़ॉल्ट रूप से max heap बनाता है। दूसरे शब्दों में, अगर आप कहते हैं:

make_heap(A.begin(), A.end()); 

A एक max heap हो जाता है। दूसरी ओर, min heap रखने के लिए, आपको एक तुलनित्र जोड़ने की आवश्यकता है लेकिन उसे लागू करने की आवश्यकता नहीं है। इस प्रकार के बजाय विधि कॉल:

make_heap(A.begin(), A.end(), greater<int>()); 

यह कॉल आपके सरणी एक min heap कर देगा।

पीएस: #include <algorithm>std::make_heap का उपयोग करने के लिए आवश्यक है। समान ऑपरेशन vector पर भी लागू होते हैं।

एचटीएच!