Złożoność czasu

Kabel, napisany jako sterta, jest rodzajem algorytmu sortowania. Obejmuje listę, która jest częściowo zamówiona i tworzy z niej posortowaną listę. Sortowanie może być rosnące lub zstępujące. W tym artykule sortowanie jest rosnące. Należy zauważyć, że Heapsort nie sortują niekompletnie nieporozumienia. Sortuje listę częściowo uporządkowaną (posortowaną). Ta częściowo uporządkowana lista to sterta. W tym artykule rozważana sterta to minimalna (rosnąca) sterta.

Sterta nazywana jest „częściowo zamówioną”, a nie „częściowo sortowaną”. Słowo „sortowanie” oznacza pełne zamówienie (pełne sortowanie). Sterta nie jest częściowo uporządkowana arbitralnie. Sterta jest częściowo uporządkowana po kryterium (wzorze), jak pokazano poniżej.

Tak więc Heapsort składa się z dwóch etapów: budowania sterty i wydobywania uporządkowanego elementu z góry sterty. W drugim etapie, po każdej ekstrakcji, sterta jest odbudowana. Każda przebudowa jest szybsza niż oryginalny proces budowy, ponieważ odbudowa odbywa się z poprzedniej wersji, w której jeden element został usunięty. A dzięki temu Heapsort sortuje całkowicie nieporządkowaną listę.

Celem tego artykułu jest krótkie wyjaśnienie heapsort, a następnie wytworzenie jego złożoności czasowej (patrz znaczenie złożoności czasu poniżej). Pod koniec kodowanie odbywa się w C++.

Minimalna stos

Sterta może być minimalną stertą lub maksymalną stertą. Max-heap to taki, w którym pierwszy element jest najwyższym elementem, a całe drzewo lub odpowiednia lista jest częściowo uporządkowana w kolejności malejącej. Min-heap to taki, w którym pierwszy element jest najmniejszym elementem, a cała lista jest częściowo uporządkowana w kolejności rosnącej. W tym artykule rozważany jest tylko minimalna stos. UWAGA: W temacie sterty element nazywa się również węzłem.

Kabel to kompletne drzewo binarne. Drzewo binarne można wyrazić jako tablicę (listę); Przeczytaj od góry do dołu i od lewej do prawej. Właściwość sterty dla minimalnej grupy jest to, że węzeł nadrzędny jest mniejszy lub równy każdemu z dwojga dzieci. Przykładem nieuporządkowanej listy jest:

9	19	24	5	3	11	14	22	7	6	17	15	zero	zero	zero
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14

Pierwszy rząd tej tabeli to elementy tablicy. W drugim rzędzie znajdują się indeksy oparte na zerowej. Ta lista elementów można wyrazić jako drzewo. Dodano zerowe elementy, aby stworzyć pełne drzewo binarne. Ściśle mówiąc, zerowe elementy nie są częścią listy (drzewo). Ta lista nie ma kolejności, więc nie jest to jeszcze kupa. Stanie się kupą, gdy będzie miał częściowe zamówienie, zgodnie z właściwością sterty.

Związek między węzłami i indeksami

Pamiętaj, że sterta jest kompletnym drzewem binarnym przed konfiguracją sterty (właściwość sterta). Poprzednia lista nie jest jeszcze stertą, ponieważ elementy nie są przestrzegane właściwością sterty. Staje się kupą po zmianie elementów w częściową kolejność zgodnie z właściwością min-heap. Częściowe zamówienie można postrzegać jako częściowy (chociaż słowo „sortowanie” oznacza pełne zamawianie).

Niezależnie od tego, czy drzewo binarne jest kupą, czy nie, każdy rodzic ma dwoje dzieci, z wyjątkiem węzłów liściowych (ostatnich). Istnieje związek matematyczny między indeksami między każdym rodzicem a jego dziećmi. Jest to następujące: jeśli rodzic znajduje się w indeksie I, lewe dziecko jest na indeksie:

2*i + 1

a właściwe dziecko jest na indeksie:

2*i + 2

To dotyczy indeksowania opartego na zero. I tak, rodzic w indeksie 0 ma lewe dziecko w indeksie 2 × 0+1 = 1 i jego prawe dziecko przy 2 × 0+2 = 2. Rodzic w indeksie 1 ma swoje lewe dziecko w indeksie 2 × 1+1 = 3 i prawe dziecko przy indeksie 2 × 1+2 = 4; i tak dalej.

Według właściwości min-heap rodzic w i jest mniejszy lub równy lewemu dziecku przy 2i+1 i mniejszy lub równy prawego dziecka przy 2i+2.

Sterta

Awatowanie oznacza budowę sterty. Oznacza to zmianę elementów listy (lub odpowiedniego drzewa), aby zaspokoić właściwość sterty. Na końcu procesu awaryjnego lista lub drzewo to sterta.

Jeśli poprzednia lista nieposortowana jest rozważana, stanie się:

3	5	11	7	6	15	14	22	9	19	17	24	zero	zero	zero
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14

Uwaga: na liście jest 12 elementów, a nie 15. W drugim rzędzie znajdują się indeksy. W procesie budowania sterty elementy musiały zostać sprawdzone, a niektóre zamienione.

Zauważ, że najmniejszy i pierwszy element to 3. Reszta elementów podąża w sposób rosnący. Jeśli lewe i prawe dzieci w pozycjach 2i+1 i 2i+2 są większe lub równe rodzica w i, to jest to minime-heap. To nie jest pełne zamówienie lub sortowanie. Jest to częściowe zamówienie, zgodnie z właściwością stertu. Stąd zaczyna się następny etap dla heap.

Rozprzyjaj złożoność czasu

Złożoność czasu to względny czas działania jakiegoś kodu. Można to postrzegać jako liczbę głównych operacji dla tego kodu do ukończenia. Istnieją różne algorytmy do budowania sterty. Najbardziej wydajne i najszybciej stale dzielą listę przez dwa, sprawdzając elementy od dołu, a następnie zamienianie elementów. Niech N będzie liczbą praktycznych elementów na liście. Z tym algorytmem maksymalna liczba głównych operacji (zamiana) wynosi n. Złożoność czasowa dla analizy jest dawniej podana jako:

NA)

Gdzie n jest n i jest maksymalną możliwą liczbą głównych operacji. Ta notacja nazywa się notacją Big-O. Zaczyna się od O Upperceerase, a następnie nawiasów. Wewnątrz nawiasów znajduje się wyrażenie dla możliwej największej liczby operacji.

Pamiętaj: dodanie może stać się mnożeniem, jeśli dodanie tego samego powtarza się.

Ilustracja stertu

Poprzednia lista nieposortowana zostanie użyta do zilustrowania humowania. Podana lista to:

9 19 24 5 3 11 14 22 7 6 17 15

Min-heap wyprodukowana z listy to:

3 5 11 7 6 15 14 22 9 19 17 24 24

Pierwszym etapem w Heapsort jest wyprodukowanie stosu, który został wyprodukowany. To jest częściowo uporządkowana lista. To nie jest posortowana (całkowicie posortowana) lista.

Drugi etap polega na usunięciu najmniejszego elementu, który jest pierwszym elementem, z sterty, ponowne heapifikowanie pozostałej sterty i usuwanie najmniejszych elementów w wynikach. Najmniejszy element jest zawsze pierwszym elementem w ponownej hotelu. Elementy nie są usuwane i wyrzucane. Można je wysłać do innej tablicy w kolejności, w jakiej są usuwane.

Ostatecznie nowa tablica miałaby wszystkie elementy (całkowicie), w kolejności rosnącej; i nie po prostu częściowo zamówiłem.

W drugim etapie pierwszą rzeczą do usunięcia 3 i umieszczenie go w nowej tablicy. Wyniki są:

3

I

5 11 7 6 15 14 22 9 19 17 24 24

Pozostałe elementy muszą być rozważane przed wyodrębnieniem pierwszego elementu. Kabła pozostałych elementów może stać się:

5 6 7 9 15 14 22 11 19 17 24

Wyodrębnienie 5 i dodanie do nowej listy (tablica) daje wyniki:

3 5

I

6 7 9 15 14 22 11 19 17 24

Dało by rozlanie pozostałego zestawu:

6 7 9 15 14 22 11 19 17 24

Wyodrębnienie 6 i dodanie do nowej listy (tablica) daje wyniki:

3 5 6

I

7 9 15 14 22 11 19 17 24

Dało by rozlanie pozostałego zestawu:

7 9 11 14 22 15 19 17 24

Wyodrębnienie 7 i dodanie go do nowej listy daje wyniki:

3 5 6 7

I

9 11 14 22 15 19 17 24

Rozprowadzanie pozostałego zestawu daje:

9 11 14 22 15 19 17 24

Wyodrębnienie 9 i dodanie do nowej listy daje wyniki:

3 5 6 7 9

I

11 14 22 15 19 17 24

Rozprowadzanie pozostałego zestawu daje:

11 14 17 15 19 22 24

Wyodrębnienie 11 i dodanie go do nowej listy daje wyniki:

3 5 6 7 9 11

I

14 17 15 19 22 24

Dało by rozlanie pozostałego zestawu:

14 17 15 19 22 24

Wyodrębnienie 14 i dodanie go do nowej listy daje wyniki:

3 5 6 7 9 11 14

I

17 15 19 22 24

Dało by rozlanie pozostałego zestawu:

15 17 19 22 24

Wyodrębnienie 15 i dodanie go do nowej listy daje wyniki:

3 5 6 7 9 11 14 15

I

17 19 22 24

Dało by rozlanie pozostałego zestawu:

17 19 22 24

Wyodrębnienie 17 i dodanie go do nowej listy daje wyniki:

3 5 6 7 9 11 14 15 17

I

19 22 24

Dało by rozlanie pozostałego zestawu:

19 22 24

Wyodrębnienie 19 i dodanie go do nowej listy daje wyniki:

3 5 6 7 9 11 14 15 17 19

I

22 24

Rozprowadzanie pozostałego zestawu daje:

22 24

Wyodrębnienie 22 i dodanie go do nowej listy daje wyniki:

3 5 6 7 9 11 14 15 17 19 22 22

I

24

Rozprowadzanie pozostałego zestawu daje:

24

Wyodrębnienie 24 i dodanie go do nowej listy daje wyniki:

3 5 6 7 9 11 14 15 17 19 22 24 24

I

- - -

Tablica sterty jest teraz pusta. Wszystkie elementy, które miał na początku, są teraz w nowej tablicy (lista) i posortowane.

Algorytm steru

Chociaż czytelnik mógł przeczytać w podręcznikach, które składa się z dwóch etapów, Heapsort może być nadal postrzegany jako składający się z jednego etapu, który iteracyjnie zmniejsza daną tablicę. Dzięki temu algorytm do sortowania z Heapsort jest następujący:

• Uprzyj listę nieporządkową.
• Wyodrębnij pierwszy element sterty i umieść go jako pierwszy element nowej listy.
• Uprzyj pozostałą listę.
• Wyodrębnij pierwszy element nowej sterty i umieść jako następny element nowej listy.
• Powtórz poprzednie kroki, aż lista sterty będzie pusta. W końcu nowa lista jest sortowana.

Złożoność czasu haupsorta właściwa

Jednostopniowe podejście jest stosowane w celu ustalenia złożoności czasowej dla heapsort. Załóżmy, że do sortowania jest 8 niepotrzebnych elementów.

Możliwa maksymalna liczba operacji w celu rozliczenia 8 elementów wynosi 8.
Możliwa maksymalna liczba operacji w celu rozliczenia pozostałych 7 elementów wynosi 7.
Możliwa maksymalna liczba operacji w celu rozliczenia pozostałych 6 elementów wynosi 6.
Możliwa maksymalna liczba operacji w celu rozliczenia pozostałych 5 elementów wynosi 5.
Możliwa maksymalna liczba operacji w celu rozliczenia pozostałych 4 elementów wynosi 4.
Możliwa maksymalna liczba operacji w celu rozliczenia pozostałych 3 elementów wynosi 3.
Możliwa maksymalna liczba operacji w celu rozliczenia pozostałych 2 elementów wynosi 2.
Możliwa maksymalna liczba operacji w celu rozliczenia pozostałego 1 elementu wynosi 1.

Możliwa maksymalna liczba operacji to:

8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36

Średnia z tych liczby operacji to:

36 /8 = 4.5

Zauważ, że ostatnie cztery stosy w poprzedniej ilustracji nie zmieniły się, gdy pierwszy element został usunięty. Niektóre z poprzednich stosów nie zmieniły się również po usunięciu pierwszego elementu. Dzięki temu lepsza średnia liczba głównych operacji (wymiany) wynosi 3, a nie 4.5. Tak więc lepsza całkowita średnia liczba głównych operacji to:

24 = 8 x 3
=> 24 = 8 x dziennik₂8

Od dziennika₂8 = 3.

Ogólnie rzecz biorąc, średnia złożoność czasu dla Heapsort wynosi:

NA.log2n)

Gdzie kropka oznacza mnożenie, a n wynosi n, całkowita liczba elementów na liście (lista).

Zauważ, że działanie wyodrębnienia pierwszego elementu zostało zignorowane. Jeśli chodzi o złożoność czasu, operacje, które trwają stosunkowo krótkie czasy, są ignorowane.

Kodowanie w c++

W bibliotece algorytmu C ++ istnieje funkcja Make_Heap (). Składnia to:

szablon
constexpr void Make_Heap (najpierw RandomAccessiterator, RandomAccessiterator Last, Porównaj Comp);

Przyjmuje iterator wskazujący na pierwszy element wektora jako jego pierwszy argument, a następnie iterator wskazujący tuż za koniec wektora jako jego ostatni argument. W przypadku poprzedniej listy Unsorted składnia zostanie zastosowana w następujący sposób, aby uzyskać minimalną stert:

wektor vtr = 9, 19, 24, 5, 3, 11, 14, 22, 7, 6, 17, 15;
wektor:: iterator iterB = vtr.zaczynać();
wektor:: iterator itere = vtr.koniec();
Make_Heap (iterb, itere, większy());

Ten kod zmienia zawartość wektora na minimalną konfigurację sterty. W następujących wektorach C ++ zamiast dwóch tablic będą używane dwa wektory.

Aby skopiować i zwrócić pierwszy element wektora, użyj składni wektorowej:

Constexpr Reference Front ();

Aby usunąć pierwszy element wektora i wyrzucić go, użyj składni wektorowej:

Constexpr Iterator Erase (pozycja Const_iterator)

Aby dodać element z tyłu wektora (następny element), użyj składni wektorowej:

constexpr void push_back (const t & x);

Początek programu to:

#włączać
#włączać
#włączać
za pomocą przestrzeni nazw Std;

Uwzględniono algorytm i biblioteki wektorowe. Następnie w programie jest funkcja heapsort (), która jest:

Nieważny heapsort (wektor & Oldv, wektor & Newv)
if (Oldv.size ()> 0)
wektor:: iterator iterB = oldv.zaczynać();
wektor:: iterator itere = oldv.koniec();
Make_Heap (iterb, itere, większy());
int następny = Oldv.przód();
Oldv.usunąć (iterB);
Newv.push_back (następny);
Shepsort (Oldv, Newv);

Jest to funkcja rekurencyjna. Używa funkcji biblioteki algorytmu C ++ C ++. Drugi segment kodu w definicji funkcji wyodrębnia pierwszy element ze starego wektora po budowie sterty i dodaje jako następny element nowego wektora. Zauważ, że w definicji funkcji parametry wektorowe są odniesieniami, podczas gdy funkcja jest wywoływana z identyfikatorami (nazw).

Odpowiednią główną funkcją C ++ jest:

int main (int argc, char ** argv)

wektor Oldv = 9, 19, 24, 5, 3, 11, 14, 22, 7, 6, 17, 15;
wektor Newv;
Shepsort (Oldv, Newv);
dla (int i = 0; iCout << newV[i] << ";

Cout << endl;
powrót 0;

Wyjście to:

3 5 6 7 9 11 14 15 17 19 22 24 24

posortowane (całkowicie).

Wniosek

Artykuł omówiono szczegółowo charakter i funkcja sterty powszechnie znana jako sterta, jako algorytm sortowania. Rozpowszechnianie złożoności czasu, ilustracji i heapsort jako algorytmu zostały omówione i poparte przykładami. Średnia złożoność czasowa dla dobrze napisanego programu sterowania to O (NLOG (N))