Yığın Sort

Heap sort, ikili yığın məlumat strukturuna əsaslanan müqayisə əsaslı çeşidləmə texnikasıdır. HeapSort, maksimum elementi tapdığımız və sonunda bu elementi yerləşdirdiyimiz seçim növünə bənzəyir. Qalan elementlər üçün də eyni prosesi təkrarlayırıq.

Mündəricat

Çeşidlənməmiş bir sıra verildiyi üçün, Heap Sort istifadə edərək sırala

Burada verilən giriş çeşidlənməmiş bir massivdir və yığını sıralama istifadə edərək sıralamalıyıq.

Input: 9,5,1,6,11,8,4

Buraxılış: 1,4,5,6,8,9,11

Heap Sort Alqoritmi

HeapSort müqayisə əsaslı bir alqoritmdir, massivin sonunda maksimum element yerləşdirir, massivin hamısı sıralanana qədər massivin qalan elementləri üçün prosesi təkrarlayır.
Heap Sort, massivdən ikili maksimum yığın düzəldir. Maksimum yığın bir ağac məlumat quruluşudur burada hər bir ana düyün uşaq düyündən daha böyükdür.
Array arr [] ikili Ağac kimi təmsil oluna bilər,
1. arr [0] kök düyündür.
2. Sol uşaqların indeksi = 2 * i + 1
3. Doğru uşaq indeksi = 2 * i + 2

Hara i ana düyünün indeksidir.

Binary Tree a istifadə edərək ikili yığına çevrilir Yığışdırmaq əməliyyat, bu əməliyyat uşaq düyünlərindən daha böyük olan ana düyünün dəyərini saxlayır (Max yığın). Əgər ana düyün uşaq düyünlərindən azdırsa, bu zaman ən böyük dəyərə sahib olan ana düyünü uşaq nodu ilə dəyişdirir.

Maksimum yığın əməliyyatı nümunəsi

Aşağıda kök dəyəri 0, sol uşağı 5, sağ uşağı 4 olan bir ağacın maksimum yığma əməliyyatı verilmişdir.

Alqoritm

Toplu sıralama alqoritmində əsasən iki funksiyadan istifadə edirik.

heapServe (arr, i, n) - yığışdırır i^th nodu arr []
heapsort (arr, n) -
1. əvvəlcə bütün massivi yığışdırır (yarpaq olmayan qovşaqları yığaraq).
2. kökdəki ən böyük elementi çıxarır.
3. onu serialın son elementi ilə əvəz edir.
4. tamamilə sıralanmış bir sıra əldə edənə qədər a, b, c prosesi (qaydada) təkrarlayır. Harada a heapServe (yığın növü üçün xidmət funksiyası), b heapSort və c çıxarış köküdür.

Heap Sort üçün C ++ Proqramı

#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;
}

Buraxılış

1 4 5 6 7 8 9

Heap Sort üçün Java Proqramı

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]+" ");
    }
}

Buraxılış

1 4 5 6 7 8 9

HeapSort'un Mürəkkəblik Analizi

Dökülmənin mürəkkəbliyi O (logn), hər elementin çıxarılması O (n) vaxt, ümumi mürəkkəblik T (n) = O (nlogn) tələb edir.
Ən yaxşı hal: T (n) = O (nlogn)
Ən pis hal: T (n) = O (nlogn)
Orta hal: T (n) = O (nlogn)
Köməkçi boşluq, A (n) = O (1)

HeapSort haqqında əlavə məlumat

HeapSort Yerdə Sıralama Alqoritmidir.
Heap Sort - Sabit Alqoritm deyil.
Quicksort və Merge Sort tez-tez rekursiv zənglər səbəbiylə bir az daimi vaxt yükü olduğu üçün HeapSort'dan daha yaxşı performans göstərirlər.

arayış

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

Əlaqədar məqalə

Bağlı siyahılar üçün sürətli sıralamadan daha yaxşı birləşdirin