ගොඩවල් වර්ග කිරීම


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ 24 * 7 නවෝත්පාදන විද්‍යාගාර ඇමේසන් Apple ජංගම දුරකථන බෙල්සබාර් ඉන්ටයිට් ඔරකල් Samsung ජංගම දුරකථන SAP SAP විද්‍යාගාර වීසා
අරා වර්ග කිරීම

ගොඩවල් වර්ග කිරීම යනු ද්විමය ගොඩවල් දත්ත ව්‍යුහයක් මත පදනම් වූ සංසන්දනය පදනම් කරගත් වර්ග කිරීමේ තාක්‍ෂණයකි. HeapSort යනු තේරීම් වර්ගයකට සමාන වන අතර එහිදී අපි උපරිම මූලද්‍රව්‍යය සොයාගෙන එම මූලද්‍රව්‍යය අවසානයේ තබන්න. ඉතිරි මූලද්රව්ය සඳහා අපි එකම ක්රියාවලියම නැවත කරන්නෙමු.

වර්ගීකරණය නොකළ අරාවක් ලබා දී, ගොඩවල් වර්ග කිරීම මඟින් එය වර්ග කරන්න

මෙහි දී ඇති ආදානය වර්ගීකරණය නොකළ අරාව වන අතර අපට අරාව වර්ග ගොඩගැසීම මඟින් වර්ග කළ යුතුය.

ආදාන: 9,5,1,6,11,8,4

ප්රතිදාන: 1,4,5,6,8,9,11

ගොඩවල් වර්ග කිරීමේ ඇල්ගොරිතම

  • HeapSort යනු සංසන්දනය මත පදනම් වූ ඇල්ගොරිතමයකි, එය අරාව අවසානයේ උපරිම මූලද්‍රව්‍යය ස්ථානගත කරයි, මුළු අරාව වර්ග කරන තෙක් ඉතිරි අරාව මූලද්‍රව්‍ය සඳහා ක්‍රියාවලිය නැවත සිදු කරයි.
  • Heap Sort මඟින් අරාවෙන් පිටත ද්විමය උපරිම ගොඩක් සාදයි. මැක්ස් ගොඩවල් යනු ගස් දත්ත ව්‍යුහයකි සෑම දෙමාපිය නෝඩයක්ම එහි ළමා නෝඩයට වඩා විශාල වේ.
  • අරාව ආර් [] ද්විමය ගසක් ලෙස නිරූපණය කළ හැකිය,
    1. arr [0] root node වේ.
    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 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 (logn) වේ, එක් එක් මූලද්‍රව්‍යය නිස්සාරණය කිරීම සඳහා O (n) කාලය ගතවේ, සමස්ත සංකීර්ණතාව T (n) = O (nlogn) වේ.
  • හොඳම අවස්ථාව: T (n) = O (nlogn)
  • නරකම අවස්ථාව: T (n) = O (nlogn)
  • සාමාන්‍ය නඩුව: T (n) = O (nlogn)
  • සහායක අවකාශය, A (n) = O (1)

HeapSort පිළිබඳ අතිරේක තොරතුරු

  • HeapSort යනු ස්ථානීය වර්ග කිරීමේ ඇල්ගොරිතමයකි.
  • ගොඩවල් වර්ග කිරීම ස්ථාවර ඇල්ගොරිතමයක් නොවේ.
  • පුනරාවර්තන ඇමතුම් හේතුවෙන් ක්වික්සෝර්ට් සහ ඒකාබද්ධ කිරීමේ වර්ග කිරීම බොහෝ විට හීප්සෝර්ට් වලට වඩා හොඳින් ක්‍රියා කරයි.

විමර්ශන

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

අදාළ ලිපිය

සම්බන්ධිත ලැයිස්තු සඳහා ඉක්මන් වර්ග කිරීමකට වඩා වර්ග කිරීම ඒකාබද්ධ කරන්න