बीप: Difference between revisions
(Created page with "{{short description|Data structure}} एक बीप, या द्वि-अभिभावक हीप (डेटा संरचना), एक डेटा संर...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Data structure}} | {{short description|Data structure}} | ||
एक बीप, या द्वि-अभिभावक हीप ([[डेटा संरचना]]), एक डेटा संरचना है जहां एक नोड में | एक बीप, या द्वि-अभिभावक हीप ([[डेटा संरचना]]), एक डेटा संरचना है जहां एक नोड में सामान्यतः दो माता-पिता होते हैं (जब तक कि यह एक स्तर पर पहला या अंतिम न हो) और दो बच्चे (जब तक कि यह अंतिम स्तर पर न हो) संग्रह के विपरीत, एक बीप सबलाइनियर या कंप्यूटर विज्ञान परिभाषा खोज की अनुमति देता है। बीप को [[इयान मुनरो (कंप्यूटर वैज्ञानिक)]] और [[हेंड्रा सुवांडा]] द्वारा प्रस्तुत किया गया था। एक संबंधित डेटा संरचना यंग दृश्य है। | ||
[[Image:beap.jpg|frame|बीप]] | [[Image:beap.jpg|frame|बीप]] | ||
| Line 6: | Line 6: | ||
==प्रदर्शन== | ==प्रदर्शन== | ||
संरचना की ऊंचाई लगभग | संरचना की ऊंचाई लगभग <math>\sqrt{n}</math> है। साथ ही, यह मानते हुए कि अंतिम स्तर पूर्ण है, उस स्तर पर अवयव की संख्या भी <math>\sqrt{n}</math> है। वास्तव में, इन गुणों के कारण सभी मूलभूत ऑपरेशन (सम्मिलित करें, हटाएं, खोजे ) औसतन <math>O(\sqrt{n})</math> समय में चलते हैं। सबसे व्यर्थ स्थिति में संग्रह में संचालन <math>O(n)</math> हो सकता है। नए अवयव को हटाने और सम्मिलित करने में बीप अपरिवर्तनीय को पुनर्स्थापित करने के लिए अवयव को ऊपर या नीचे (संग्रह की तरह) फैलाना सम्मिलित है। एक अतिरिक्त लाभ यह है कि बीप सबसे छोटे अवयव तक निरंतर समय पहुंच और अधिकतम अवयव के लिए <math>O(\sqrt{n})</math> समय प्रदान करता है। | ||
इसलिए, यदि प्रत्येक नोड पर पैरेंट पॉइंटर्स बनाए रखा जाता है तो एक <math>O(\sqrt{n}) | |||
</math> फाइंड ऑपरेशन प्रयुक्त किया जा सकता है। आप शीर्ष नोड के सबसे निचले तत्व से प्रारंभ करेंगे (संग्रह में सबसे बाईं ओर के बच्चे के समान) और रुचि के तत्व को खोजने के लिए या तो ऊपर या दाएं जाएंगे। | |||
==संदर्भ== | ==संदर्भ == | ||
* {{cite journal | last1 = Munro | first1 = J. Ian | last2 = Suwanda | first2 = Hendra | year = 1980 | title = Implicit data structures for fast search and update | journal = [[Journal of Computer and System Sciences]] | volume = 21 | issue = 2| pages = 236–250 | doi=10.1016/0022-0000(80)90037-9| doi-access = free }} | * {{cite journal | last1 = Munro | first1 = J. Ian | last2 = Suwanda | first2 = Hendra | year = 1980 | title = Implicit data structures for fast search and update | journal = [[Journal of Computer and System Sciences]] | volume = 21 | issue = 2| pages = 236–250 | doi=10.1016/0022-0000(80)90037-9| doi-access = free }} | ||
Revision as of 11:16, 24 July 2023
एक बीप, या द्वि-अभिभावक हीप (डेटा संरचना), एक डेटा संरचना है जहां एक नोड में सामान्यतः दो माता-पिता होते हैं (जब तक कि यह एक स्तर पर पहला या अंतिम न हो) और दो बच्चे (जब तक कि यह अंतिम स्तर पर न हो) संग्रह के विपरीत, एक बीप सबलाइनियर या कंप्यूटर विज्ञान परिभाषा खोज की अनुमति देता है। बीप को इयान मुनरो (कंप्यूटर वैज्ञानिक) और हेंड्रा सुवांडा द्वारा प्रस्तुत किया गया था। एक संबंधित डेटा संरचना यंग दृश्य है।
प्रदर्शन
संरचना की ऊंचाई लगभग है। साथ ही, यह मानते हुए कि अंतिम स्तर पूर्ण है, उस स्तर पर अवयव की संख्या भी है। वास्तव में, इन गुणों के कारण सभी मूलभूत ऑपरेशन (सम्मिलित करें, हटाएं, खोजे ) औसतन समय में चलते हैं। सबसे व्यर्थ स्थिति में संग्रह में संचालन हो सकता है। नए अवयव को हटाने और सम्मिलित करने में बीप अपरिवर्तनीय को पुनर्स्थापित करने के लिए अवयव को ऊपर या नीचे (संग्रह की तरह) फैलाना सम्मिलित है। एक अतिरिक्त लाभ यह है कि बीप सबसे छोटे अवयव तक निरंतर समय पहुंच और अधिकतम अवयव के लिए समय प्रदान करता है।
इसलिए, यदि प्रत्येक नोड पर पैरेंट पॉइंटर्स बनाए रखा जाता है तो एक फाइंड ऑपरेशन प्रयुक्त किया जा सकता है। आप शीर्ष नोड के सबसे निचले तत्व से प्रारंभ करेंगे (संग्रह में सबसे बाईं ओर के बच्चे के समान) और रुचि के तत्व को खोजने के लिए या तो ऊपर या दाएं जाएंगे।
संदर्भ
- Munro, J. Ian; Suwanda, Hendra (1980). "Implicit data structures for fast search and update". Journal of Computer and System Sciences. 21 (2): 236–250. doi:10.1016/0022-0000(80)90037-9.
- Williams, J. W. J. (Jun 1964). "Algorithm 232 - Heapsort". Communications of the ACM. 7 (6): 347–348. doi:10.1145/512274.512284.
