Struktura dat haldy: Co je halda? Minimální a maximální halda (příklad)

Co je halda?

Halda je specializovaná stromová datová struktura. Halda obsahuje nejvyšší uzel nazývaný kořen (rodič). Jeho druhý uzel je levým potomkem kořene, zatímco třetí uzel je pravým potomkem kořene. Následné uzly se vyplňují zleva doprava. Klíč rodičovského uzlu se porovná s klíčem jeho potomka a dojde ke správnému uspořádání. Strom lze snadno vizualizovat, kde se každá entita nazývá uzel. Uzel má jedinečné klíče pro identifikaci.

Proč potřebujete datovou strukturu haldy?

Zde jsou hlavní důvody pro použití datové struktury haldy:

Struktura dat haldy umožňuje mazání a vkládání v logaritmickém čase – O(log₂ne).
Data ve stromu jsou vytvořena v určitém pořadí. Kromě aktualizace nebo dotazování na věci, jako je maximum nebo minimum, může programátor najít vztahy mezi rodičem a potomkem.
Můžete použít koncept Objektový model dokumentu které vám pomohou pochopit strukturu dat haldy.

Typy hald

Struktura dat haldy má různé algoritmy pro zpracování vkládání a odstraňování prvků v datové struktuře haldy, včetně prioritní fronty, binární haldy, binomické haldy a Heap-Sort.

Prioritní fronta: Jedná se o abstraktní datovou strukturu obsahující prioritní objekty. Každý objekt nebo položka má pro něj předem nastavenou prioritu. Proto objekt nebo položka s vyšší prioritou získává službu před ostatními.
Binární halda: Binární haldy jsou vhodné pro jednoduché operace s haldami, jako jsou mazání a vkládání.
Binomická halda: Binomická halda se skládá ze série kolekcí binomických stromů, které tvoří haldu. Binomický strom haldy není obyčejný strom, jak je přesně definován. Celkový počet prvků v binomickém stromě má vždy 2ⁿ uzly.
Heap-Sort: Na rozdíl od většiny třídicích algoritmů používá heap-sort pro svou operaci řazení prostor O(1). Je to algoritmus třídění založený na porovnání, kde k řazení dochází ve vzrůstajícím pořadí tak, že se nejprve změní na maximální hromadu. Na Heapsort se můžete dívat jako na vylepšený binární vyhledávací strom.

Struktura dat haldy obvykle využívá dvě strategie. Pro vstup 12 – 8 – 4 – 2 a 1

Min Heap – nejmenší hodnota nahoře
Max Heap – nejvyšší hodnota nahoře

Min. halda

Ve struktuře Min Heap má kořenový uzel hodnotu buď rovnou nebo menší než děti v tomto uzlu. Tento uzel haldy minimální haldy má minimální hodnotu. Celkově vzato je jeho struktura min-hromady kompletní binární strom.

Jakmile máte na stromě hromadu Min, všechny listy jsou životaschopnými kandidáty. Musíte však prozkoumat každý z listů, abyste získali přesnou hodnotu Max-heap.

Příklad min. haldy

Ve výše uvedených diagramech si můžete všimnout určité jasné sekvence od kořene po nejnižší uzel.

Předpokládejme, že uložíte prvky do pole Array Array_N[12,2,8,1,4]. Jak můžete vidět z pole, kořenový prvek porušuje prioritu minimální haldy. Chcete-li zachovat vlastnost Min haldy, musíte provést operace min-heapify pro výměnu prvků, dokud nebudou splněny vlastnosti Min haldy.

Max Heap

Ve struktuře Max Heap má nadřazený nebo kořenový uzel hodnotu rovnou nebo větší než jeho potomci v uzlu. Tento uzel má maximální hodnotu. Navíc je to kompletní binární strom, takže můžete sestavit maximální hromadu z kolekce hodnot a spustit ji v čase O(n).

Zde je několik metod pro implementaci java max haldy

Přidat (): umístěte nový prvek do hromady. Pokud použijete pole, objekty se přidají na konec pole, zatímco v binárním stromu se objekty přidají shora dolů a poté zleva doprava.
Odebrat (): Tato metoda umožňuje odstranit první prvek ze seznamu polí. Protože nově přidaný prvek již není největší, metoda Sift-Down jej vždy posune na nové místo.
Třídění dolů (): Tato metoda porovná kořenový objekt s jeho potomkem a poté přesune nově přidaný uzel na jeho správnou pozici.
Sift-Up (): pokud použijete metodu pole k přidání nově vloženého prvku do pole, pak metoda Sift-Up pomůže nově přidanému uzlu přemístit se na jeho novou pozici. Nově vložená položka je nejprve porovnána s nadřazenou simulací stromové datové struktury.
Použít vzorec Parent_Index=Child_Index/2. Pokračujte v tom, dokud nebude maximální prvek v přední části pole.

Základní halda Operace

K tomu, abyste našli nejvyšší a nejnižší hodnoty v sadě dat, potřebujete spoustu základních operací s haldou, jako je najít, odstranit a vložit. Protože prvky budou neustále přicházet a odcházet, musíte:

Najít – Hledejte předmět na hromadě.
Vložit – Přidejte do hromady nové dítě.
Vymazat – Odstranit uzel z hromady.

Vytvořte haldy

Proces vytváření hald je známý jako vytváření hald. Vzhledem k seznamu klíčů programátor vytvoří prázdnou hromadu a poté vloží další klíče jeden po druhém pomocí základních operací s hromadou.

Začněme tedy sestavovat Min-heap pomocí Willaimovy metody vložením hodnot 12,2,8,1 a 4 do haldy. Hromadu s n prvky můžete vytvořit tak, že začnete s prázdnou hromadou a poté ji postupně naplníte dalšími prvky pomocí času O (nlogn).

Heapify: ve vkládacím algoritmu, který pomáhá vkládat prvky do haldy. Kontroluje se, zda je zvýrazněna datová struktura haldy vlastností.
Například maximální heapify by zkontrolovalo, zda je hodnota rodiče větší než jeho potomek. Prvky pak lze třídit pomocí metod, jako je výměna.

Sloučit: Vzhledem k tomu, že máte dvě hromady ke spojení do jedné, použijte slučovací hromady ke spojení hodnot z těchto dvou hromad. Původní haldy jsou však stále zachovány.

Zkontrolujte haldy

Kontrola hald se týká kontroly počtu prvků v datové struktuře haldy a ověření, zda je halda prázdná.

Je důležité kontrolovat hromady jako třídění nebo řazení prvků do fronty. Je důležité zkontrolovat, zda máte prvky ke zpracování pomocí Is-Empty(). Velikost haldy pomůže najít maximální nebo minimální haldu. Takže musíte znát prvky následující po vlastnosti haldy.

Velikost – vrátí velikost nebo délku haldy. Můžete zjistit, kolik prvků je seřazeno.
Je prázdný – pokud je halda NULL, vrátí hodnotu TRUE, jinak vrátí hodnotu FALSE.

Zde tisknete všechny prvky v prioritaQ smyčka a poté kontrola, zda prioritaQ není prázdná.

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

Použití datové struktury haldy

Struktura dat haldy je užitečná v mnoha programovacích aplikacích v reálném životě, jako je:

Pomáhá při filtrování spamu.
Implementace grafových algoritmů.
Operating Vyrovnávání zatížení systému a komprese dat.
Najděte pořadí ve statistikách.
Implementujte prioritní fronty, kde můžete vyhledávat položky v seznamu v logaritmickém čase.
Struktura dat haldy se také používá pro řazení.
Simulace zákazníků na lince.
Přerušit manipulaci v Operasystém.
V Huffmanově kódování pro kompresi dat.

Vlastnosti prioritní fronty haldy

V prioritních haldách se datové položky v seznamu vzájemně porovnávají, aby se určil menší prvek.
Prvek je umístěn do fronty a poté odstraněn.
Každý jednotlivý prvek v prioritní frontě má jedinečné číslo, které se k němu vztahuje, identifikované jako priorita.
Po opuštění prioritní fronty se nejprve ukončí prvek nejvyšší priority.

Kroky pro implementaci prioritní fronty haldy v Java

Řazení haldy v JAVA s příkladem kódu

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);
        }
    }
}

Výstup

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

Halda Seřadit Python s příkladem kódu

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)