के-डी हीप

20 तत्वों वाला 2-डी ढेर।

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

संरचना

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

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

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

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

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

संचालन

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

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

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