Үйінді сұрыптау алгоритмі

Heap Sort, сортировка, алгоритмы

Үйме сұрыптау - компьютерлік бағдарламалаудағы танымал және тиімді сұрыптау алгоритмі. Үйінді сұрыптау алгоритмін жазуды үйрену деректер құрылымының екі түрін - массивтер мен ағаштарды білуді талап етеді.

Мысалы, біз сұрыптағымыз келетін сандардың бастапқы жиыны [10, 3, 76, 34, 23, 32] массивінде сақталады, ал сұрыптағаннан кейін сұрыпталған массив [3,10,23,32, 34,76].

Үйме сұрыптау массив элементтерін үйме деп аталатын толық екілік ағаштың арнайы түрі ретінде көрсету арқылы жұмыс істейді.

Екілік ағаш дегеніміз не? Екілік ағаштардың қандай түрлері бар?

Екілік ағаш - әрбір негізгі түйінде ең көбі екі еншілес болуы мүмкін ағаш деректер құрылымы.

Толық екілік ағаш – бұл екілік ағаштың ерекше түрі, онда әрбір ата-аналық түйінде екі немесе ешқандай еншілес болмайды.

Мінсіз екілік ағаш толық екілік ағашқа ұқсас, бірақ екі негізгі айырмашылығы бар:

1. Әр деңгей толығымен толтырылуы керек.
2. Барлық парақ элементтері солға еңкейуі керек.

Ескертпе: Соңғы элементтің жарамды бауыры болмауы мүмкін, яғни идеалды екілік ағаштың толық екілік ағаш болуы қажет емес.

Сұрыпталмаған тізімнен (массив) толық екілік ағашты қалай жасауға болады?

• Түбірлік түйін болу үшін тізімнің бірінші элементін таңдаңыз. (Бірінші деңгей – 1 элемент).
• Екінші элементті түбір түйінінің сол жақ еншілес элементі ретінде және үшінші элементті оң жақ еншілес элемент ретінде орналастырыңыз. (Екінші деңгей – 2 элемент).
• Келесі екі элементті екінші деңгейдің сол жақ түйінінің еншілестері ретінде орналастырыңыз. Тағы да келесі екі элементті екінші деңгейлі оң түйіннің еншілестері ретінде орналастырыңыз (3-деңгей - 4 элемент).
• Соңғы элементке жеткенше қайталаңыз.

Массив индекстері мен ағаш элементтері арасындағы байланыс

Толық екілік ағаштың қызықты қасиеті бар, оны біз кез келген түйіннің балалары мен ата-аналарын табу үшін пайдалана аламыз.
Егер массивтің кез келген элементінің индексі i болса, 2i + 1 индексіндегі элемент сол жақтағы еншілес, ал 2i + 2 индексіндегі элемент оң жақтағы еншілес болады. Сондай-ақ, i индексіндегі кез келген элементтің ата-анасына (i-1) / 2 төменгі шегі беріледі.

Оны тексеріп көрейік:

Left child of 1 (index 0)
= element in (2*0+1) index 
= element in 1 index 
= 12


Right child of 1
= element in (2*0+2) index
= element in 2 index 
= 9

Similarly,
Left child of 12 (index 1)
= element in (2*1+1) index
= element in 3 index
= 5

Right child of 12
= element in (2*1+2) index
= element in 4 index
= 6

Сондай-ақ ережелердің кез келген түйіннің ата-анасын табу үшін дұрыс екенін растаңыз:

Parent of 9 (position 2) 
= (2-1)/2 
= ½ 
= 0.5
~ 0 index 
= 1

Parent of 12 (position 1) 
= (1-1)/2 
= 0 index 
= 1

Жиым индекстерін ағаш орындарына салыстыруды түсіну үйме деректер құрылымының қалай жұмыс істейтінін және оның үйме сұрыптауды жүзеге асыру үшін қалай пайдаланылатынын түсіну үшін өте маңызды.

Деректердің үйінді құрылымы дегеніміз не?

Үйме – ағаш тәрізді арнайы деректер құрылымы. Екілік ағаш егер болса, үйме деректер құрылымын бақылайды дейді

• бұл толық екілік ағаш;
• ағаштың барлық түйіндері олардың балаларынан үлкенірек қасиетке бағынады, яғни ең үлкен элемент түбірде және оның екі еншісінде де түбірден кіші және т.б. Мұндай үйінді кему үйіндісі (Max-Heap) деп атайды. Оның орнына барлық түйіндер өз еншілестерінен кішірек болса, бұл өсіп келе жатқан үйме (Min-Heap) деп аталады.

Суретте сол жақта азайып бара жатқан үйінді, оң жақта ұлғайған үйінді.

Ағашты қалай салу керек

Керемет екілік ағаштан бастап, үйменің барлық жапырақты емес элементтерінде heapify функциясын іске қосу арқылы оны кему жолына өзгерте аламыз.

Heapfiy рекурсияны пайдаланатындықтан, мұны түсіну қиын болуы мүмкін. Ендеше, алдымен үш элементтен тұратын ағашты қалай жасайтындығыңызды ойластырайық.

heapify(array)
    Root = array[0]
    Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
    if(Root != Largest)
          Swap(Root, Largest)

Жоғарыдағы мысал екі сценарийді көрсетеді - біреуі түбір ең үлкен элемент және бізге ештеңе істеудің қажеті жоқ. Түбірде үлкенірек бала бар тағы бірінде және кішірейетін үйме сипатын сақтау үшін оларды ауыстыру қажет болды.
Егер сіз бұрын рекурсивті алгоритмдермен жұмыс істеген болсаңыз, онда бұл негізгі жағдай болуы керек екенін түсінесіз.

Енді бірнеше деңгей болатын басқа сценарийді қарастырайық.

Суретте екінші деңгейлі түбір элементінің екі ішкі ағаштары да бұрыннан бар
төмендейтін үйінділер.
Жоғарғы элемент кему үйіндісіне сәйкес келмейді, бірақ барлық ішкі ағаштар төмендейді.
Бүкіл ағаш үшін кему сипатын сақтау үшін ата-ананы оның дұрыс орнына жеткенше «итеру» керек.

Осылайша, екі ішкі ағаштар да төмендейтін ағашта кему сипатын сақтау үшін түбір элементінде оның еншілестерінен үлкен болғанша немесе ол жапырақ түйініне айналғанша heapify функциясын қайта-қайта орындауымыз керек.

Біз осы екі шарттың екеуін бір үйінді функциясына келесідей біріктіре аламыз:

void heapify(int arr[], int n, int i)
{
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if (l < n && arr[l] > arr[largest])
     largest = l;

   if (right < n && arr[r] > arr[largest])
     largest = r;

   if (largest != i)
   {
     swap(arr[i], arr[largest]);

     // Recursively heapify the affected sub-tree
     heapify(arr, n, largest);
   }
}

Бұл функция негізгі корпус үшін де, кез келген ағаш өлшемі үшін де жұмыс істейді. Осылайша, ішкі ағаштар кішірейіп жатқанда, кез келген ағаш өлшемі үшін кішірейетін үйме күйін сақтау үшін түбір элементін дұрыс орынға жылжыта аламыз.

Төмендеу үйіндісі

Кез келген ағаштан кему үйіндісін құру үшін біз әрбір ішкі ағашты төменнен жоғары қарай салуды бастай аламыз және функцияны барлық элементтерге, соның ішінде түбір элементіне қолданғаннан кейін төмендейтін үйінді аламыз.

Толық ағаш жағдайында жапырақты емес түйіннің бірінші индексі n/2 - 1 ретінде анықталады. Одан кейінгі барлық басқа түйіндер жапырақ түйіндері болып табылады, сондықтан үйме қажет емес.

Біз төмендеу үйіндісін келесідей құра аламыз:

// Build heap (rearrange array)
   for (int i = n / 2 - 1; i >= 0; i--)
     heapify(arr, n, i);

Жоғарыдағы диаграммада көрсетілгендей, біз ең кішкентай ағаштардың шоғырынан бастаймыз және тамыр элементіне жеткенше жоғары қарай жүреміз.

Үйінді сұрыптау процедуралары

1. Ағаш кему сипатын қанағаттандыратындықтан, ең үлкен элемент түбірлік түйінде сақталады.
2. Түбір элементін алып тастаңыз және оны массивтің соңына қойыңыз (n-ші орын). Ағаштың соңғы элементін (үйінді) бос орынға қойыңыз.
3. Үйме өлшемін 1-ге азайтыңыз және түбір элементін түбірде ең үлкен элементке ие болу үшін қайта өсіріңіз.
4. Процесс тізімнің барлық элементтері сұрыпталғанша қайталанады.

Код келесідей көрінеді:

for (int i=n-1; i>=0; i--)
   {
     // Переместить текущий корень в конец
     swap(arr[0], arr[i]);

     // вызовите максимальный heapify на уменьшенной куче
     heapify(arr, i, 0);
   }

Орындалу

Үйме сұрыптауда барлық жағдайлар үшін O(nlogn) уақыт күрделілігі бар (ең жақсы жағдай, орташа жағдай және ең нашар жағдай). Мұның себебі неде? n элементі бар толық екілік ағаштың биіктігі log(n) болып табылады.

Бұрын көргеніміздей, ішкі ағаштары үйінділері төмендеп жатқан элементті толығымен жинақтау үшін элементті оның сол және оң жақ еншілестерімен салыстыруды жалғастырып, оның екі баласы да өзінен кіші болатын нүктеге жеткенше төмен итеруіміз керек.

Ең нашар жағдайда, бірнеше журнал(n) салыстырулары мен своптарын орындау арқылы элементті түбірлік түйіннен жапырақ түйініне жылжыту қажет болады.

build_max_heap қадамында біз мұны n/2 элементтері үшін жасаймыз, сондықтан build_heap қадамының ең нашар күрделілігі n/2 * log(n) ~ nlogn болып табылады.

Сұрыптау қадамында біз түбір элементін соңғы элементпен алмастырамыз және түбір элементін ауыстырамыз. Әрбір элемент үшін бұл қайтадан көп уақытты алады, себебі біз сол элементті тамырдан жапыраққа жылжытуымыз мүмкін. Біз операцияны n рет қайталағандықтан, heap_sort қадамы да nlogn болып табылады.

Сондай-ақ build_max_heap және heap_sort қадамдары бірінен соң бірі орындалатындықтан, алгоритмдік күрделілік көбейтілмейді және nlogn тәртібінде қалады.

Ол сондай-ақ O(1) күрделілік кеңістігінде сұрыпталады. Жылдам сұрыптаумен салыстырғанда, ең нашар жағдай (O(nlogn)). Quicksort ең нашар жағдайда O(n^2) күрделілігіне ие. Бірақ басқа жағдайларда жылдам сұрыптау өте жылдам. Introsort – үйме сұрыптаудың ең нашар жағдайдағы жылдамдығы мен жылдам сұрыптаудың орташа жылдамдығы сияқты артықшылықтарды сақтау үшін жылдам сұрыптау мен үйінді сұрыптауды біріктіретін үйінді сұрыптауға балама.

Үйінді сұрыптауды пайдалану

Linux ядросы сияқты қауіпсіздікке қатысты және ендірілген жүйелер Heapsort жұмыс уақытындағы O(n log n) жоғарғы шекарасы және оның қосалқы қоймасындағы тұрақты O(1) жоғарғы шекарасы себебінен үйінді сұрыптауды пайдаланады.

Heapsort тіпті ең нашар жағдайда да O(n log n) уақыт күрделілігіне ие болса да, оның қосымшалары көп емес (жылдам сұрыптау, біріктіру сияқты басқа сұрыптау алгоритмдерімен салыстырғанда). Дегенмен, оның негізгі деректер құрылымы, үйінді, егер элементтер тізімінен ең кішісін (немесе ең үлкенін) қалған элементтерді сұрыпталған тәртіпте сақтауға қосымша шығындарсыз шығарып алғымыз келсе, тиімді пайдалануға болады. Мысалы, басымдылық кезектері.

Түрлі программалау тілдерінде үйінді сұрыптауды жүзеге асыру

C++ іске асыру

// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i)
{
   // Find largest among root, left child and right child
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if (l < n && arr[l] > arr[largest])
     largest = l;

   if (right < n && arr[r] > arr[largest])
     largest = r;

   // Swap and continue heapifying if root is not largest
   if (largest != i)
   {
     swap(arr[i], arr[largest]);
     heapify(arr, n, largest);
   }
}

// main function to do heap sort
void heapSort(int arr[], int n)
{
   // Build max heap
   for (int i = n / 2 - 1; i >= 0; i--)
     heapify(arr, n, i);

   // Heap sort
   for (int i=n-1; i>=0; i--)
   {
     swap(arr[0], arr[i]);

     // Heapify root element to get highest element at root again
     heapify(arr, i, 0);
   }
}

void printArray(int arr[], int n)
{
   for (int i=0; i<n; ++i)
     cout << arr[i] << " ";
   cout << "\n";
}

int main()
{
   int arr[] = {1,12,9,5,6,10};
   int n = sizeof(arr)/sizeof(arr[0]);
   heapSort(arr, n);

   cout << "Sorted array is \n";
   printArray(arr, n);
}

Java енгізу

// Java program for implementation of Heap Sort
public class HeapSort
{   

    public void sort(int arr[])
    {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
          heapify(arr, n, i);
        }


        // Heap sort
        for (int i=n-1; i>=0; i--)
        {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify root element
            heapify(arr, i, 0);
        }
    }

    void heapify(int arr[], int n, int i)
    {
        // Find largest among root, left child and right child
        int largest = i; 
        int l = 2*i + 1; 
        int r = 2*i + 2;  

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        // Swap and continue heapifying if root is not largest
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i < n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

    public static void main(String args[])
    {
        int arr[] = {1,12,9,5,6,10};

        HeapSort hs = new HeapSort();
        hs.sort(arr);

        System.out.println("Sorted array is");
        printArray(arr);
    }
}

Python енгізу (Python 3)

def heapify(arr, n, i):
    # Find largest among root and children
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2 

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    # If root is not largest, swap with largest and continue heapifying
    if largest != i:
        arr[i],arr[largest] = arr[largest],arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

    # Build max heap
    for i in range(n, 0, -1):
        heapify(arr, n, i)


    for i in range(n-1, 0, -1):
        # swap
        arr[i], arr[0] = arr[0], arr[i]  

        #heapify root element
        heapify(arr, i, 0)


arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
    print ("%d" %arr[i])