Lila25mila
Lila25mila01 березня 2019 р. 03:55

Алгоритм сортування купою

Сортування купою – популярний та ефективний алгоритм сортування у комп'ютерному програмуванні. Щоб навчитися писати алгоритм сортування купою, потрібне знання двох типів структур даних – масивів та дерев.


Наприклад, початковий набір чисел, які хочемо відсортувати, зберігається у масиві [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 для кореневого елемента, поки він не стане більше, ніж його дочірні елементи, або він не стане листовим вузлом.

Ми можемо об'єднати обидві ці умови в одну функцію 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);

Як показано на діаграмі вище, ми починаємо з купи найменших дерев і поступово просуваємося вгору, поки не досягнемо кореневого елемента.

Процедури для Heapsort
  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).

Як ми бачили раніше, щоб повністю накопичувати елемент, чиї піддерев'я вже є убывающими купами, нам потрібно продовжувати порівнювати елемент з його лівим і правим нащадками і штовхати його вниз, поки він не досягне точки, де обидва його нащадки менші за нього.

У гіршому випадку нам потрібно буде перемістити елемент з кореневого вузла в кінцевий вузол, виконавши кілька порівнянь та обмінів log(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)). Швидке сортування має складність O (n^2) для найгіршого випадку. Але в інших випадках швидке сортування виконується досить швидко. Introsort - це альтернатива heapsort, яка поєднує в собі quicksort і heapsort для збереження переваг, таких як швидкість heapsort у гіршому випадку та середня швидкість quicksort.

Застосування сортування купою

Системи, пов'язані з безпекою, та вбудовані системи, такі як ядро ​​Linux, використовують сортування купою через верхню межу O (n log n) часу роботи Heapsort та постійну верхню межу O (1) його допоміжного сховища.

Хоча сортування купою має 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])
Рекомендуємо хостинг TIMEWEB
Рекомендуємо хостинг TIMEWEB
Стабільний хостинг, на якому розміщується соціальна мережа EVILEG. Для проектів на Django радимо VDS хостинг.

Вам це подобається? Поділіться в соціальних мережах!

Коментарі

Only authorized users can post comments.
Please, Log in or Sign up
AD

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:50бали,
  • Рейтинг балів-4
m
  • molni99
  • 26 жовтня 2024 р. 01:37

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:80бали,
  • Рейтинг балів4
m
  • molni99
  • 26 жовтня 2024 р. 01:29

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:20бали,
  • Рейтинг балів-10
Останні коментарі
ИМ
Игорь Максимов22 листопада 2024 р. 11:51
Django - Підручник 017. Налаштуйте сторінку входу до Django Добрый вечер Евгений! Я сделал себе авторизацию аналогичную вашей, все работает, кроме возврата к предидущей странице. Редеректит всегда на главную, хотя в логах сервера вижу запросы на правильн…
Evgenii Legotckoi
Evgenii Legotckoi31 жовтня 2024 р. 14:37
Django - Урок 064. Як написати розширення для Python Markdown Добрый день. Да, можно. Либо через такие же плагины, либо с постобработкой через python библиотеку Beautiful Soup
A
ALO1ZE19 жовтня 2024 р. 08:19
Читалка файлів fb3 на Qt Creator Подскажите как это запустить? Я не шарю в программировании и кодинге. Скачал и установаил Qt, но куча ошибок выдается и не запустить. А очень надо fb3 переконвертировать в html
ИМ
Игорь Максимов05 жовтня 2024 р. 07:51
Django - Урок 064. Як написати розширення для Python Markdown Приветствую Евгений! У меня вопрос. Можно ли вставлять свои классы в разметку редактора markdown? Допустим имея стандартную разметку: <ul> <li></li> <li></l…
d
dblas505 липня 2024 р. 11:02
QML - Урок 016. База даних SQLite та робота з нею в QML Qt Здравствуйте, возникает такая проблема (я новичок): ApplicationWindow неизвестный элемент. (М300) для TextField и Button аналогично. Могу предположить, что из-за более новой верси…
Тепер обговоріть на форумі
Evgenii Legotckoi
Evgenii Legotckoi24 червня 2024 р. 15:11
добавить qlineseries в функции Я тут. Работы оень много. Отправил его в бан.
t
tonypeachey115 листопада 2024 р. 06:04
google domain [url=https://google.com/]domain[/url] domain [http://www.example.com link title]
NSProject
NSProject04 червня 2022 р. 03:49
Всё ещё разбираюсь с кешем. В следствии прочтения данной статьи. Я принял для себя решение сделать кеширование свойств менеджера модели LikeDislike. И так как установка evileg_core для меня не была возможна, ибо он писался…
9
9Anonim25 жовтня 2024 р. 09:10
Машина тьюринга // Начальное состояние 0 0, ,<,1 // Переход в состояние 1 при пустом символе 0,0,>,0 // Остаемся в состоянии 0, двигаясь вправо при встрече 0 0,1,>…

Слідкуйте за нами в соціальних мережах