हीप्स और प्रायोरिटी क्यूज़

एक प्रायोरिटी क्यू एक अमूर्त डेटा प्रकार है जो हमेशा उच्चतम (या निम्नतम) प्राथमिकता वाले तत्व को देता है; हीप्स मानक ट्री-आधारित संरचनाएं हैं जो कुशल सम्मिलन और एक्सट्रैक्ट-मिन ऑपरेशंस के साथ इसे लागू करती हैं।

Definition

एक प्रायोरिटी क्यू एक अमूर्त डेटा प्रकार है जो प्राथमिकताओं के साथ तत्वों के सम्मिलन और उच्चतम-प्राथमिकता वाले तत्व के निष्कर्षण का समर्थन करता है; एक हीप एक ट्री-आधारित डेटा संरचना है जो हीप प्रॉपर्टी को संतुष्ट करती है — प्रत्येक नोड की कुंजी उसके बच्चों के सापेक्ष लगातार क्रमबद्ध होती है — जो एक प्रायोरिटी क्यू को कुशलता से लागू करती है।

Scope

यह विषय प्रायोरिटी-क्यू ADT और इसके हीप कार्यान्वयन को शामिल करता है: बाइनरी हीप और इसका ऐरे प्रतिनिधित्व, हीप प्रॉपर्टी और सिफ्ट-अप/सिफ्ट-डाउन ऑपरेशंस, हीपसॉर्ट, और उन्नत मर्ज करने योग्य हीप्स जैसे बाइनोमियल और फिबोनाची हीप्स जो कुंजी-कमी और यूनियन लागतों में सुधार करते हैं। यह ग्राफ एल्गोरिदम (डिज्क्स्ट्रा, प्रिम) और इवेंट-ड्रिवन सिमुलेशन से जुड़ता है, जो प्रायोरिटी क्यूज़ पर निर्भर करते हैं।

Core questions

• प्रायोरिटी-क्यू ADT को कौन से ऑपरेशन परिभाषित करते हैं, और एक हीप उन्हें कैसे लागू करता है?
• हीप प्रॉपर्टी निरंतर समय में फाइंड-मिन और लॉगरिदमिक समय में इंसर्ट/एक्सट्रैक्ट की अनुमति कैसे देती है?
• एक बाइनरी हीप को एक ऐरे में कॉम्पैक्ट रूप से कैसे संग्रहीत किया जाता है, और इसे लीनियर समय में कैसे बनाया जाता है?
• हीपसॉर्ट O(n log n) समय में इन-प्लेस सॉर्ट करने के लिए हीप का उपयोग कैसे करता है?
• जब फिबोनाची हीप्स जैसे मर्ज करने योग्य हीप्स उन एल्गोरिदम में सुधार करते हैं जो अक्सर कुंजियों को कम करते हैं?

Key concepts

• प्रायोरिटी क्यू ADT
• हीप प्रॉपर्टी
• बाइनरी हीप
• ऐरे-आधारित हीप प्रतिनिधित्व
• सिफ्ट-अप और सिफ्ट-डाउन
• लीनियर समय में बिल्ड-हीप
• हीपसॉर्ट
• फिबोनाची और बाइनोमियल हीप्स

Key theories

हीप प्रॉपर्टी और ऐरे प्रतिनिधित्व

एक बाइनरी हीप एक लगभग पूर्ण बाइनरी ट्री है जिसमें प्रत्येक नोड की कुंजी उसके बच्चों पर हावी होती है; इसे निहित पैरेंट-चाइल्ड इंडेक्सिंग के साथ एक ऐरे में संग्रहीत किया जा सकता है, जिससे O(log n) इंसर्ट और एक्सट्रैक्ट और O(1) फाइंड-मिन मिलता है।

फिबोनाची हीप्स की एमोर्टाइज्ड दक्षता

फिबोनाची हीप्स O(1) एमोर्टाइज्ड समय में डिक्रीज-की और O(log n) एमोर्टाइज्ड समय में एक्सट्रैक्ट-मिन का समर्थन करते हैं, जिससे डिज्क्स्ट्रा और प्रिम जैसे एल्गोरिदम के एसिम्प्टोटिक चलने के समय में सुधार होता है जो कई कुंजी कमी करते हैं।

Clinical relevance

प्रायोरिटी क्यूज़ आवश्यक बुनियादी ढाँचा हैं: वे ऑपरेटिंग-सिस्टम शेड्यूलर में तैयार कार्यों को क्रमबद्ध करते हैं, असतत-घटना सिमुलेशन में घटनाओं का प्रबंधन करते हैं, बेस्ट-फर्स्ट और A* खोज को संचालित करते हैं, और डिज्क्स्ट्रा और प्रिम के एल्गोरिदम में सीमा प्रदान करते हैं। हीपसॉर्ट गारंटीकृत सबसे खराब स्थिति की सीमाओं के साथ एक इन-प्लेस O(n log n) सॉर्ट प्रदान करता है।

History

जे. डब्ल्यू. जे. विलियम्स ने 1964 में बाइनरी हीप और हीपसॉर्ट की शुरुआत की, और रॉबर्ट फ्लॉयड ने इसके तुरंत बाद लीनियर-टाइम बिल्ड-हीप प्रक्रिया दी। बाइनोमियल हीप्स (वुइलेमिन, 1978) और फिबोनाची हीप्स (फ्रेडमैन और टार्जन, 1987) ने कुशल मर्जिंग और एमोर्टाइज्ड डिक्रीज-की को जोड़ा, जिससे क्लासिक ग्राफ एल्गोरिदम के चलने के समय में सुधार हुआ।

Key figures

• J. W. J. Williams
• Robert W. Floyd
• Michael Fredman
• Robert Tarjan

Seminal works

• williams1964
• fredman1987
• cormen2009

Frequently asked questions

बाइनरी हीप को पॉइंटर्स के बजाय ऐरे में क्यों संग्रहीत किया जाता है?

एक बाइनरी हीप एक लगभग पूर्ण बाइनरी ट्री है, इसलिए इसके नोड्स लगातार ऐरे इंडेक्स पर स्पष्ट रूप से मैप होते हैं: इंडेक्स i पर एक नोड के बच्चे 2i और 2i+1 पर होते हैं। यह पॉइंटर ओवरहेड से बचाता है, कैश व्यवहार में सुधार करता है, और नेविगेशन को सरल अंकगणित बनाता है।

फिबोनाची हीप्स अपनी जटिलता के लायक कब होते हैं?

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