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