हीप डेटा संरचना: हीप क्या है? न्यूनतम और अधिकतम हीप (उदाहरण)

ढेर क्या है?

हीप एक विशेष वृक्ष डेटा संरचना है। हीप में सबसे ऊपर का नोड शामिल होता है जिसे रूट (पैरेंट) कहा जाता है। इसका दूसरा बच्चा रूट का बायाँ बच्चा होता है, जबकि तीसरा नोड रूट का दायाँ बच्चा होता है। क्रमिक नोड्स बाएँ से दाएँ भरे जाते हैं। पैरेंट-नोड कुंजी की तुलना उसके संतान से की जाती है, और एक उचित व्यवस्था होती है। पेड़ को देखना आसान है जहाँ प्रत्येक इकाई को नोड कहा जाता है। नोड में पहचान के लिए अद्वितीय कुंजियाँ होती हैं।

आपको हीप डेटा संरचना की आवश्यकता क्यों है?

हीप डेटा संरचना का उपयोग करने के मुख्य कारण यहां दिए गए हैं:

हीप डेटा संरचना लॉगरिदमिक समय में विलोपन और सम्मिलन की अनुमति देती है – O(log₂एन)।
वृक्ष में डेटा एक विशेष क्रम में बना होता है। अधिकतम या न्यूनतम जैसी चीज़ों को अपडेट करने या क्वेरी करने के अलावा, प्रोग्रामर पैरेंट और संतान के बीच संबंध भी ढूँढ सकता है।
आप इस अवधारणा को लागू कर सकते हैं दस्तावेज़ ऑब्जेक्ट मॉडल हीप डेटा संरचना को समझने में आपकी सहायता करने के लिए.

ढेर के प्रकार

हीप डेटा संरचना में तत्वों को सम्मिलित करने और हटाने के लिए विभिन्न एल्गोरिदम हैं, जिनमें प्राथमिकता-कतार, बाइनरी-हीप, द्विपद हीप और शामिल हैं। ढेर बनाएं और छांटें.

प्राथमिकता कतार: यह एक अमूर्त डेटा संरचना है जिसमें प्राथमिकता वाले ऑब्जेक्ट होते हैं। प्रत्येक ऑब्जेक्ट या आइटम के लिए पहले से ही एक प्राथमिकता तय होती है। इसलिए, जिस ऑब्जेक्ट या आइटम को उच्च प्राथमिकता दी जाती है, उसे बाकी सभी से पहले सेवा मिल जाती है।
बाइनरी-हीप: बाइनरी हीप सरल हीप संचालन जैसे विलोपन और सम्मिलन के लिए उपयुक्त हैं।
द्विपद-ढेर: द्विपद ढेर में द्विपद वृक्षों के संग्रह की एक श्रृंखला होती है जो ढेर बनाते हैं। द्विपद ढेर वृक्ष कोई साधारण वृक्ष नहीं है क्योंकि इसे कड़ाई से परिभाषित किया गया है। द्विपद वृक्ष में तत्वों की कुल संख्या हमेशा 2 होती हैⁿ नोड्स।
ढेर बनाएं और छांटें: अधिकांश सॉर्टिंग एल्गोरिदम के विपरीत, हीप-सॉर्ट अपने सॉर्ट ऑपरेशन के लिए O(1) स्पेस का उपयोग करता है। यह एक तुलना-आधारित सॉर्टिंग एल्गोरिदम है जहाँ सॉर्टिंग बढ़ते क्रम में होती है, पहले इसे अधिकतम हीप में बदलकर। आप हीपसॉर्ट को एक उन्नत गुणवत्ता वाले बाइनरी सर्च ट्री के रूप में देख सकते हैं।

आम तौर पर, हीप डेटा संरचना दो रणनीतियों को नियोजित करती है। इनपुट 12 – 8 – 4 – 2 और 1 के लिए

न्यूनतम हीप – शीर्ष पर न्यूनतम मान
अधिकतम हीप – शीर्ष पर उच्चतम मान

मिन हीप

मिन हीप संरचना में, रूट नोड का मान उस नोड पर बच्चों के बराबर या उससे छोटा होता है। मिन हीप का यह हीप नोड न्यूनतम मान रखता है। कुल मिलाकर, इसकी मिन-हीप संरचना एक पूर्ण है बाइनरी वृक्ष.

एक बार जब आपके पास पेड़ में न्यूनतम हीप हो, तो सभी पत्तियाँ व्यवहार्य उम्मीदवार हैं। हालाँकि, सटीक अधिकतम-हीप मान प्राप्त करने के लिए आपको प्रत्येक पत्ती की जाँच करने की आवश्यकता है।

न्यूनतम हीप उदाहरण

उपरोक्त आरेख में आप मूल से लेकर निम्नतम नोड तक कुछ स्पष्ट अनुक्रम देख सकते हैं।

मान लीजिए कि आप तत्वों को Array Array_N[12,2,8,1,4] में संग्रहीत करते हैं। जैसा कि आप सरणी से देख सकते हैं, मूल तत्व न्यूनतम हीप प्राथमिकता का उल्लंघन कर रहा है। न्यूनतम हीप गुण को बनाए रखने के लिए, आपको तत्वों को स्वैप करने के लिए min-heapify ऑपरेशन करना होगा जब तक कि न्यूनतम हीप गुण पूरे न हो जाएं।

अधिकतम ढेर

मैक्स हीप की संरचना में, पैरेंट या रूट नोड का मान नोड में उसके बच्चों के बराबर या उससे बड़ा होता है। यह नोड अधिकतम मान रखता है। इसके अलावा, यह एक पूर्ण बाइनरी ट्री है, इसलिए आप मानों के संग्रह से अधिकतम हीप बना सकते हैं और इसे O(n) समय पर चला सकते हैं।

जावा मैक्स हीप को क्रियान्वित करने के लिए यहां कुछ विधियां दी गई हैं

जोड़ना (): एक नया तत्व हीप में रखें। यदि आप एक सरणी का उपयोग करते हैं, तो ऑब्जेक्ट सरणी के अंत में जोड़े जाते हैं, जबकि बाइनरी ट्री में, ऑब्जेक्ट ऊपर से नीचे और फिर बाएं से दाएं जोड़े जाते हैं।
निकालना (): यह विधि आपको सरणी सूची से पहला तत्व हटाने की अनुमति देती है। चूंकि नया जोड़ा गया तत्व अब सबसे बड़ा नहीं है, इसलिए Sift-Down विधि हमेशा इसे अपने नए स्थान पर धकेल देती है।
सिफ्ट-डाउन ()यह विधि मूल ऑब्जेक्ट की तुलना उसके चाइल्ड से करती है और फिर नए जोड़े गए नोड को उसके सही स्थान पर धकेलती है।
सिफ्ट-अप (): यदि आप किसी सरणी में नया डाला गया तत्व जोड़ने के लिए सरणी विधि का उपयोग करते हैं, तो सिफ्ट-अप विधि नए जोड़े गए नोड को उसके नए स्थान पर स्थानांतरित करने में मदद करती है। नए डाले गए आइटम की तुलना पहले ट्री डेटा संरचना का अनुकरण करके पैरेंट से की जाती है।
सूत्र Parent_Index=Child_Index/2 लागू करें। आप ऐसा तब तक करते रहें जब तक कि अधिकतम तत्व सरणी के सामने न आ जाए।

बेसिक हीप Operaमाहौल

डेटा के सेट में उच्चतम और निम्नतम मान खोजने के लिए, आपको बहुत सारे बुनियादी हीप ऑपरेशन जैसे कि ढूँढना, हटाना और सम्मिलित करना होगा। चूँकि तत्व लगातार आते-जाते रहेंगे, इसलिए आपको यह करना होगा:

खोज – ढेर में किसी वस्तु को खोजें।
सम्मिलित करें - ढेर में एक नया बच्चा जोड़ें।
मिटाना – हीप से नोड हटाएँ।

ढेर बनाएं

हीप बनाने की प्रक्रिया को हीप बनाना कहते हैं। कुंजियों की एक सूची दिए जाने पर, प्रोग्रामर एक खाली हीप बनाता है और फिर बुनियादी हीप संचालन का उपयोग करके एक-एक करके अन्य कुंजियाँ सम्मिलित करता है।

तो चलिए एक हीप में 12,2,8,1 और 4 मान डालकर विलियम की विधि का उपयोग करके एक मिन-हीप बनाना शुरू करते हैं। आप एक खाली हीप से शुरू करके और फिर O (nlogn) समय का उपयोग करके इसे क्रमिक रूप से अन्य तत्वों से भरकर n तत्वों के साथ हीप बना सकते हैं।

हीपफाई: सम्मिलन एल्गोरिथ्म, जो हीप में तत्वों को सम्मिलित करने में मदद करता है। जाँचता है कि क्या हाइलाइट की गई प्रॉपर्टी हीप डेटा संरचना का पालन किया गया है।
उदाहरण के लिए, एक अधिकतम हीपिफ़ाई यह जाँच करेगा कि क्या पैरेंट का मान उसके संतान से अधिक है। फिर तत्वों को स्वैपिंग जैसी विधियों का उपयोग करके क्रमबद्ध किया जा सकता है।

मर्ज: यह मानते हुए कि आपके पास एक में संयोजित करने के लिए दो हीप हैं, दो हीप से मानों को एक साथ लाने के लिए मर्ज हीप का उपयोग करें। हालाँकि, मूल हीप अभी भी संरक्षित हैं।

ढेर का निरीक्षण करें

हीप का निरीक्षण करने से तात्पर्य हीप डेटा संरचना में तत्वों की संख्या की जांच करना और यह सत्यापित करना है कि हीप खाली है या नहीं।

तत्वों की छंटाई या कतार के रूप में हीप का निरीक्षण करना महत्वपूर्ण है। यह जाँचना महत्वपूर्ण है कि क्या आपके पास Is-Empty() का उपयोग करके संसाधित करने के लिए तत्व हैं। हीप का आकार अधिकतम-हीप या न्यूनतम-हीप का पता लगाने में मदद करेगा। इसलिए, आपको हीप प्रॉपर्टी के बाद के तत्वों को जानना होगा।

आकार - ढेर का परिमाण या लंबाई लौटाता है। आप बता सकते हैं कि कितने तत्व क्रमबद्ध क्रम में हैं।
खाली है - यदि हीप NULL है, तो यह TRUE लौटाता है, अन्यथा, यह FALSE लौटाता है।

यहाँ, आप सभी तत्वों को प्रिंट कर रहे हैं प्राथमिकताQ लूप और फिर जाँच करना कि प्राथमिकताQ रिक्त नहीं है।

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

हीप डेटा संरचना के उपयोग

हीप डेटा संरचना वास्तविक जीवन में कई प्रोग्रामिंग अनुप्रयोगों में उपयोगी है जैसे:

स्पैम फ़िल्टरिंग में मदद करता है.
ग्राफ एल्गोरिदम का कार्यान्वयन.
Operaसिस्टम लोड संतुलन, और डेटा संपीड़न.
आँकड़ों में क्रम खोजें.
प्राथमिकता कतारों को क्रियान्वित करें जहां आप सूची में आइटमों को लघुगणकीय समय में खोज सकते हैं।
हीप डेटा संरचना का उपयोग सॉर्टिंग के लिए भी किया जाता है।
ग्राहकों को एक लाइन में खड़ा करना।
में हैंडलिंग में बाधा Operaटिंग सिस्टम.
डेटा संपीड़न के लिए हफ़मैन की कोडिंग में।

हीप प्राथमिकता कतार गुण

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

हीप प्राथमिकता कतार को कार्यान्वित करने के चरण Java

कोड उदाहरण के साथ जावा में हीप सॉर्ट

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap the root and the largest element and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

उत्पादन

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

हीप सॉर्ट इन Python कोड उदाहरण के साथ

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)