കൂമ്പാരം അടുക്കുക  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു 24 * 7 ഇന്നൊവേഷൻ ലാബുകൾ ആമസോൺ ആപ്പിൾ ബെൽസബാർ Intuit ഒറാക്കിൾ സാംസങ് എസ്.എ.പി എസ്എപി ലാബുകൾ വിസ
അറേ ക്രമപ്പെടുത്തൽ

ഒരു ബൈനറി ഹീപ്പ് ഡാറ്റാ ഘടനയെ അടിസ്ഥാനമാക്കിയുള്ള ഒരു താരതമ്യ അധിഷ്ഠിത തരംതിരിക്കൽ സാങ്കേതികതയാണ് ഹീപ്പ് സോർട്ട്. ഹീപ്‌സോർട്ട് ഒരു സെലക്ഷൻ സോർട്ടിന് സമാനമാണ്, അവിടെ ഞങ്ങൾ പരമാവധി ഘടകം കണ്ടെത്തി ആ മൂലകം അവസാനം സ്ഥാപിക്കുന്നു. ശേഷിക്കുന്ന ഘടകങ്ങൾ‌ക്കായി ഞങ്ങൾ‌ സമാന പ്രക്രിയ ആവർത്തിക്കുന്നു.

ക്രമീകരിക്കാത്ത ഒരു അറേ നൽകി, ഹീപ്പ് സോർട്ട് ഉപയോഗിച്ച് അടുക്കുക  

ഇവിടെ നൽകിയിരിക്കുന്ന ഇൻപുട്ട് ഒരു തരംതിരിക്കാത്ത അറേ ആണ്, കൂടാതെ ഞങ്ങൾ ഹേപ്പ് സോർട്ട് ഉപയോഗിച്ച് അറേ അടുക്കണം.

ഇൻപുട്ട്: 9,5,1,6,11,8,4

ഔട്ട്പുട്ട്: 1,4,5,6,8,9,11

ഹീപ്പ് സോർട്ട് അൽ‌ഗോരിതം  

  • ഹീപ്‌സോർട്ട് ഒരു താരതമ്യ-അധിഷ്‌ഠിത അൽ‌ഗോരിതം ആണ്, ഇത് അറേയുടെ അവസാനത്തിൽ പരമാവധി ഘടകം സ്ഥാപിക്കുന്നു, അറേ മുഴുവനും അടുക്കുന്നതുവരെ ശേഷിക്കുന്ന അറേ ഘടകങ്ങൾക്കുള്ള പ്രക്രിയ ആവർത്തിക്കുന്നു.
  • ഹീപ്പ് സോർട്ട് അറേയിൽ നിന്ന് ഒരു ബൈനറി മാക്സ്-ഹീപ്പ് നിർമ്മിക്കുന്നു. ഒരു ട്രീ ഡാറ്റാ ഘടനയാണ് മാക്സ് ഹീപ്പ് അതിൽ ഓരോ രക്ഷാകർതൃ നോഡും അതിന്റെ ചൈൽഡ് നോഡിനേക്കാൾ വലുതാണ്.
  • അറേ അറയെ ഒരു ബൈനറി ട്രീ ആയി പ്രതിനിധീകരിക്കാം,
    1. arr [0] റൂട്ട് നോഡ് ആണ്.
    2. ഇടത് കുട്ടികളുടെ സൂചിക = 2 * i + 1
    3. ശരിയായ കുട്ടികളുടെ സൂചിക = 2 * i + 2

എവിടെ i പാരന്റ് നോഡിന്റെ സൂചികയാണ്.

  • A ഉപയോഗിച്ച് ബൈനറി ട്രീ ബൈനറി കൂമ്പാരമായി പരിവർത്തനം ചെയ്യുന്നു കൂമ്പാരം പ്രവർത്തനം, ഈ പ്രവർത്തനം ചൈൽഡ് നോഡുകളേക്കാൾ വലുതായ രക്ഷാകർതൃ നോഡിന്റെ മൂല്യം നിലനിർത്തുന്നു (മാക്സ് ഹീപ്പ്). രക്ഷാകർതൃ നോഡ് ചൈൽഡ് നോഡുകളേക്കാൾ കുറവാണെങ്കിൽ, അത് ഏറ്റവും വലിയ മൂല്യമുള്ള ചൈൽഡ് നോഡിനൊപ്പം രക്ഷകർത്താവിനെ സ്വാപ്പ് ചെയ്യുന്നു.
ഇതും കാണുക
ഒരു മരത്തിൽ രണ്ട് നോഡുകൾ ഒരേ പാതയിലാണോയെന്ന് പരിശോധിക്കുക

മാക്സ് ഹീപ്പ് പ്രവർത്തനത്തിന്റെ ഉദാഹരണം  

ഒരു വൃക്ഷത്തിന്റെ പരമാവധി മൂല്യം 0 ഉം ഇടത് കുട്ടി 5 ഉം വലത് കുട്ടി 4 ഉം ആണ്.

കൂമ്പാരം അടുക്കുകമൊട്ടുസൂചി

അൽഗോരിതം  

ഒരു ഹീപ്പ് സോർട്ട് അൽ‌ഗോരിതം ഞങ്ങൾ പ്രധാനമായും രണ്ട് ഫംഗ്ഷനുകൾ ഉപയോഗിക്കുന്നു.

  1. heapServe (arr, i, n) - കൂമ്പാരമാക്കുന്നു ith ന്റെ നോഡ് arr []
  2. heapsort (arr, n) -
    1. ഇത് ആദ്യം മുഴുവൻ അറേയും കൂട്ടിചേർക്കുന്നു (ഇലയില്ലാത്ത നോഡുകൾ കൂമ്പാരമാക്കി).
    2. റൂട്ടിലെ ഏറ്റവും വലിയ മൂലകം വേർതിരിച്ചെടുക്കുന്നു.
    3. അറേയുടെ അവസാന ഘടകം ഉപയോഗിച്ച് അത് മാറ്റിസ്ഥാപിക്കുന്നു.
    4. പൂർണ്ണമായും അടുക്കിയ അറേ ലഭിക്കുന്നതുവരെ ആവർത്തന പ്രക്രിയ a, b, c (ക്രമത്തിൽ). എവിടെ a is 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

ഹീപ്‌സോർട്ടിന്റെ സങ്കീർണ്ണത വിശകലനം  

  • കൂമ്പാരീകരണത്തിന്റെ സങ്കീർണ്ണത O (ലോഗ്) ആണ്, ഓരോ മൂലകവും വേർതിരിച്ചെടുക്കുന്നതിന് O (n) സമയമെടുക്കും, മൊത്തത്തിലുള്ള സങ്കീർണ്ണത T (n) = O (nlogn).
  • മികച്ച കേസ്: T (n) = O (nlogn)
  • ഏറ്റവും മോശം കേസ്: T (n) = O (nlogn)
  • ശരാശരി കേസ്: T (n) = O (nlogn)
  • സഹായ സ്ഥലം, A (n) = O (1)
ഇതും കാണുക
സ്വയം വിഭജിക്കുന്ന നമ്പറുകൾ

ഹീപ്‌സോർട്ടിനെക്കുറിച്ചുള്ള അനുബന്ധ വിവരങ്ങൾ

  • ഇൻ‌പ്ലേസ് സോർട്ടിംഗ് അൽ‌ഗോരിതം ആണ് ഹീപ്‌സോർട്ട്.
  • ഹീപ്പ് അടുക്കൽ ഒരു സ്ഥിരമായ അൽഗോരിതം അല്ല.
  • ആവർത്തന കോളുകൾ കാരണം സ്ഥിരമായ സമയ ഓവർഹെഡ് ഉള്ളതിനാൽ ക്വിക്സോർട്ടും ലയനം അടുക്കുന്നതും പലപ്പോഴും ഹീപ്‌സോർട്ടിനേക്കാൾ മികച്ച പ്രകടനം കാഴ്ചവയ്ക്കുന്നു.

അവലംബം

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

അനുബന്ധ ലേഖനം

ലിങ്കുചെയ്‌ത ലിസ്റ്റുകൾക്കായി ദ്രുതഗതിയിലുള്ള അടുക്കുന്നതിനേക്കാൾ മികച്ചത് അടുക്കുക

1