Implementace datové struktury haldy (Max Heap) v Javě

Implementace datové struktury maximální haldy v Javě

Úvodní informace

Maximální halda, označovaná také jako max heap, je specifický typ stromové datové struktury. Uspořádání dat v této struktuře zajišťuje, že kořenový uzel vždy obsahuje největší prvek. Tato vlastnost ji činí ideální pro implementaci prioritních front, kde prvky s nejvyšší prioritou jsou zpracovávány přednostně.

Základní principy haldy

Haldy jsou formou úplných binárních stromů. To znamená, že každý uzel v haldě má maximálně dva následníky (levého a pravého potomka). Struktura haldy je navržena tak, aby hodnota každého uzlu byla větší nebo rovna hodnotám jeho potomků. Díky tomu je kořen stromu vždy největším prvkem.

Klíčové charakteristiky haldy

• Úplnost: Halda je kompletní binární strom, kde každý uzel, s výjimkou posledního, má dva potomky.
• Hierarchie: Hodnota každého uzlu je větší nebo rovna hodnotám jeho následníků.
• Výšková složitost: Maximální výška haldy je úměrná logaritmu počtu uzlů (O(log n)), kde n je počet uzlů v haldě.

Základní operace nad haldou

Mezi nejčastější operace prováděné s haldou patří:

• Vložení prvku: Přidání nového prvku do haldy při zachování jejích vlastností.
• Odebrání maximálního prvku: Odstranění kořenového prvku (největšího v haldě) a jeho nahrazení s cílem zachovat strukturu haldy.
• Snížení klíče: Snížení hodnoty uzlu, což může vést k narušení struktury haldy a vyžaduje její obnovení.
• Zvýšení klíče: Operace zvýšení hodnoty uzlu je obecně zakázána, protože by porušila hierarchii haldy.

Implementace v Javě

V jazyce Java se halda obvykle implementuje pomocí pole. Každý prvek pole reprezentuje uzel haldy. Indexování pole začíná od 1.

Následující kód představuje základní implementaci maximální haldy:

public class MaxHeap {

    private int[] heap;
    private int size;

    // Konstruktor
    public MaxHeap(int capacity) {
        heap = new int[capacity + 1]; // +1 pro kořen
        size = 0;
    }

    // Vložení prvku
    public void insert(int key) {
        if (size == heap.length - 1) {
            // Halda je plná
            return;
        }

        // Vložení na konec
        heap[++size] = key;

        // Obnovení vlastností haldy
        heapifyUp(size);
    }

    // Obnovení vlastností haldy po vložení
    private void heapifyUp(int index) {
        while (index > 1) {
            int parentIndex = index / 2;
            if (heap[index] > heap[parentIndex]) {
                // Prohození
                swap(heap, index, parentIndex);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    // Odebrání kořene
    public int extractMax() {
        if (size == 0) {
            // Halda je prázdná
            return -1;
        }

        // Uložení kořene
        int max = heap[1];

        // Nahrazení kořene posledním prvkem
        heap[1] = heap[size];

        // Snížení velikosti
        size--;

        // Obnovení vlastností haldy
        heapifyDown(1);

        return max;
    }

    // Obnovení vlastností haldy po vyjmutí
    private void heapifyDown(int index) {
        while (true) {
            int leftChildIndex = index * 2;
            int rightChildIndex = index * 2 + 1;

            // Žádní potomci
            if (leftChildIndex > size) {
                break;
            }

            int maxChildIndex;
            if (rightChildIndex > size) {
                maxChildIndex = leftChildIndex;
            } else {
                if (heap[leftChildIndex] > heap[rightChildIndex]) {
                    maxChildIndex = leftChildIndex;
                } else {
                    maxChildIndex = rightChildIndex;
                }
            }

            if (heap[index] < heap[maxChildIndex]) {
                swap(heap, index, maxChildIndex);
                index = maxChildIndex;
            } else {
                break;
            }
        }
    }

    // Prohození prvků
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Praktické využití

Maximální haldy se uplatňují v mnoha oblastech, například:

• Implementace prioritních front.
• Algoritmus pro třídění haldou (Heapsort).
• Použití v grafových algoritmech.
• Vyhledávání mediánu.

Závěr

Maximální halda je datová struktura s efektivním způsobem ukládání dat, kde největší prvek má vždy prioritu. Její rychlé operace, jako je vkládání, odstraňování a aktualizace, z ní činí ideální řešení pro různé algoritmy a aplikace. Implementace v Javě s použitím pole je poměrně jednoduchá a snadno pochopitelná.

Často kladené otázky

1. Jaká je časová náročnost vložení do haldy?	Operace vložení má časovou složitost O(log n), kde n je počet prvků v haldě.
2. Jaká je časová náročnost odebrání kořene haldy?	Časová složitost operace odebrání kořene haldy je rovněž O(log n), kde n je počet prvků v haldě.
3. Co se stane, když vložíme prvek větší než kořen?	Pokud vložíme prvek s hodnotou větší než kořen, dojde k porušení hierarchie haldy. V takovém případě je nutné použít operaci heapifyUp pro obnovení správného uspořádání prvků.
4. Co se stane, když snížíme hodnotu uzlu, který není kořenem?	Snížení hodnoty uzlu, který není kořenem, může narušit vlastnosti haldy. Po takové operaci je nutné provést heapifyUp pro obnovení struktury.
5. Proč haldu reprezentujeme polem?	Reprezentace haldy polem je efektivní a jednoduchý způsob, jak uložit strukturu v paměti. Pole umožňuje snadný přístup k prvkům a rychlé vyhledávání.
6. Existují jiné možnosti implementace haldy v Javě?	Ano, lze použít Java Collections Framework, které nabízí další možnosti implementace haldy.
7. Jak můžeme třídit pole čísel s pomocí haldy?	Halda se používá v algoritmu heapsort, jehož časová složitost je O(n log n).
8. Jak se liší halda od binárních vyhledávacích stromů?	Na rozdíl od binárních vyhledávacích stromů, které jsou optimalizované pro vyhledávání a vkládání, haldy primárně slouží k efektivnímu získání prvku s nejvyšší prioritou.