Struktura danych sterty: co to jest sterta? Minimalna i maksymalna sterta (przykład)

Co to jest sterta?

Heap to wyspecjalizowana struktura danych drzewa. Heap obejmuje najwyższy węzeł zwany korzeniem (rodzicem). Jego drugie dziecko jest lewym dzieckiem korzenia, podczas gdy trzeci węzeł jest 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 jego potomstwa, a właściwe ułożenie następuje. Drzewo jest łatwe do zwizualizowania, gdzie każda jednostka jest nazywana węzłem. Węzeł ma unikalne klucze do identyfikacji.

Dlaczego potrzebujesz struktury danych sterty?

Oto główne powody stosowania struktury danych sterty:

Struktura danych sterty pozwala na usuwanie i wstawianie w czasie logarytmicznym – O(log₂N).
Dane w drzewie są ułożone w określonej kolejności. Oprócz aktualizowania lub sprawdzania takich rzeczy, jak maksimum lub minimum, programista może znaleźć relacje między rodzicem a potomkiem.
Można zastosować koncepcję Dokumentowy model obiektowy aby pomóc Ci w zrozumieniu struktury danych sterty.

Rodzaje stosów

Struktura danych sterty ma różne algorytmy obsługi wstawiania i usuwania elementów w strukturze danych sterty, w tym kolejkę priorytetową, stertę binarną, stertę dwumianową i Sortowanie sterty.

Kolejka priorytetowa: Jest to abstrakcyjna struktura danych zawierająca obiekty z priorytetami. Każdy obiekt lub element ma ustalony priorytet. Dlatego obiekt lub pozycja, której przypisano wyższy priorytet, otrzymuje usługę przed resztą.
Kopia binarna: Stosy binarne nadają się do prostych operacji na stosie, takich jak usuwanie i wstawianie.
Sterta dwumianowa: Kopiec dwumianowy składa się z serii zbiorów drzew dwumianowych, które tworzą stertę. Drzewo sterty dwumianowej nie jest zwyczajnym drzewem, ponieważ jest rygorystycznie zdefiniowane. Całkowita liczba elementów drzewa dwumianowego zawsze wynosi 2ⁿ węzły
Sortowanie sterty: W przeciwieństwie do większości algorytmów sortowania, heap-sort używa przestrzeni O(1) do swojej operacji sortowania. Jest to algorytm sortowania oparty na porównaniach, w którym sortowanie odbywa się w kolejności rosnącej, najpierw zamieniając je w maksymalny stos. Możesz postrzegać heapsort jako ulepszone drzewo wyszukiwania binarnego.

Zazwyczaj struktura danych sterty wykorzystuje dwie strategie. Dla wejścia 12 – 8 – 4 – 2 i 1

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

Min stos

W strukturze Min Heap węzeł główny ma wartość równą lub mniejszą niż wartości dzieci w tym węźle. Ten węzeł sterty minimalnej sterty przechowuje wartość minimalną. Podsumowując, jego struktura min-heap jest kompletna drzewo binarne.

Kiedy już będziesz mieć stertę Min na drzewie, wszystkie liście będą realnymi kandydatami. Należy jednak zbadać każdy liść, aby uzyskać dokładną wartość maksymalnej sterty.

Przykład minimalnej sterty

Na powyższych diagramach 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, musisz wykonać operacje min-heapify, aby zamienić elementy, aż właściwości Min heap zostaną spełnione.

Maksymalna sterta

W strukturze Max Heap węzeł nadrzędny lub główny ma wartość równą lub większą niż jego elementy podrzędne w węźle. Węzeł ten przechowuje wartość maksymalną. Co więcej, jest to kompletne drzewo binarne, więc możesz zbudować maksymalną stertę ze zbioru wartości i uruchomić ją w czasie O(n).

Oto kilka metod implementacji sterty Java Max

Dodać (): umieść nowy element na stercie. Jeśli używasz tablicy, obiekty są dodawane na końcu tablicy, podczas gdy 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 tablic. Ponieważ nowo dodany element nie jest już największy, metoda Sift-Down zawsze wypycha go w nowe miejsce.
Przesiewanie ():Ta metoda porównuje obiekt główny z jego obiektem podrzędnym, a następnie umieszcza nowo dodany węzeł na jego właściwej pozycji.
Przesiewanie (): jeśli użyjesz metody array w celu dodania nowo wstawionego elementu do tablicy, wówczas metoda Sift-Up pomoże nowo dodanemu węzłowi przenieść się do nowej pozycji. Nowo wstawiony element jest najpierw porównywany z elementem nadrzędnym poprzez symulację drzewiastej struktury danych.
Zastosuj formułę Parent_Index=Child_Index/2. Kontynuuj tę czynność, aż maksymalny element znajdzie się na początku tablicy.

Podstawowy stos Operanych

Aby znaleźć najwyższe i najniższe wartości w zestawie danych, potrzebujesz wielu podstawowych operacji na stercie, takich jak find, delete i insert. Ponieważ elementy będą stale pojawiać się i znikać, musisz:

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

Twórz stosy

Proces konstruowania stosów jest znany jako tworzenie stosów. Mając listę kluczy, programista tworzy pusty stos, a następnie wstawia inne klucze jeden po drugim, używając podstawowych operacji stosu.

Zacznijmy więc budować minimalną stertę, korzystając z metody Willaima, wstawiając wartości 12,2,8,1 i 4 na stercie. Możesz zbudować stertę z n elementów, zaczynając od pustej sterty, a następnie wypełniając ją sukcesywnie innymi elementami, stosując czas O (nlogn).

Heapify: w algorytmie wstawiania, który pomaga wstawiać elementy do sterty. Sprawdza, czy wyróżniona struktura danych sterty właściwości jest przestrzegana.
Na przykład, max heapify sprawdza, czy wartość rodzica jest większa niż jego potomka. Elementy można następnie sortować za pomocą metod takich jak swapping.

Scalanie: Biorąc pod uwagę, że masz dwie kopce do połączenia w jedną, użyj stert scalających, aby połączyć wartości z dwóch kopców. Jednak oryginalne hałdy są nadal zachowane.

Sprawdź stosy

Sprawdzanie stert oznacza sprawdzanie liczby elementów w strukturze danych sterty i sprawdzanie, czy sterta jest pusta.

Ważne jest, aby sprawdzać sterty jako sortowanie lub kolejkowanie elementów. Ważne jest sprawdzenie, czy masz elementy do przetworzenia za pomocą Is-Empty(). Rozmiar sterty pomoże zlokalizować stertę maksymalną lub stertę minimalną. Musisz więc znać elementy następujące po właściwości sterty.

Rozmiar – zwraca wielkość lub długość sterty. Można określić, ile elementów jest posortowanych.
Jest pusty – jeśli stos jest NULL, zwraca wartość TRUE, w przeciwnym wypadku zwraca wartość 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 sterty jest przydatna w wielu zastosowaniach programistycznych w prawdziwym życiu, takich jak:

Pomaga w filtrowaniu spamu.
Implementacja algorytmów grafowych.
OperaRównoważenie obciążenia systemu i kompresja danych.
Znajdź kolejność w statystykach.
Zaimplementuj kolejki priorytetowe, w których możesz wyszukiwać elementy na liście w czasie logarytmicznym.
Struktura danych sterty służy również do sortowania.
Symulacja klientów na linii.
Obsługa przerwań w Operasystemu.
W kodowaniu Huffmana do kompresji danych.

Właściwości kolejki priorytetu sterty

Na stertach priorytetowych elementy danych na liście są porównywane ze sobą w celu określenia mniejszego elementu.
Element umieszczany jest w kolejce, a następnie usuwany.
Każdy pojedynczy element w kolejce priorytetowej ma przypisany unikalny numer, identyfikowany jako priorytet.
Po wyjściu z kolejki priorytetowej element o najwyższym priorytecie wychodzi jako pierwszy.

Kroki wdrażania kolejki priorytetowej sterty w Java

Sortowanie sterty w Javie z przykładem kodu

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 the root and the largest element 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 z przykładem kodu

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)