Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> प्रोग्रामिंग

डेटा संरचना में डिएप्स (Deaps): परिभाषा और गुण


डिएप (Deap) परिभाषा

एक **डिएप** (डबल-एंडेड हीप) एक विशेष बाइनरी ट्री-आधारित डेटा संरचना है जिसमें निम्नलिखित गुण होते हैं:

  1. खाली रूट: रूट नोड (इंडेक्स 1) में कोई तत्व/की मान नहीं होता; यह खाली होता है।
  2. लेफ्ट सबट्री = मिन-हीप: रूट का लेफ्ट सबट्री एक मानक मिन-हीप होता है।
  3. राइट सबट्री = मैक्स-हीप: रूट का राइट सबट्री एक मानक मैक्स-हीप होता है।

कॉरेस्पॉन्डेंस गुण

यदि लेफ्ट और राइट सबट्री के विशिष्ट नोड्स नॉन-खाली हैं, और उनके कॉरेस्पॉन्डिंग नोड्स a (मिन-हीप में) और b (मैक्स-हीप में) हैं, तो:

a.KeyValue ≤ b.KeyValue

डेटा संरचना में डिएप्स (Deaps): परिभाषा और गुण

निहितार्थ

  • मिन-हीप में प्रत्येक तत्व अपने कॉरेस्पॉन्डिंग मैक्स-हीप तत्व से कम या बराबर होता है।
  • यह डुअल-हीप कॉरेस्पॉन्डेंस विधि का एक कुशल सरणी-आधारित कार्यान्वयन है।
  • न्यूनतम तत्व इंडेक्स 2 पर (लेफ्ट सबट्री रूट)।
  • अधिकतम तत्व राइट सबट्री रूट पर (इंडेक्स पावर-ऑफ-टू ऑफसेट द्वारा गणना)।

संचालन सारांश

लाभ

  • सरणी में कॉम्पैक्ट स्टोरेज (कोई पॉइंटर ओवरहेड नहीं)।
  • मानक हीप ऑपरेशन्स का सीधा अनुकूलन।
  • कॉरेस्पॉन्डेंस पॉइंटर्स के बजाय अंकगणितीय इंडेक्स गणना का उपयोग करता है।
  1. डेटा संरचना में B+ ट्री क्वेरी (B+ tree Query) डेटा संरचना में B+ ट्री क्वेरी (B+ tree Query)

    यहाँ हम देखेंगे कि B+ ट्री में खोज कैसे की जाती है। B+ ट्री खोज को B+ ट्री क्वेरीिंग (B+ Tree Querying) के रूप में भी जाना जाता है। यह एल्गोरिदम B-ट्री की क्वेरी करने के समान है। इसके अलावा, यह रेंज क्वेरी (range query) का समर्थन करता है। मान लीजिए हमारे पास नीचे जैसा B+ ट्री है: B+ ट्री का उदाहरण

  1. डेटा संरचना में B+ ट्री (The B+ tree) डेटा संरचना में B+ ट्री (The B+ tree)

    यहाँ हम देखेंगे कि B+ ट्री (B+ Trees) क्या हैं। B+ ट्री B-ट्री का विस्तारित संस्करण हैं। यह ट्री B-ट्री की तुलना में बेहतर सम्मिलन, विलोपन और खोज का समर्थन करता है। B-ट्री में, कुंजियाँ और रिकॉर्ड मान आंतरिक और साथ ही पत्ती नोड्स में संग्रहीत होते हैं। B+ ट्री में रिकॉर्ड्स, पत्ती नोड पर संग्रहीत

  1. हाफएज डेटा स्ट्रक्चर (Halfedge Data Structure) हाफएज डेटा स्ट्रक्चर (Halfedge Data Structure)

    परिचय (Introduction) टेम्पलेट पैरामीटर्स के लिए HDS या हाफएज डेटा स्ट्रक्चर (Halfedge Data Structure - संक्षिप्त HalfedgeDS) को एक एज-केंद्रित डेटा स्ट्रक्चर (Edge-centered Data Structure) के रूप में परिभाषित किया जाता है जो वर्टेक्स, एज और फेसेस (Vertices, Edges and Faces) की घटना जानकारी (Incidenc

© कॉपीराइट https://in.wsxdn.com सर्वाधिकार सुरक्षित
ऑपरेशनजटिलता
`getMin()` / `getMax()`O(1)
`insert(x)`O(log n)
`removeMin()` / `removeMax()`O(log n)