Datová struktura haldy: Co je halda?

Co je datová struktura haldy?

Halda je specializovaná stromová datová struktura. Datová struktura haldy se skládá z nejvyššího uzlu nazývaného 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 plní zleva doprava. Klíč rodičovského uzlu se porovnává s klíčem jeho potomka, aby došlo ke správnému uspořádání. Strom je snadno vizualizovatelný, kde každá entita se nazývá uzel a každý uzel má jedinečný klíč pro identifikaci.

Jednoduše řečeno, halda je kompletní binární strom, který splňuje vlastnost haldy: každý rodič je konzistentně seřazen vůči svým potomkům, což z něj činí ideální pro prioritní fronty a třídění haldou.

Proč potřebujete datovou strukturu haldy?

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

• Datová struktura Heap umožňuje mazání a vkládání v logaritmickém čase – O(log₂ne).
• Data ve stromu jsou uspořádána v určitém pořadí. Kromě aktualizace nebo dotazování hodnot, 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 vizuálně porozumět datové struktuře haldy.
• Haldy podporují efektivní operace s prioritními frontami, které jsou klíčové pro grafové algoritmy, jako je Dijkstrova metoda nejkratší cesty a Primův minimální kostní strom.

Typy hald

Datová struktura haldy má různé algoritmy pro zpracování vkládání a odebírání prvků, včetně prioritní fronty, binární haldy, binomické haldy a... Třídění haldy.

• Prioritní fronta: Je to břišní svaltracDatová struktura t obsahující objekty s prioritou. Každý objekt nebo položka má předem stanovenou prioritu. Objekt nebo položka s vyšší prioritou proto získá službu dříve než ostatní.
• Binární halda: Binární haldy jsou vhodné pro jednoduché operace s haldou, jako je mazání a vkládání. Jsou výchozí implementací pro většinu prioritních front standardních knihoven.
• Binomická halda: Binomická halda se skládá ze série kolekcí binomických stromů, které tvoří haldu. Binomický strom není obyčejný strom, protože je striktně definován. Celkový počet prvků v binomickém stromu se vždy rovná 2.ⁿ uzly.
• Třídění haldy: Na rozdíl od většiny třídících algoritmů používá Heap Sort pro svou třídící operaci prostor O(1). Jedná se o třídicí algoritmus založený na porovnávání, kde řazení probíhá vzestupně tak, že se nejprve vstup převede na Max-Heap. Na Heap Sort se můžete dívat jako na vylepšený binární vyhledávací strom.

Datová struktura Heap obvykle používá dvě strategie. Pro vstupy 12 – 8 – 4 – 2 a 1:

• Min-Heap – nejnižší hodnota nahoře
• Max-Heap – nejvyšší hodnota nahoře

Min-Heap

Ve struktuře Min-Heap má kořenový uzel hodnotu buď rovnou, nebo menší než potomci daného uzlu. Kořen Min-Heap proto obsahuje minimální hodnotu. Min-Heap je také kompletní binární strom.

Jakmile máte ve stromu Min-Heap, všechny listy jsou vhodnými kandidáty na maximální hodnotu. Abyste však získali přesnou hodnotu Max-Heap, musíte prozkoumat každý list.

Příklad Min-Heap

Na výše uvedeném diagramu si můžete všimnout jasné posloupnosti od kořene k nejnižšímu uzlu.

Předpokládejme, že ukládáte prvky do pole Array_N[12, 2, 8, 1, 4]. Jak je z pole vidět, kořenový prvek porušuje prioritu Min-Heap. Abyste zachovali vlastnost Min-Heap, musíte provést operace min-heapify, abyste prohodili prvky, dokud nebudou splněna pravidla Min-Heap.

Max-Heap

Ve struktuře Max-Heap má nadřazený nebo kořenový uzel hodnotu rovnou nebo větší než jeho potomci. Tento uzel obsahuje maximální hodnotu. Jedná se o kompletní binární strom, takže Max-Heap lze sestavit z kolekce hodnot v čase O(n).

Zde je několik metod běžně používaných při implementaci Java Max-Heap:

• Přidat (): Umístí nový prvek do haldy. Pokud používáte pole, objekty se přidávají na konec pole, zatímco v binárním stromu se objekty přidávají shora dolů a poté zleva doprava.
• Odebrat (): Tato metoda umožňuje odstranit první prvek ze seznamu polí. Protože nově povýšený prvek již není největší, metoda Sift-Down jej vždy přesune na nové místo.
• Prosítění (): Tato metoda porovnává kořenový objekt s jeho podřízenými objekty a poté přesune přemístěný uzel na jeho správnou pozici.
• Prosít (): Pokud použijete metodu array 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 správnou pozici. Nový prvek je nejprve porovnán se svým rodičem simulací stromové datové struktury.

  Použijte vzorec Parent_Index = Child_Index / 2. Pokračujte v tom, dokud se maximální prvek nedostane na začátek pole.

Základní halda Operace

Abyste v datové sadě našli nejvyšší a nejnižší hodnotu, potřebujete několik základních operací s haldou, jako je hledání, vkládání a mazání. Protože prvky neustále přicházejí a odcházejí, měli byste vědět, jak:

• 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 sestavování hald se nazývá vytváření hald. Na základě seznamu klíčů programátor vytvoří prázdnou haldu a poté do ní postupně vkládá ostatní klíče pomocí základních operací s haldou.

Začněme tedy budovat Min-Heap pomocí Williamsovy metody vložením hodnot 12, 2, 8, 1 a 4. Haldu s n prvky můžete vytvořit tak, že začnete s prázdnou haldou a poté ji postupně naplníte dalšími prvky s časem O(n log n).

• Heapify: Vkládací rutina, která pomáhá vkládat prvky do haldy a zároveň zachovává vlastnost haldy.

  Například operace max-heapify kontroluje, zda je hodnota rodičovského prvku větší než hodnota jeho potomka. Prvky pak lze seřadit pomocí metod jako swap.ping.

• Spojit: Pokud máte dvě haldy, které chcete sloučit do jedné, použijte operaci sloučení, abyste hodnoty z obou hald sloučili dohromady. Původní haldy zůstanou zachovány.

Zkontrolujte haldy

Inspekce hald se vztahuje ke kontrole počtu prvků v datové struktuře haldy a ověření, zda je halda prázdná.

Při třídění nebo řazení prvků do fronty je důležité kontrolovat haldy. Důležité je ověřit, zda existují prvky ke zpracování pomocí funkce Is-Empty(). Velikost haldy pomůže najít kořeny Max-Heap nebo Min-Heap, takže je potřeba vědět, kolik prvků následuje za vlastností heap.

• Velikost – vrací velikost nebo délku haldy. Udává, kolik prvků je uloženo v seřazeném pořadí.
• Je prázdné – vrací TRUE, pokud je halda null, jinak vrací 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

Datová struktura haldy je užitečná v mnoha programovacích aplikacích v reálném životě, například:

• Pomáhá s filtrováním spamu.
• Implementace grafových algoritmů, jako jsou Dijkstra a Prim.
• Operavyvažování zátěže systému a komprese dat.
• Hledání statistik řádu, jako je například k-tý nejmenší prvek.
• Implementace prioritních front, kde můžete vyhledávat položky v seznamu v logaritmickém čase.
• Struktura dat haldy se také používá pro třídění pomocí metody Heap Sort.
• Simulace zákazníků ve frontě.
• Ošetření přerušení v Operasystém.
• V Huffmanově kódování pro kompresi dat.
• Využití metody hledání podle principu „nejprve nejlepší“ a heuristik A* v plánování cest s využitím umělé inteligence.

Vlastnosti prioritní fronty haldy

Následující vlastnosti popisují, jak se chová prioritní fronta vytvořená na haldě:

• V prioritních haldách se datové položky v seznamu vzájemně porovnávají, aby se určil menší nebo větší prvek.
• Prvek je umístěn do fronty a následně odstraněn v pořadí podle priority.
• Každý jednotlivý prvek ve frontě priorit má jedinečné číslo, které se k němu vztahuje a je identifikované jako priorita.
• Po opuštění prioritní fronty se jako první opustí prvek s nejvyšší prioritou.

Kroky pro implementaci fronty s prioritou haldy v Java

Další část se přesouvá do betonu Java implementace, která tato pravidla přemění na funkční kód.

Halda Seřadit Java s Code Příklad

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

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 Code Příklad

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)

Výstup

[1, 3, 4, 7, 9]

Dále se dozvíte o Metoda půlení.

Nejčastější dotazy