Algorytm sortowania sterty (z kodem w Python oraz C++)

Co to jest algorytm sortowania sterty?

Heap Sort to jeden z popularnych i szybszych algorytmów sortowania. Jest zbudowany na kompletnej strukturze danych drzewa binarnego. Poszukamy maksymalnego elementu i umieścimy go na szczycie sterty maksymalnej. Umieścimy go na węźle nadrzędnym drzewa binarnego.

Powiedzmy, że podana jest tablica, dane = [10,5, 7, 9, 4, 11, 45, 17, 60].

W tablicy, jeśli i-ty (i=0,1,2,3 …) indeks jest węzłem nadrzędnym, to (2i+1) i (2i+2) będą lewym i prawym dzieckiem. Tworzenie kompletnego drzewa binarnego za pomocą tej tablicy będzie wyglądać następująco:

Wykonamy proces heapify od początku do końca tablicy. Początkowo, jeśli przekonwertujemy tablicę na drzewo, będzie wyglądać jak powyżej. Możemy zobaczyć, że nie utrzymuje żadnej właściwości heap (min-heap lub max heap). Otrzymamy posortowaną tablicę, wykonując proces heapify dla wszystkich węzłów.

Zastosowanie sortowania stertowego

Oto kilka zastosowań algorytmu sortowania sterty:

• Konstrukcja „kolejek priorytetowych” wymaga sortowania sterty. Ponieważ heapsort utrzymuje element posortowany po każdym wstawieniu.
• Struktura danych sterty jest skuteczna w znajdowaniu k^th największy element w danej tablicy.
• Jądro Linuksa domyślnie używa sortowania przez stertę algorytm sortowania ponieważ ma złożoność przestrzenną O (1).

Utwórz sortowanie sterty na przykładzie

Tutaj utworzymy kopiec maksymalny z następującego kompletnego drzewa binarnego.

Węzły liściowe to 17, 60, 4, 11 i 45. Nie mają żadnych węzłów podrzędnych. Dlatego są węzłami liściowymi. Więc rozpoczniemy metodę heapify od ich węzła nadrzędnego. Oto kroki:

Krok 1) Wybierz poddrzewo znajdujące się najbardziej na lewo. Jeśli węzły podrzędne są większe, zamień węzeł nadrzędny z węzłem podrzędnym.

Tutaj węzeł nadrzędny to 9. Węzły podrzędne to 17 i 60. Ponieważ 60 jest największe, 60 i 9 zostaną zamienione miejscami, aby zachować maksymalna sterta.

Krok 2) Teraz poddrzewo znajdujące się najbardziej po lewej stronie jest stertowane. Następny węzeł nadrzędny to 7. Ten rodzic ma dwa węzły podrzędne, a największy ma 45. Zatem 45 i 7 zostaną zamienione.

Krok 3) Węzły 60 i 4 mają węzeł nadrzędny 5. Ponieważ „5” jest mniejsze niż węzeł podrzędny 60, zostanie ono zamienione.

Krok 4) Teraz węzeł 5 ma węzeł podrzędny 17,9. To nie jest zachowanie właściwości max sterty. Zatem 5 zostanie zastąpione 17.

Krok 5) Węzeł 10 zostanie zamieniony z węzłem 60, a następnie z węzłem 17. Proces będzie wyglądał następująco.

Krok 6) Do kroku 5 utworzyliśmy maksymalną stertę. Każdy węzeł nadrzędny jest większy niż jego węzły podrzędne. Węzeł główny ma maksymalną wartość (60).

Uwaga: Aby utworzyć posortowaną tablicę, musimy zastąpić węzeł o maksymalnej wartości jego następcą.

Ten proces nazywa się „ekstrakt maks”. Ponieważ 60 to maksymalny węzeł, ustalimy jego pozycję na 0-tym indeksie i utworzymy stertę bez węzła 60.

Krok 7) Po usunięciu 60 następna maksymalna wartość wyniesie 45. Ponownie wykonamy proces „Wyodrębnij Max” z węzła 45.

Tym razem otrzymamy 45 i zastąpimy węzeł główny jego następcą 17.

Musimy wykonać „Wyciąg maks”, aż wszystkie elementy zostaną posortowane.

Po wykonaniu tych kroków aż do wyodrębnienia wszystkich wartości maksymalnych otrzymamy następującą tablicę.

Co to jest sterta binarna?

Kopia binarna jest swego rodzaju kompletna drzewo binarne struktura danych. W tego rodzaju strukturze drzewa węzeł nadrzędny jest większy lub mniejszy niż węzły podrzędne. Jeśli węzeł nadrzędny jest mniejszy, wówczas sterta nazywa się „Stertą minimalną”, a jeśli węzeł nadrzędny jest większy, stertę nazywa się „Stertą maksymalną”.

Oto przykłady minimalnej i maksymalnej sterty.

Jeśli na powyższym rysunku zauważysz „Min Heap”, węzeł nadrzędny jest zawsze mniejszy niż jego węzły podrzędne. Na czele drzewa możemy znaleźć najmniejszą wartość 10.

Podobnie w przypadku „Maksymalnej sterty” węzeł nadrzędny jest zawsze większy niż węzły podrzędne. Maksymalny element występuje w węźle głównym „Max Heap”.

Czym jest „Heapify”?

„Heapify” to zasada kopca, która zapewnia pozycję węzła. W Heapify, maksymalny kopiec zawsze utrzymuje relację z rodzicem i dzieckiem, a węzeł rodzica będzie większy niż węzły dzieci.

Na przykład, jeśli dodany zostanie nowy węzeł, musimy zmienić kształt sterty. Jednak możemy potrzebować zmienić lub zamienić węzły lub przearanżować tablicę. Ten proces zmiany kształtu sterty nazywa się „heapify”.

Oto przykład działania heapify:

Oto kroki dla heapify:

Krok 1) Dodano węzeł 65 jako prawy element podrzędny węzła 60.

Krok 2) Sprawdź, czy nowo dodany węzeł jest większy niż rodzic.

Krok 3) Ponieważ jest większy niż węzeł nadrzędny, zamieniliśmy właściwe dziecko z jego rodzicem.

Jak zbudować stertę

Zanim zbudujemy stos lub utworzymy stos drzewa, musimy wiedzieć, jak będziemy go przechowywać. Ponieważ stos jest kompletnym drzewem binarnym, lepiej jest użyć szyk do przechowywania danych sterty.

Załóżmy, że tablica zawiera łącznie n elementów. Jeśli „i” indeks jest węzłem nadrzędnym, wówczas lewy węzeł będzie miał indeks (2i+1), a prawy węzeł będzie w indeksie (2i+2). Zakładamy, że indeks tablicy zaczyna się od 0.

Używając tego, zapiszemy maksymalną ilość stosu w następujący sposób:

Algorytm heapify utrzymuje właściwość heap. Jeśli rodzic nie ma wartości skrajnej (mniejszej lub większej), zostanie zamieniony z najbardziej skrajnym węzłem podrzędnym.

Oto kroki służące do utworzenia kopca maksymalnego:

Krok 1) Zacznij od węzła liścia.

Krok 2) Znajdź maksimum między rodzicem a dziećmi.

Krok 3) Zamień węzły, jeśli węzeł podrzędny ma większą wartość niż węzeł nadrzędny.

Krok 4) Przejdź o jeden poziom wyżej.

Krok 5) Postępuj zgodnie z krokami 2,3,4, aż osiągniemy indeks 0 lub posortuj całe drzewo.

Oto pseudokod dla rekurencyjnego heapify (maksymalny heap):

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)

Pseudokod sortowania sterty

Oto pseudokod algorytmu sortowania sterty:

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)

Przykład kodu sortowania sterty w 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);
}

Wyjście:

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

Przykład kodu sortowania sterty w 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)

Wyjście:

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

Analiza złożoności czasowej i przestrzennej sortowania kopcowego

Istnieje złożoność czasowa i złożoność przestrzenna, które możemy analizować dla sortowania kopcowego. Dla złożoności czasowej mamy następujące przypadki:

1. Najlepsza sprawa
2. Średnia sprawa
3. Najgorszy przypadek

Sterta jest zaimplementowana na kompletnym drzewie binarnym. Zatem na dolnym poziomie drzewa binarnego będzie maksymalna liczba węzłów. Jeśli dolny poziom ma n węzłów, wówczas wyższy poziom będzie miał n/2 węzłów.

W tym przykładzie poziom 3 ma cztery elementy, poziom 2 ma dwa elementy, a poziom 1 ma jeden element. Jeśli istnieje całkowita liczba n elementów, wysokość lub całkowity poziom będzie wynosić Zaloguj₂(N). Zatem wstawienie pojedynczego elementu może wymagać maksymalnie iteracji Log(n).

Gdy chcemy pobrać maksymalną wartość ze sterty, po prostu bierzemy węzeł główny. Następnie ponownie uruchamiamy heapify. Każda heapify pobiera Zaloguj₂(n) czas. Wyodrębnienie maksimum zajmuje czas O(1).

Najlepszy przypadek złożoności czasowej dla algorytmu sortowania kopcowego

Kiedy wszystkie elementy tablicy są już posortowane, zbudowanie sterty zajmie O(n) czasu. Ponieważ jeśli lista jest posortowana, wstawienie elementu zajmie stały czas, czyli O(1).

Zatem w najlepszym przypadku utworzenie maksymalnej lub minimalnej sterty zajmie O(n) czasu.

Średnia złożoność czasowa przypadku dla algorytmu sortowania kopcowego

Wstawienie elementu lub wydobycie maksimum kosztuje O(log(n)) czasu. Zatem średnia złożoność czasowa przypadku dla algorytmu sortowania kopcowego wynosi O(n log(n)).

Najgorszy przypadek złożoności czasowej dla algorytmu sortowania kopcowego

Podobnie jak w przypadku przeciętnym, w najgorszym scenariuszu moglibyśmy wykonać heapify n razy. Każde heapify będzie kosztować O(log(n)) czasu. Tak więc złożoność czasowa w najgorszym przypadku będzie wynosić O(n log(n)).

Złożoność przestrzenna dla algorytmu sortowania kopcowego

Sortowanie kopcowe to algorytm zaprojektowany w miejscu. Oznacza to, że do wykonania zadania nie jest potrzebna żadna dodatkowa ani tymczasowa pamięć. Jeśli przyjrzymy się implementacji, zauważymy, że użyliśmy swap() do wykonania wymiany węzłów. Nie była potrzebna żadna inna lista ani tablica. Zatem złożoność przestrzenna wynosi O(1).