Алгоритъм за сортиране на купчина (с код в Python намлява C++)

Какво представлява алгоритъмът за сортиране на купчина?

Heap Sort е един от популярните и по-бързи алгоритми за сортиране. Той е изграден върху пълната двоична дървовидна структура от данни. Ще търсим максималния елемент и ще го поставим на върха за максималния куп. Ще го поставим на родителския възел на двоичното дърво.

Да кажем, че е даден масив, данни = [10,5, 7, 9, 4, 11, 45, 17, 60].

В масива, ако i-тият (i=0,1,2,3 …) индекс е родителски възел, тогава (2i+1) и (2i+2) ще бъдат левите и десните деца. Създаването на пълно двоично дърво с този масив ще изглежда така:

Ще извършим процеса на heapify от началото до края на масива. Първоначално, ако преобразуваме масива в дърво, той ще изглежда като горния. Можем да видим, че не поддържа никакво свойство на купчината (мин. купчина или максимална купчина). Ще получим сортирания масив, като извършим процеса на heapify за всички възли.

Приложение на Heap Sort

Ето малко използване на алгоритъма за сортиране на купчината:

Изграждането на „Приоритетни опашки“ изисква сортиране в купчина. Тъй като heapsort поддържа елемента сортиран след всяко вмъкване.
Heap Data Structure е ефективна при намирането на k^th най-големият елемент в даден масив.
Ядрото на Linux използва сортирането на купчина по подразбиране алгоритъм за сортиране тъй като има O (1) пространствена сложност.

Създаване на Heap сортиране с пример

Тук ще конструираме максимална купчина от следното пълно двоично дърво.

Листовите възли са 17, 60, 4, 11 и 45. Те нямат дъщерни възли. Ето защо те са листни възли. И така, ще стартираме метода heapify от техния родителски възел. Ето стъпките:

Стъпка 1) Изберете най-лявото поддърво. Ако дъщерните възли са по-големи, разменете родителския възел с дъщерния възел.

Тук родителският възел е 9. А дъщерните възли са 17 и 60. Тъй като 60 е най-големият, 60 и 9 ще бъдат разменени, за да се поддържа макс. купчина.

Стъпка 2) Сега най-лявото поддърво е натрупано. Следващият родителски възел е 7. Този родител има два дъщерни възела, а най-големият е 45. Така че 45 и 7 ще бъдат разменени.

Стъпка 3) Възлите 60 и 4 имат родителския възел 5. Тъй като „5“ е по-малък от дъщерния възел 60, той ще бъде разменен.

Стъпка 4) Сега възел 5 има дъщерния възел 17,9. Това не е поддържане на свойството за максимална купчина. Така че 5 ще бъде заменено със 17.

Стъпка 5) Възел 10 ще бъде разменен с 60, след това с 17. Процесът ще изглежда по следния начин.

Стъпка 6) До стъпка 5 създадохме максималната купчина. Всеки родителски възел е по-голям от неговите дъщерни възли. Основният възел има максималната стойност (60).

Забележка: За да създадем сортирания масив, трябва да заменим възела с максимална стойност с неговия наследник.

Този процес се нарича „екстракт макс”. Тъй като 60 е максималният възел, ние ще фиксираме позицията му към 0-ия индекс и ще създадем купчината без възел 60.

Стъпка 7) Тъй като 60 е премахнато, следващата максимална стойност е 45. Ще извършим процеса „Извличане на Макс“ отново от възел 45.

Този път ще получим 45 и ще заменим основния възел с неговия наследник 17.

Трябва да изпълним "Екстракт Макс”, докато всички елементи бъдат сортирани.

След като изпълним тези стъпки, докато извлечем всички максимални стойности, ще получим следния масив.

Какво е Binary Heap?

Двоичната купчина е един вид пълна двоично дърво структура на данните. В този вид дървовидна структура родителският възел е или по-голям, или по-малък от дъщерните възли. Ако родителският възел е по-малък, тогава купчината се нарича „Минимална купчина“, а ако родителският възел е по-голям, купчината се нарича „Максимална купчина“.

Ето примери за min heap и max heap.

На фигурата по-горе, ако забележите „Минимална купчина“, родителският възел винаги е по-малък от неговите дъщерни възли. В началото на дървото можем да намерим най-малката стойност 10.

По същия начин, за „Max Heap“ родителският възел винаги е по-голям от дъщерните възли. Максималният елемент присъства в главния възел за „Максимална купчина“.

Какво е „Heapify“?

„Heapify“ е принципът на купчината, който осигурява позицията на възела. В Heapify максималната купчина винаги поддържа връзка с родител и дете и това е, че родителският възел ще бъде по-голям от дъщерните възли.

Например, ако се добави нов възел, трябва да променим формата на купчината. Въпреки това може да се наложи да променим или разменим възлите или да пренаредим масива. Този процес на преоформяне на купчина се нарича „heapify“.

Ето пример за това как работи heapify:

Добавяне на нов възел и Heapify — Добавяне на нов възел и heapify

Ето стъпките за heapify:

Стъпка 1) Добавен е възел 65 като дясно дете на възел 60.

Стъпка 2) Проверете дали новодобавеният възел е по-голям от родителския.

Стъпка 3) Тъй като е по-голям от родителския възел, сменихме дясното дете с неговия родител.

Как да изградим Купчината

Преди да изградим купчината или да натрупаме дърво, трябва да знаем как ще го съхраняваме. Тъй като купчината е цялостно двоично дърво, по-добре е да използвате an масив за съхранение на данните от купчината.

Да кажем, че един масив съдържа общо n елемента. Ако “i”-ият индекс е родителски възел, тогава левият възел ще бъде в индекса (2i+1), а десният възел ще бъде на индекс (2i+2). Приемаме, че индексът на масива започва от 0.

Използвайки това, нека съхраним максимален обем в подобен на масив след:

Базирано на масив представяне на максималната купчина

Алгоритъмът за heapify поддържа свойството heap. Ако родителят няма екстремната стойност (по-малка или по-голяма), той ще бъде разменен с най-крайния дъщерен възел.

Ето стъпките за натрупване на максимална купчина:

Стъпка 1) Започнете от листовия възел.

Стъпка 2) Намерете максимума между родител и деца.

Стъпка 3) Разменете възлите, ако дъщерният възел има по-голяма стойност от родителския.

Стъпка 4) Отидете едно ниво нагоре.

Стъпка 5) Следвайте стъпки 2,3,4, докато достигнем индекс 0 или сортираме цялото дърво.

Ето псевдокода за рекурсивна heapify (максимална купчина):

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

Псевдо код за Heap сортиране

Ето псевдокода за алгоритъма за сортиране на купчина:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

Пример за код за сортиране на Heap в C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

Изход:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

Пример за код за сортиране на Heap в Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

Изход:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

Времеви и пространствен анализ на сложността на Heap Sort

Има времева сложност и пространствена сложност, които можем да анализираме за груповото сортиране. За времева сложност имаме следните случаи:

Най -добрият случай
Среден случай
Най-лошия случай

Купчината е имплементирана върху цялостно двоично дърво. Така че на най-долното ниво на двоичното дърво ще има максимален брой възли. Ако долното ниво има n възли, тогава горното ниво ще има n/2 възела.

В този пример ниво 3 има четири елемента, ниво 2 има два елемента, а ниво 1 има един елемент. Ако има общо n на брой елементи, ще бъде височината или общото ниво Вход₂(н). Така че вмъкването на един елемент може да отнеме максимум Log(n) итерации.

Когато искаме да вземем максималната стойност от купчината, ние просто вземаме основния възел. След това отново стартирайте heapify. Всеки heapify взема Вход₂(П) време. Извличането на максимума отнема O(1) време.

Най-добър случай на времева сложност за алгоритъм за сортиране на купчина

Когато всички елементи вече са сортирани в масива, изграждането на купчината ще отнеме O(n) време. Защото, ако списъкът е сортиран, тогава вмъкването на елемент ще отнеме постоянното време, което е O(1).

Така че ще отнеме O(n) време за създаване на max-heap или min-heap в най-добрия случай.

Средна времева сложност на случая за алгоритъм за сортиране на купчина

Вмъкването на елемент или извличането на максимум струва O(log(n)) време. И така, средната времева сложност на случая за алгоритъма за сортиране на купчина е O(n log(n)).

Времева сложност в най-лошия случай за алгоритъм за сортиране на купчина

Подобно на средния случай, в най-лошия сценарий можем да извършим heapify n пъти. Всяко heapify ще струва O(log(n)) време. Така че в най-лошия случай времевата сложност ще бъде O(n log(n)).

Пространствена сложност за алгоритъм за сортиране на купчина

Heap sort е алгоритъм, проектиран на място. Това означава, че не е необходима допълнителна или временна памет за изпълнение на задачата. Ако видим изпълнението, ще забележим, че сме използвали swap (), за да извършим обмена на възлите. Не беше необходим друг списък или масив. И така, пространствената сложност е O(1).