क्या किसी सरणी से पूर्णांक की पूर्ण x मात्रा प्राप्त करने के लिए बाइनरी ढेर का उपयोग करना तेज होगा या त्वरित प्रकार का उपयोग करें - c ++, quicksort, बाइनरी-ढेर

किसी सरणी से पूर्णांक की उच्चतम X राशि प्राप्त करने के लिए, क्या आप लोग सोचते हैं कि इस तरह से बाइनरी हीप का उपयोग करना जल्दी होगा:

• उच्चतम पूर्णांक प्राप्त करने के लिए बाइनरी हीप
• उच्चतम पूर्णांक स्टोर करें
• सरणी से उच्चतम पूर्णांक निकालें
• दोहराएँ जब तक हम सरणी से उच्चतम एक्स राशि है

या यह केवल त्वरित सॉर्ट का उपयोग करने और सरणी से पूर्णांक की शीर्ष x राशि लेने के लिए तेज़ होगा?

संपादित करें: मुझे यह भी जोड़ना चाहिए कि सरणी को "हल किया जा सकता है क्योंकि इसमें कई चर हैं जिन्हें हम क्रमबद्ध करना चाहते हैं, जैसे:

class cl{
int var;
int var1;
int var2;
};
cl clArr[];

इसलिए, हम किसी भी चर से उच्चतम पूर्णांक प्राप्त करने का अनुरोध कर सकते हैं।

इसे लिखते हुए, ऐसा लगता है कि एक त्वरित प्रकार एक बेहतर विचार हो सकता है, हालांकि मुझे कुछ राय पसंद है, ज्यादातर क्या सबसे तेज़ विकल्प होगा।

धन्यवाद

उत्तर:

आपको इन दोनों समाधानों को लागू करने और वास्तविक डेटा के साथ कुछ रूपरेखा करने की आवश्यकता है ताकि यह पता लगाया जा सके कि कौन सा तेज है।

आइए इन दोनों मामलों के लिए एक उदाहरण लें: -

विधि 1 (अधिकतम हीप का उपयोग करें): -

1) Build a Max Heap tree in O(n)
2) Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)

Time complexity: O(n + klogn)

विधि 2 (त्वरित सॉर्ट का उपयोग करें): -

1) Sort the elements in descending order in O(nLogn)
2) Print the first k numbers of the sorted array O(k).

Time complexity: O(nlogn)