Struktura danych sterty: Czym jest sterta?

Czym jest struktura danych Heap?

Kopiec to specjalistyczna struktura danych oparta na drzewie. Struktura danych kopca składa się z najwyższego węzła zwanego korzeniem (rodzicem). Drugi węzeł jest lewym dzieckiem korzenia, a trzeci – prawym dzieckiem korzenia. Kolejne węzły są wypełniane od lewej do prawej. Klucz węzła nadrzędnego jest porównywany z kluczem węzła potomnego, co zapewnia właściwe uporządkowanie. Drzewo jest łatwe do zwizualizowania, gdzie każdy element nazywany jest węzłem, a każdy węzeł ma unikalny klucz do identyfikacji.

Mówiąc najprościej, kopiec to kompletne drzewo binarne spełniające właściwości kopca: każdy element nadrzędny jest uporządkowany spójnie względem swoich elementów potomnych, co czyni je idealnym rozwiązaniem dla kolejek priorytetowych i sortowania kopcowego.

Dlaczego potrzebujesz struktury danych sterty?

Oto główne powody używania sterty:

• Struktura danych Heap umożliwia usuwanie i wstawianie w czasie logarytmicznym – O(log₂N).
• Dane w drzewie są uporządkowane w określonej kolejności. Oprócz aktualizowania lub wyszukiwania wartości, takich jak maksimum lub minimum, programista może znaleźć relacje między elementem nadrzędnym a potomnym.
• Można zastosować koncepcję Dokumentowy model obiektowy aby pomóc Ci zrozumieć strukturę danych Heap wizualnie.
• Stosy obsługują wydajne operacje kolejek priorytetowych, które są krytyczne dla algorytmów grafowych, takich jak najkrótsza ścieżka Dijkstry i minimalne drzewo rozpinające Prima.

Rodzaje stosów

Struktura danych kopca ma różne algorytmy do obsługi wstawiania i usuwania elementów, w tym kolejkę priorytetową, kopiec binarny, kopiec dwumianowy i Sortowanie na stosie.

• Kolejka priorytetowa: To jest brzuchtracStruktura danych zawierająca obiekty o określonym priorytecie. Każdy obiekt lub element ma ustalony priorytet. W związku z tym obiekt lub element o wyższym priorytecie jest obsługiwany przed pozostałymi.
• Stos binarny: Stosy binarne nadają się do prostych operacji na stosie, takich jak usuwanie i wstawianie. Stanowią domyślną implementację większości kolejek priorytetowych bibliotek standardowych.
• Kopiec dwumianowy: Kopiec dwumianowy składa się z serii zbiorów drzew dwumianowych, które tworzą kopiec. Drzewo kopca dwumianowego nie jest zwykłym drzewem, ponieważ jest ściśle zdefiniowane. Całkowita liczba elementów w drzewie dwumianowym zawsze wynosi 2.ⁿ węzły
• Sortowanie kopcowe: W przeciwieństwie do większości algorytmów sortowania, sortowanie kopcowe wykorzystuje przestrzeń O(1) do operacji sortowania. Jest to algorytm sortowania oparty na porównaniach, w którym sortowanie odbywa się w kolejności rosnącej, najpierw przekształcając dane wejściowe do kopca Max-Heap. Sortowanie kopcowe można traktować jako ulepszone drzewo poszukiwań binarnych.

Zazwyczaj struktura danych kopca wykorzystuje dwie strategie. Dla danych wejściowych 12 – 8 – 4 – 2 i 1:

• Min-Heap – najmniejsza wartość na górze
• Max-Heap – najwyższa wartość na górze

Min-Heap

W strukturze Min-Heap węzeł główny ma wartość równą lub mniejszą od wartości potomnych tego węzła. Zatem korzeń Min-Heap zawiera wartość minimalną. Min-Heap jest również kompletnym drzewem binarnym.

Gdy w drzewie znajduje się Min-Heap, wszystkie liście są potencjalnymi kandydatami na wartość maksymalną. Należy jednak zbadać każdy liść, aby uzyskać dokładną wartość Max-Heap.

Przykład kopca minimalnego

Na powyższym diagramie można zauważyć wyraźną sekwencję od korzenia do najniższego węzła.

Załóżmy, że przechowujesz elementy w tablicy Array_N[12, 2, 8, 1, 4]. Jak widać z tablicy, element główny narusza priorytet Min-Heap. Aby zachować właściwość Min-Heap, należy wykonać operacje min-heapify, aby zamienić elementy, aż do spełnienia reguł Min-Heap.

Max-Heap

W strukturze Max-Heap węzeł nadrzędny lub główny ma wartość równą lub większą od swoich potomków. Ten węzeł przechowuje wartość maksymalną. Jest to kompletne drzewo binarne, więc można zbudować Max-Heap ze zbioru wartości w czasie O(n).

Oto kilka metod powszechnie stosowanych podczas wdrażania Java Maksymalna sterta:

• Dodać (): Umieszcza nowy element w stercie. W przypadku tablicy obiekty są dodawane na końcu tablicy, natomiast w drzewie binarnym obiekty są dodawane od góry do dołu, a następnie od lewej do prawej.
• Usunąć (): Ta metoda pozwala usunąć pierwszy element z listy tablicowej. Ponieważ nowo promowany element nie jest już największy, metoda Sift-Down zawsze umieszcza go w nowej lokalizacji.
• Sift-Down (): Ta metoda porównuje obiekt główny z jego elementami podrzędnymi, a następnie umieszcza przeniesiony węzeł na jego właściwą pozycję.
• Sift-Up (): Jeśli użyjesz metody array do dodania nowo wstawionego elementu do tablicy, metoda Sift-Up pomoże nowo dodanemu węzłowi przenieść się na właściwe miejsce. Nowy element jest najpierw porównywany z elementem nadrzędnym poprzez symulację struktury danych drzewa.

  Zastosuj formułę Parent_Index = Child_Index / 2. Powtarzaj tę czynność, aż maksymalny element znajdzie się na początku tablicy.

Podstawowy stos Operanych

Aby znaleźć najwyższe i najniższe wartości w zbiorze danych, potrzebujesz kilku podstawowych operacji na stercie, takich jak wyszukiwanie, wstawianie i usuwanie. Ponieważ elementy stale się pojawiają i znikają, powinieneś wiedzieć, jak:

• Znajdź – Poszukaj przedmiotu na stosie.
• wstawka – Dodaj nowe dziecko do sterty.
• Usunięcia – Usuń węzeł ze sterty.

Twórz stosy

Proces konstruowania stosów nazywa się tworzeniem stosów. Mając listę kluczy, programista tworzy pusty stos, a następnie wstawia pozostałe klucze jeden po drugim, korzystając z podstawowych operacji na stosie.

Zacznijmy więc budować kopiec minimalny, stosując metodę Williama, wstawiając wartości 12, 2, 8, 1 i 4. Kopiec można zbudować z n elementów, zaczynając od pustego kopca, a następnie wypełniając go kolejno innymi elementami, korzystając z czasu O(n log n).

• Heapify: Procedura wstawiania, która pomaga wstawiać elementy do sterty, zachowując jednocześnie jej właściwości.

  Na przykład operacja „max-heapify” sprawdza, czy wartość elementu nadrzędnego jest większa niż wartość jego elementu potomnego. Elementy można następnie posortować za pomocą metod takich jak „swap” (zamień).ping.

• Łączyć: Jeśli masz dwa stosy do połączenia w jeden, użyj operacji scalania, aby połączyć wartości z obu stosów. Oryginalne stosy zostaną zachowane.

Sprawdź stosy

Inspekcja stosów polega na sprawdzeniu liczby elementów w strukturze danych stosu i upewnieniu się, że stos jest pusty.

Podczas sortowania lub kolejkowania elementów ważne jest sprawdzanie stert. Ważne jest sprawdzenie, czy istnieją elementy do przetworzenia za pomocą funkcji Is-Empty(). Rozmiar sterty pomoże zlokalizować pierwiastki sterty maksymalnej lub minimalnej, dlatego musisz wiedzieć, ile elementów znajduje się za właściwością sterty.

• Rozmiar – zwraca wielkość lub długość stosu. Informuje, ile elementów jest przechowywanych w kolejności posortowanej.
• Jest pusty – zwraca TRUE, jeśli stos jest pusty, w przeciwnym wypadku zwraca FALSE.

Tutaj drukujesz wszystkie elementy w pliku priorytetQ pętli, a następnie sprawdzamy, czy priorytetQ nie jest pusty.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

Zastosowania struktury danych sterty

Struktura danych Heap jest przydatna w wielu praktycznych zastosowaniach programistycznych, takich jak:

• Pomaga w filtrowaniu spamu.
• Implementacja algorytmów grafowych takich jak Dijkstra i Prim.
• Operarównoważenie obciążenia systemu i kompresja danych.
• Znajdowanie statystyk rzędu, takich jak k-ty najmniejszy element.
• Implementacja kolejek priorytetowych umożliwiających wyszukiwanie elementów na liście w czasie logarytmicznym.
• Struktura danych Heap jest również wykorzystywana do sortowania za pomocą sortowania kopcowego.
• Symulacja klientów oczekujących w kolejce.
• Obsługa przerwań w Operasystemu.
• W kodowaniu Huffmana do kompresji danych.
• Wspieranie wyszukiwania „najlepszy-najpierw” i heurystyki A* w planowaniu ścieżek AI.

Właściwości kolejki priorytetu sterty

Poniższe właściwości opisują zachowanie kolejki priorytetowej zbudowanej na stosie:

• W przypadku stosów priorytetowych elementy danych na liście są porównywane ze sobą w celu określenia, który element jest mniejszy lub większy.
• Element umieszczany jest w kolejce, a następnie usuwany według kolejności priorytetów.
• Każdy element w kolejce priorytetowej ma przypisany unikalny numer, który określa priorytet.
• Po opuszczeniu kolejki priorytetowej, element o najwyższym priorytecie wychodzi pierwszy.

Kroki implementacji kolejki priorytetowej sterty w Java

Następna sekcja przenosi się do betonu Java implementacja, która zamienia te reguły w działający kod.

Sortowanie sterty Java w Code Przykład

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

Wydajność

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

Sortowanie sterty Python w Code Przykład

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)

Wydajność

[1, 3, 4, 7, 9]

Następnie dowiesz się o Metoda bisekcji.

FAQ