के-डी हीप: Difference between revisions
From Vigyanwiki
No edit summary |
|||
| Line 1: | Line 1: | ||
[[File:K-d heap 2 keys.png|thumb|20 तत्वों वाला 2-डी | [[File:K-d heap 2 keys.png|thumb|20 तत्वों वाला 2-डी हीप।]]एक '''के-डी हीप'''<ref>Ding Y., Weiss M.A. (1993) The ''K''-D heap: An efficient multi-dimensional priority queue. In: Dehne F., Sack JR., Santoro N., Whitesides S. (eds) Algorithms and Data Structures. WADS 1993. Lecture Notes in Computer Science, vol 709. Springer, Berlin, Heidelberg</ref> [[Index.php?title=अभिकलित्र विज्ञान|अभिकलित्र विज्ञान]] में एक [[डेटा संरचना|आँकड़ा संरचना]] है जो अतिरिक्त स्थान की आवश्यकता के बिना बहुआयामी [[प्राथमिकता कतार]] को लागू करती है। यह हीप (आँकड़ा संरचना) का सामान्यीकरण है।<ref>Advanced Data Structures, Peter Brass, {{ISBN|978-0-521-88037-4}}, page 270</ref> यह किसी भी k आयाम में कुशल सम्मिलन, न्यूनतम तत्व की क्वेरी और न्यूनतम तत्व को हटाने की अनुमति देता है, और इसलिए इसमें एक विशेष मामले के रूप में डबल-एंडेड हीप शामिल है। | ||
==संरचना== | ==संरचना== | ||
n वस्तुओं का एक संग्रह दिया गया है, जहां प्रत्येक के पास है <math>k</math> कुंजियाँ (या प्राथमिकताएँ), के-डी हीप उन्हें एक [[ | n वस्तुओं का एक संग्रह दिया गया है, जहां प्रत्येक के पास है <math>k</math> कुंजियाँ (या प्राथमिकताएँ), के-डी हीप उन्हें एक [[Index.php?title=बाइनरी ट्री|बाइनरी ट्री]] में व्यवस्थित करता है जो दो शर्तों को पूरा करता है: | ||
* यह एक पूर्ण बाइनरी ट्री है, जिसका अर्थ है कि यह संभवतः अंतिम परत को छोड़कर भरा हुआ है, जहां इसे बाईं ओर से भरा जाना चाहिए। | * यह एक पूर्ण बाइनरी ट्री है, जिसका अर्थ है कि यह संभवतः अंतिम परत को छोड़कर भरा हुआ है, जहां इसे बाईं ओर से भरा जाना चाहिए। | ||
* यह के-डी हीप ऑर्डर को संतुष्ट करता है। | * यह के-डी हीप ऑर्डर को संतुष्ट करता है। | ||
के-डी हीप ऑर्डर की | के-डी हीप ऑर्डर की गुण नियमित हीप के लिए [[Index.php?title=हीप गुण|हीप गुण]] के अनुरूप है। एक हीप k-d हीप क्रम बनाए रखता है यदि: | ||
* | * रूट में नोड में पूरे ट्री की सबसे छोटी पहली गुण होती है, और | ||
* प्रत्येक अन्य नोड v जो रूट नहीं है, ऐसा है कि यदि उसके | * प्रत्येक अन्य नोड v जो रूट नहीं है, ऐसा है कि यदि उसके मूल w में मूल द्वारा रूट किए गए सब ट्री की सबसे छोटी i-th गुण है, तो v में सबसे छोटा है <math>(i \mod k) +1</math>v द्वारा निहित संपूर्ण सब ट्री की -''v'' गुण है। | ||
इस संरचना का एक परिणाम यह है कि सबसे छोटा पहला | इस संरचना का एक परिणाम यह है कि सबसे छोटा पहला गुण-तत्व रूट में होगा, और इसके अलावा प्रत्येक i के लिए सभी सबसे छोटे i-वें गुण तत्व पहले k स्तरों में होंगे। | ||
==संचालन== | ==संचालन== | ||
n वस्तुओं से | n वस्तुओं से के-डी हीप बनाने में O(n) समय लगता है। निम्नलिखित संक्रिया समर्थित हैं: | ||
* समय O(लॉग एन) में एक नया आइटम डालें | * समय O(लॉग एन) में एक नया आइटम डालें | ||
* निरंतर समय में किसी भी आयाम में न्यूनतम कुंजी के साथ आइटम पुनर्प्राप्त करें | * निरंतर समय में किसी भी आयाम में न्यूनतम कुंजी के साथ आइटम पुनर्प्राप्त करें | ||
* समय O(लॉग एन) में किसी भी आयाम में न्यूनतम कुंजी के साथ एक आइटम हटाएं | * समय O(लॉग एन) में किसी भी आयाम में न्यूनतम कुंजी के साथ एक आइटम हटाएं | ||
* | * हीप में किसी यादृच्छिक आइटम को समय O(लॉग एन) में हटाएं या संशोधित करें, यह मानते हुए कि हीप में उसकी स्थिति ज्ञात है | ||
महत्वपूर्ण बात यह है कि इन परिचालनों में छिपा हुआ स्थिरांक तेजी से बड़ा सापेक्ष है <math>k</math>, आयामों की संख्या, इसलिए के-डी हीप्स बहुत अधिक आयामों वाले अनुप्रयोगों के लिए व्यावहारिक नहीं हैं। | महत्वपूर्ण बात यह है कि इन परिचालनों में छिपा हुआ स्थिरांक तेजी से बड़ा सापेक्ष है <math>k</math>, आयामों की संख्या, इसलिए के-डी हीप्स बहुत अधिक आयामों वाले अनुप्रयोगों के लिए व्यावहारिक नहीं हैं। | ||
Revision as of 16:33, 22 July 2023
एक के-डी हीप[1] अभिकलित्र विज्ञान में एक आँकड़ा संरचना है जो अतिरिक्त स्थान की आवश्यकता के बिना बहुआयामी प्राथमिकता कतार को लागू करती है। यह हीप (आँकड़ा संरचना) का सामान्यीकरण है।[2] यह किसी भी k आयाम में कुशल सम्मिलन, न्यूनतम तत्व की क्वेरी और न्यूनतम तत्व को हटाने की अनुमति देता है, और इसलिए इसमें एक विशेष मामले के रूप में डबल-एंडेड हीप शामिल है।
संरचना
n वस्तुओं का एक संग्रह दिया गया है, जहां प्रत्येक के पास है कुंजियाँ (या प्राथमिकताएँ), के-डी हीप उन्हें एक बाइनरी ट्री में व्यवस्थित करता है जो दो शर्तों को पूरा करता है:
- यह एक पूर्ण बाइनरी ट्री है, जिसका अर्थ है कि यह संभवतः अंतिम परत को छोड़कर भरा हुआ है, जहां इसे बाईं ओर से भरा जाना चाहिए।
- यह के-डी हीप ऑर्डर को संतुष्ट करता है।
के-डी हीप ऑर्डर की गुण नियमित हीप के लिए हीप गुण के अनुरूप है। एक हीप k-d हीप क्रम बनाए रखता है यदि:
- रूट में नोड में पूरे ट्री की सबसे छोटी पहली गुण होती है, और
- प्रत्येक अन्य नोड v जो रूट नहीं है, ऐसा है कि यदि उसके मूल w में मूल द्वारा रूट किए गए सब ट्री की सबसे छोटी i-th गुण है, तो v में सबसे छोटा है v द्वारा निहित संपूर्ण सब ट्री की -v गुण है।
इस संरचना का एक परिणाम यह है कि सबसे छोटा पहला गुण-तत्व रूट में होगा, और इसके अलावा प्रत्येक i के लिए सभी सबसे छोटे i-वें गुण तत्व पहले k स्तरों में होंगे।
संचालन
n वस्तुओं से के-डी हीप बनाने में O(n) समय लगता है। निम्नलिखित संक्रिया समर्थित हैं:
- समय O(लॉग एन) में एक नया आइटम डालें
- निरंतर समय में किसी भी आयाम में न्यूनतम कुंजी के साथ आइटम पुनर्प्राप्त करें
- समय O(लॉग एन) में किसी भी आयाम में न्यूनतम कुंजी के साथ एक आइटम हटाएं
- हीप में किसी यादृच्छिक आइटम को समय O(लॉग एन) में हटाएं या संशोधित करें, यह मानते हुए कि हीप में उसकी स्थिति ज्ञात है
महत्वपूर्ण बात यह है कि इन परिचालनों में छिपा हुआ स्थिरांक तेजी से बड़ा सापेक्ष है , आयामों की संख्या, इसलिए के-डी हीप्स बहुत अधिक आयामों वाले अनुप्रयोगों के लिए व्यावहारिक नहीं हैं।
संदर्भ
- ↑ Ding Y., Weiss M.A. (1993) The K-D heap: An efficient multi-dimensional priority queue. In: Dehne F., Sack JR., Santoro N., Whitesides S. (eds) Algorithms and Data Structures. WADS 1993. Lecture Notes in Computer Science, vol 709. Springer, Berlin, Heidelberg
- ↑ Advanced Data Structures, Peter Brass, ISBN 978-0-521-88037-4, page 270
