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

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

Úvod

Max heap je datová struktura stromového typu, která uchovává data ve stromové struktuře, přičemž největší prvek je vždy umístěn na kořenu. Díky této vlastnosti se max heap často používá pro efektivní implementaci prioritní fronty, kde jsou prvky zpracovávány podle jejich priority.

Struktura haldy

Halda je úplný binární strom, kde každý uzel má maximálně dvě děti. Strom je uspořádán tak, že klíč každého uzlu je větší nebo roven klíčům jeho dětí. Kořen stromu má tedy vždy největší klíč.

Vlastnosti haldy

* Kompletnost: Halda je úplný binární strom, kde je každý uzel vyplněn nebo je posledním uzlem v nejnižší úrovni.
* Vlastnost haldy: Klíč každého uzlu je větší nebo roven klíčům jeho dětí.
* Výška: Výška haldy je O(log n), kde n je počet uzlů v haldě.

Operace haldy

Hlavní operace prováděné na haldě jsou:

* Vložení: Vložení prvku do haldy udržuje vlastnost haldy.
* Vyjmutí: Vyjmutí kořene haldy a jeho nahrazení dalším největším prvkem udržuje vlastnost haldy.
* Snížení klíče: Snížení klíče uzlu může porušit vlastnost haldy a vyžaduje její obnovení.
* Zvýšení klíče: Zvýšení klíče uzlu není povoleno, protože naruší vlastnost haldy.

Implementace v Javě

V Javě můžeme implementovat datovou strukturu haldy pomocí pole. Každý prvek pole představuje uzel haldy a pole je indexováno od 1.

java
public class MaxHeap {

private int[] heap;
private int size;

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

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

// Vložení nového uzlu na konec
heap[++size] = key;

// Provedení operace heapify pro obnovení vlastnosti haldy
heapifyUp(size);
}

// Provedení operace heapify pro obnovení vlastnosti haldy po vložení
private void heapifyUp(int index) {
while (index > 1) {
int parentIndex = index / 2;
if (heap[index] > heap[parentIndex]) {
// Porušení vlastnosti haldy, prohození klíčů
swap(heap, index, parentIndex);
index = parentIndex;
} else {
// Vlastnost haldy zachována, ukončení smyčky
break;
}
}
}

// Vyjmutí kořenového uzlu
public int extractMax() {
if (size == 0) {
// Halda je prázdná, nelze vyjmout
return -1;
}

// Kořenový uzel
int max = heap[1];

// Nahrazení kořenového uzlu posledním uzlem
heap[1] = heap[size];

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

// Provedení operace heapify pro obnovení vlastnosti haldy po odstranění
heapifyDown(1);

return max;
}

// Provedení operace heapify pro obnovení vlastnosti haldy po vyjmutí
private void heapifyDown(int index) {
while (true) {
int leftChildIndex = index * 2;
int rightChildIndex = index * 2 + 1;

// Nebyly nalezeny žádné děti
if (leftChildIndex > size) {
break;
}

int maxChildIndex;
if (rightChildIndex > size) {
// Pouze levé dítě
maxChildIndex = leftChildIndex;
} else {
// Oba děti
if (heap[leftChildIndex] > heap[rightChildIndex]) {
maxChildIndex = leftChildIndex;
} else {
maxChildIndex = rightChildIndex;
}
}

if (heap[index] < heap[maxChildIndex]) {
// Porušení vlastnosti haldy, prohození klíčů
swap(heap, index, maxChildIndex);
index = maxChildIndex;
} else {
// Vlastnost haldy zachována, ukončení smyčky
break;
}
}
}

// Pomocná metoda pro prohození dvou prvků v poli
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}


Příklady použití

Max heap lze použít v různých aplikacích, včetně:

* Prioritní fronty
* Algoritmus třídění haldou
* Grafové algoritmy
* Výběr mediánu

Závěr

Max heap je efektivní datová struktura pro ukládání prvků v uspořádaném pořadí. Umožňuje rychlé vkládání, vyjímání a operace snižování klíče a nachází široké uplatnění v různých algoritmech a aplikacích. Implementace v Javě je poměrně přímočará a využívá pole pro reprezentaci stromu.

Často kladené dotazy

1. Jaká je časová složitost operace vložení do haldy?
Časová složitost operace vložení je O(log n), kde n je počet prvků v haldě.

2. Jaká je časová složitost operace vyjmutí kořene haldy?
Časová složitost operace vyjmutí kořene haldy je O(log n), kde n je počet prvků v haldě.

3. Co se stane, když se pokusíme vložit prvek větší než kořen?
Pokud se pokusíme vložit prvek větší než kořen, nebude vlastnost haldy zachována. Bude nutné provést operaci heapifyUp pro obnovení vlastnosti haldy.

4. Co se stane, když se pokusíme snížit klíč uzlu, který není kořenem?
Snížení klíče uzlu, který není kořenem, může porušit vlastnost haldy. Bude nutné provést operaci heapifyUp pro obnovení vlastnosti haldy.

5. Proč se halda zobrazuje jako pole?
Halda se zobrazuje jako pole, protože je to jednoduchý způsob, jak uložit haldovou strukturu v paměti. Pole umožňuje rychlé vyhledávání a přístup k prvkům haldy.

6. Existují nějaké alternativy k implementaci haldy v Javě?
Ano, existují alternativy k implementaci haldy v Javě, jako je použití knihovny Java Collections Framework.

7. Jak lze třídit pole čísel pomocí haldy?
Pole čísel lze třídit pomocí haldy pomocí algoritmu třídění haldou, který má časovou složitost O(n log n).

8. Jak se odhalí haldy od jiných datových struktur stromového typu, jako jsou binární vyhledávací stromy?
Na rozdíl od binárních vyhledávacích stromů, které prioritují operace vyhledávání a vkládání, se haldy zaměřují na umožnění efektivního vyjímání prvků s nejvyšší prioritou.