के-डी हीप: Difference between revisions

From Vigyanwiki
(Created page with "thumb|20 तत्वों वाला 2-डी ढेर।एक के-डी ढेर<ref>Ding Y., Weiss M.A. (1993) The ''K''-D heap: An e...")
 
No edit summary
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[[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> [[कंप्यूटर विज्ञान]] में एक [[डेटा संरचना]] है जो अतिरिक्त स्थान की आवश्यकता के बिना बहुआयामी [[प्राथमिकता कतार]] को लागू करती है। यह हीप (डेटा संरचना) का सामान्यीकरण है।<ref>Advanced Data Structures, Peter Brass, {{ISBN|978-0-521-88037-4}}, page 270</ref> यह किसी भी k आयाम में कुशल सम्मिलन, न्यूनतम तत्व की क्वेरी और न्यूनतम तत्व को हटाने की अनुमति देता है, और इसलिए इसमें एक विशेष मामले के रूप में [[डबल-एंडेड प्राथमिकता कतार]] | डबल-एंडेड हीप शामिल है।
[[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=बाइनरी ट्री|बाइनरी ट्री]] में व्यवस्थित करता है जो दो शर्तों को पूरा करता है:


* यह एक पूर्ण बाइनरी ट्री है, जिसका अर्थ है कि यह संभवतः अंतिम परत को छोड़कर भरा हुआ है, जहां इसे बाईं ओर से भरा जाना चाहिए।
* यह एक पूर्ण बाइनरी ट्री है, जिसका अर्थ है कि यह संभवतः अंतिम परत को छोड़कर भरा हुआ है, जहां इसे बाईं ओर से भरा जाना चाहिए।
* यह के-डी हीप ऑर्डर को संतुष्ट करता है।
* यह के-डी हीप ऑर्डर को संतुष्ट करता है।


के-डी हीप ऑर्डर की संपत्ति नियमित ढेर के लिए [[ढेर संपत्ति]] के अनुरूप है। एक ढेर k-d ढेर क्रम बनाए रखता है यदि:
के-डी हीप ऑर्डर की गुण नियमित हीप के लिए [[Index.php?title=हीप गुण|हीप गुण]] के अनुरूप है। एक हीप k-d हीप क्रम बनाए रखता है यदि:


* जड़ में नोड में पूरे पेड़ की सबसे छोटी पहली संपत्ति होती है, और
* रूट में नोड में पूरे ट्री की सबसे छोटी पहली गुण होती है, और
* प्रत्येक अन्य नोड v जो रूट नहीं है, ऐसा है कि यदि उसके पैरेंट w में पैरेंट द्वारा रूट किए गए सबट्री की सबसे छोटी i-th संपत्ति है, तो v में सबसे छोटा है <math>(i \mod k) +1</math>v द्वारा निहित संपूर्ण उपवृक्ष की -वीं संपत्ति।
* प्रत्येक अन्य नोड v जो रूट नहीं है, ऐसा है कि यदि उसके मूल w में मूल द्वारा रूट किए गए सब ट्री की सबसे छोटी i-th गुण है, तो v में सबसे छोटा है <math>(i \mod k) +1</math>v द्वारा निहित संपूर्ण सब ट्री की -''v'' गुण है।


इस संरचना का एक परिणाम यह है कि सबसे छोटा पहला संपत्ति-तत्व जड़ में होगा, और इसके अलावा प्रत्येक i के लिए सभी सबसे छोटे i-वें संपत्ति तत्व पहले k स्तरों में होंगे।
इस संरचना का एक परिणाम यह है कि सबसे छोटा पहला गुण-तत्व रूट में होगा, और इसके अतिरिक्त प्रत्येक i के लिए सभी सबसे छोटे i-वें गुण तत्व पहले k स्तरों में होंगे।


==संचालन==
==संचालन==
n वस्तुओं से K-D ढेर बनाने में O(n) समय लगता है। निम्नलिखित ऑपरेशन समर्थित हैं:
n वस्तुओं से के-डी हीप बनाने में O(n) समय लगता है। निम्नलिखित संक्रिया समर्थित हैं:


* समय O(लॉग एन) में एक नया आइटम डालें
* समय O(लॉग एन) में एक नया आइटम डालें
* निरंतर समय में किसी भी आयाम में न्यूनतम कुंजी के साथ आइटम पुनर्प्राप्त करें
* निरंतर समय में किसी भी आयाम में न्यूनतम कुंजी के साथ आइटम पुनर्प्राप्त करें
* समय O(लॉग एन) में किसी भी आयाम में न्यूनतम कुंजी के साथ एक आइटम हटाएं
* समय O(लॉग एन) में किसी भी आयाम में न्यूनतम कुंजी के साथ एक आइटम हटाएं
* ढेर में किसी मनमाने आइटम को समय O(लॉग एन) में हटाएं या संशोधित करें, यह मानते हुए कि ढेर में उसकी स्थिति ज्ञात है
* हीप में किसी यादृच्छिक आइटम को समय O(लॉग एन) में हटाएं या संशोधित करें, यह मानते हुए कि हीप में उसकी स्थिति ज्ञात है


महत्वपूर्ण बात यह है कि इन परिचालनों में छिपा हुआ स्थिरांक तेजी से बड़ा सापेक्ष है <math>k</math>, आयामों की संख्या, इसलिए के-डी हीप्स बहुत अधिक आयामों वाले अनुप्रयोगों के लिए व्यावहारिक नहीं हैं।
महत्वपूर्ण बात यह है कि इन परिचालनों में छिपा हुआ स्थिरांक तेजी से बड़ा सापेक्ष है <math>k</math>, आयामों की संख्या, इसलिए के-डी हीप्स बहुत अधिक आयामों वाले अनुप्रयोगों के लिए व्यावहारिक नहीं हैं।
Line 27: Line 27:
== संदर्भ ==
== संदर्भ ==
{{Reflist}}
{{Reflist}}
[[Category: ढेर (डेटा संरचनाएं)]]


[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:ढेर (डेटा संरचनाएं)]]

Latest revision as of 10:38, 27 July 2023

20 तत्वों वाला 2-डी हीप।

एक के-डी हीप[1] अभिकलित्र विज्ञान में एक आँकड़ा संरचना है जो अतिरिक्त स्थान की आवश्यकता के बिना बहुआयामी प्राथमिकता कतार को लागू करती है। यह हीप (आँकड़ा संरचना) का सामान्यीकरण है।[2] यह किसी भी k आयाम में कुशल सम्मिलन, न्यूनतम तत्व की क्वेरी और न्यूनतम तत्व को हटाने की अनुमति देता है, और इसलिए इसमें एक विशेष स्थितिे के रूप में डबल-एंडेड हीप सम्मलित है।

संरचना

n वस्तुओं का एक संग्रह दिया गया है, जहां प्रत्येक के पास है कुंजियाँ (या प्राथमिकताएँ), के-डी हीप उन्हें एक बाइनरी ट्री में व्यवस्थित करता है जो दो शर्तों को पूरा करता है:

  • यह एक पूर्ण बाइनरी ट्री है, जिसका अर्थ है कि यह संभवतः अंतिम परत को छोड़कर भरा हुआ है, जहां इसे बाईं ओर से भरा जाना चाहिए।
  • यह के-डी हीप ऑर्डर को संतुष्ट करता है।

के-डी हीप ऑर्डर की गुण नियमित हीप के लिए हीप गुण के अनुरूप है। एक हीप k-d हीप क्रम बनाए रखता है यदि:

  • रूट में नोड में पूरे ट्री की सबसे छोटी पहली गुण होती है, और
  • प्रत्येक अन्य नोड v जो रूट नहीं है, ऐसा है कि यदि उसके मूल w में मूल द्वारा रूट किए गए सब ट्री की सबसे छोटी i-th गुण है, तो v में सबसे छोटा है v द्वारा निहित संपूर्ण सब ट्री की -v गुण है।

इस संरचना का एक परिणाम यह है कि सबसे छोटा पहला गुण-तत्व रूट में होगा, और इसके अतिरिक्त प्रत्येक i के लिए सभी सबसे छोटे i-वें गुण तत्व पहले k स्तरों में होंगे।

संचालन

n वस्तुओं से के-डी हीप बनाने में O(n) समय लगता है। निम्नलिखित संक्रिया समर्थित हैं:

  • समय O(लॉग एन) में एक नया आइटम डालें
  • निरंतर समय में किसी भी आयाम में न्यूनतम कुंजी के साथ आइटम पुनर्प्राप्त करें
  • समय O(लॉग एन) में किसी भी आयाम में न्यूनतम कुंजी के साथ एक आइटम हटाएं
  • हीप में किसी यादृच्छिक आइटम को समय O(लॉग एन) में हटाएं या संशोधित करें, यह मानते हुए कि हीप में उसकी स्थिति ज्ञात है

महत्वपूर्ण बात यह है कि इन परिचालनों में छिपा हुआ स्थिरांक तेजी से बड़ा सापेक्ष है , आयामों की संख्या, इसलिए के-डी हीप्स बहुत अधिक आयामों वाले अनुप्रयोगों के लिए व्यावहारिक नहीं हैं।

संदर्भ

  1. ↑ 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
  2. ↑ Advanced Data Structures, Peter Brass, ISBN 978-0-521-88037-4, page 270
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=के-डी_हीप&oldid=226930’