हिप क्रमबद्ध


कठिनाई तह मध्यम
बारम्बार सोधिन्छ २ * * ov इनोवेशन ल्याबहरू अमेजन एप्पल बेलजाबार Intuit बजेट Samsung SAP SAP ल्याबहरू भिषा
एरे क्रमबद्ध

हिप क्रमबद्ध एक तुलना आधारित छँटाई टेकनीक जुन बाइनरी हिप डेटा संरचनामा आधारित छ। हिपसोर्ट एक चयन क्रमसँग मिल्दोजुल्दो छ जहाँ हामी अधिकतम तत्व फेला पार्दछौं र त्यस तत्वलाई अन्तमा राख्दछौं। बाँकी तत्वहरूको लागि हामी समान प्रक्रिया दोहोर्याउँछौं।

एक क्रमबद्ध एर्रे दिइयो, यसलाई हिप क्रमबद्ध गरेर क्रमबद्ध गर्नुहोस्

यहाँ दिईएको इनपुट एक अनसोर्टेड एर्रे हो र हामीले एरेलाई हिप क्रमबद्ध गरेर क्रमबद्ध गर्नु पर्छ।

आगत: 9,5,1,6,11,8,4

उत्पादन: 1,4,5,6,8,9,11

हिप क्रमबद्ध एल्गोरिथ्म

  • हिप्सोर्ट तुलनामा आधारित एल्गोरिथ्म हो, यसले एर्रेको अन्त्यमा अधिकतम तत्त्व राख्छ, एरेको बाँकी भागको लागि प्रक्रिया दोहोर्याउँदछ सम्म एरेको सम्पूर्ण क्रमबद्ध नगरेसम्म।
  • हिप सॉर्टले एर्रेबाट बाइनरी म्याक्स-हेप बनाउँदछ। अधिकतम हिप एक रूख डेटा संरचना हो जहाँ प्रत्येक अभिभावक नोड आफ्नो बच्चा नोड भन्दा ठूलो हुन्छ।
  • एर्रे एर [] बाइनरी रूखको रूपमा प्रतिनिधित्व गर्न सकिन्छ,
    1. एर [०] मूल नोड हो।
    2. बायाँ बच्चाहरूको सूचकांक = २ * i + १
    3. सही बच्चाहरूको सूचकांक = २ * i + १

कहाँ i प्यारेन्ट नोडको अनुक्रमणिका हो।

  • बाइनरी ट्री बाइनरी हिपमा रूपान्तरण गरीयो a Heapify अपरेशन, यो अपरेसनले अभिभावक नोडको मान कायम गर्दछ जुन बच्चा नोडहरू भन्दा ठूलो हुन्छ (अधिकतम ढेर)। यदि अभिभावक नोड बच्चा नोडहरू भन्दा कम छ भने, त्यसपछि यो प्यारेन्टलाई बच्चा नोडको साथ ठूलो मानको साथ अदला-बदली गर्दछ।

अधिकतम हिप अपरेशनको उदाहरण

तल रूखको अधिकतम हिप अपरेशन हो जसको मूल मान 0 छ, बायाँ बच्चा 5 र दायाँ बच्चा is हो।

हिप क्रमबद्ध

अल्गोरिदम

हामी मुख्यतया दुई कार्यहरू हिप क्रमबद्ध एल्गोरिथ्ममा प्रयोग गर्दछौं।

  1. heapServe (एर, आई, एन) - heapifies ith नोड एर []
  2. हिप्सोर्ट (एर, एन) -
    1. यसले पहिले पूरै एर्रेलाई heapifies (गैर-पात नोडहरू हेपाईफाई गरेर)।
    2. मूलमा सबैभन्दा ठूलो तत्व निकाल्छ।
    3. एर्रेको अन्तिम तत्वको साथ बदल्छ।
    4. प्रक्रिया पूर्ण रूपमा ए, बी, सी (क्रममा) दोहोर्याउँदछ सम्म हामी पूर्ण रूपमा क्रमबद्ध एर्रे प्राप्त गर्दैनौं। कहाँ a heapServe (हिप क्रमबद्धको लागि सेवा प्रकार्य), b र heapSort छ c मूल निकासी छ।

हिप क्रमबद्ध

हिप क्रमबद्ध

हिप क्रमबद्ध

सी ++ कार्यक्रम हिप क्रमबद्धको लागि

#include <iostream>
using namespace std;

// service function to heapify array
void heapServe(int arr[],int i,int n)
{
    int large = i;
    // index of left and right child
    int left = 2*i+1;
    int right = 2*i+2;

    // find largest amongst parent ,left and right children
    if(left < n && arr[left] > arr[large])
    large = left;
    if(right < n && arr[right] > arr[large])
    large = right;

    // swap if parent node is not largest
    // recursiveley heapify swapped nodes
    if(large != i)
    {
        swap(arr[i],arr[large]);
        heapServe(arr,large,n);
    }
}

// function to sort the array
// Parent node is node that has atleast one children
void heapSort(int arr[],int n)
{
    // Index of last/right most parent node
    int last_non_leaf = n/2 - 1;

    // heapify the array beginning from right most parent node
    for(;last_non_leaf >= 0;last_non_leaf--)
    heapServe(arr,last_non_leaf,n);
    
    // start sorting from rightmost of the array
    for(int i=n-1;i >= 0;i--)
    {
        // Extract root (largest) element,swap with last array element
        swap(arr[0],arr[i]);
        // heapify the leftover array (obtained after extracting largest element)
        heapServe(arr,0,i);
    }
}

int main()
{
    int arr[] = {9,5,1,6,11,8,4};
    int n = sizeof(arr)/sizeof(arr[0]);

    heapSort(arr,n);

    for(int i=0;i<n;i++)
    cout<<arr[i]<<" ";
    
    return 0;
}

उत्पादन

1 4 5 6 7 8 9

हिप क्रमबद्धको लागि जाभा कार्यक्रम

class heap
{
    // service function to heapify array
    public static void heapServe(int arr[],int i,int n)
    {
        int large = i;
        // index of left and right child
        int left = 2*i+1;
        int right = 2*i+2;

        // find largest amongst parent ,left and right children
        if(left < n && arr[left] > arr[large])
        large = left;
        if(right < n && arr[right] > arr[large])
        large = right;

        // swap if parent node is not largest
        // recursiveley heapify swapped nodes
        if(large != i)
        {
            int temp = arr[large];
            arr[large] = arr[i];
            arr[i] = temp;
            heapServe(arr,large,n);
        }
    }
    // function to sort the array
    // Parent node is node that has atleast one children
    public static void heapSort(int arr[],int n) 
    {
        // Index of last/right most parent node
        int last_non_leaf = n/2 - 1;
        
        // heapify the array beginning from right most parent node
        for(;last_non_leaf >= 0;last_non_leaf--)
        heapServe(arr,last_non_leaf,n);

        // start sorting from rightmost of the array
        for(int i=n-1;i >= 0;i--)
        {
            // Extract root (largest) element,swap with last array element
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            
            // heapify the leftover array (obtained after extracting largest element)
            heapServe(arr,0,i);
        }
    }

    public static void main(String args[]) 
    {
        int arr[] = {9,5,1,6,11,8,4};
        int n = arr.length;

        heapSort(arr,n);

        for(int i=0;i<n;i++)
        System.out.print(arr[i]+" ");
    }
}

उत्पादन

1 4 5 6 7 8 9

जटिलता HeapSort को विश्लेषण

  • हेपिफिकेसनको जटिलता O (लग) हो, प्रत्येक तत्त्व निकाल्दा O (n) समय लाग्छ, समग्र जटिलता T (n) = O (nlogn)।
  • उत्तम केस: T (n) = O (nlogn)
  • सबैभन्दा खराब केस: T (n) = O (nlogn)
  • औसत केस: T (n) = O (nlogn)
  • सहायक स्पेस, A (n) = O (१)

HeapSort मा पूरक जानकारी

  • हिप्सोर्ट एक इन्स्टलेस सॉर्टिंग एल्गोरिथ्म हो।
  • हिप क्रमबद्ध एक स्थिर एल्गोरिथ्म होईन।
  • क्विकसोर्ट र मर्ज क्रमबद्ध अक्सर हिपसोर्ट भन्दा राम्रो प्रदर्शन गर्दछ किनकि यसमा रिकर्सिव कलहरूको कारण केही स्थिर समय ओभरहेड छ।

संदर्भ

https://en.wikipedia.org/wiki/Heapsort

सम्बन्धित लेख

लि linked्क गरिएको सूचीहरूको लागि द्रुत क्रमबद्ध भन्दा उत्तम क्रम मिलाउनुहोस्