Spis treści:
Implementacja struktury danych Max Heap w Javie
Wprowadzenie
Max heap to specjalny typ drzewa binarnego, w którym każdy węzeł jest większy lub równy swoim potomnym. Ta struktura danych jest często używana w algorytmach, takich jak sortowanie heap, wyszukiwanie najlepszego pierwszeństwa i wybór elementów o najwyższej wartości.
Implementacja max heap w Javie jest stosunkowo prosta. Aby to zrobić, możemy wykorzystać tablicę, która będzie reprezentować drzewo binarne. Następnie możemy użyć następujących zasad do utrzymania struktury max heap:
* Węzeł rodzicielski: Każdy węzeł ma dokładnie jeden węzeł rodzicielski, który jest zawsze większy lub równy jemu.
* Węzły potomne: Każdy węzeł może mieć maksymalnie dwa węzły potomne, które są zawsze mniejsze lub równe jemu.
* Wysokość: Wysokość drzewa heap jest mniejsza lub równa log2(n), gdzie n jest liczbą elementów w drzewie.
Operacje na max heap
Najczęstsze operacje na max heap to:
Insert (wstawianie)
Wstawianie elementu do max heap polega na dodaniu go do końca tablicy i następnie przywróceniu struktury heap za pomocą operacji bubble up. Bubble up przesuwa element w górę drzewa, zamieniając go z jego rodzicem, dopóki nie znajdzie się na właściwym miejscu w stosunku do swoich potomnych.
Extract Max (usuwanie maksymalnego elementu)
Usuwanie maksymalnego elementu z max heap polega na zamianie go z ostatnim elementem w tablicy i następnie przywróceniu struktury heap za pomocą operacji bubble down. Bubble down przesuwa element w dół drzewa, zamieniając go z jego większym potomkiem, dopóki nie znajdzie się na właściwym miejscu w stosunku do swoich potomków.
Decrease Key (zmniejszenie klucza)
Operacja decrease key zmniejsza wartość elementu w max heap. Wymaga to przywrócenia struktury heap za pomocą operacji bubble up, aby zapewnić, że element pozostaje mniejszy lub równy swoim potomnym.
Increase Key (zwiększenie klucza)
Operacja increase key zwiększa wartość elementu w max heap. Wymaga to przywrócenia struktury heap za pomocą operacji bubble down, aby zapewnić, że element pozostaje większy lub równy swoim potomnym.
Delete (usuwanie)
Operacja delete usuwa element z max heap. Aby to zrobić, najpierw używamy operacji decrease key, aby zmniejszyć wartość elementu do ujemnej nieskończoności, a następnie używamy operacji extract max, aby usunąć element z drzewa.
Implementacja kodu w Javie
Poniżej przedstawiono przykładową implementację max heap w Javie:
java
import java.util.Arrays;
public class MaxHeap {
private int[] heap;
private int size;
public MaxHeap(int[] arr) {
heap = arr;
size = arr.length;
buildHeap();
}
public int getSize() {
return size;
}
private void buildHeap() {
for (int i = size / 2 - 1; i >= 0; i--) {
bubbleDown(i);
}
}
public void insert(int value) {
if (size == heap.length) {
resizeHeap();
}
heap[size++] = value;
bubbleUp(size - 1);
}
public int extractMax() {
int max = heap[0];
heap[0] = heap[size - 1];
size--;
bubbleDown(0);
return max;
}
public void decreaseKey(int index, int value) {
if (value > heap[index]) {
throw new IllegalArgumentException("New value must be less than or equal to current value.");
}
heap[index] = value;
bubbleUp(index);
}
public void increaseKey(int index, int value) {
if (value < heap[index]) {
throw new IllegalArgumentException("New value must be greater than or equal to current value.");
}
heap[index] = value;
bubbleDown(index);
}
public void delete(int index) {
decreaseKey(index, Integer.MIN_VALUE);
extractMax();
}
private void bubbleUp(int index) {
while (index > 0) {
int parentIndex = (index - 1) / 2;
if (heap[index] > heap[parentIndex]) {
swap(index, parentIndex);
index = parentIndex;
} else {
break;
}
}
}
private void bubbleDown(int index) {
while (true) {
int leftChildIndex = 2 * index + 1;
int rightChildIndex = 2 * index + 2;
int maxIndex = index;
if (leftChildIndex < size && heap[leftChildIndex] > heap[maxIndex]) {
maxIndex = leftChildIndex;
}
if (rightChildIndex < size && heap[rightChildIndex] > heap[maxIndex]) {
maxIndex = rightChildIndex;
}
if (maxIndex == index) {
break;
}
swap(index, maxIndex);
index = maxIndex;
}
}
private void resizeHeap() {
int[] newHeap = new int[heap.length * 2];
System.arraycopy(heap, 0, newHeap, 0, heap.length);
heap = newHeap;
}
private void swap(int index1, int index2) {
int temp = heap[index1];
heap[index1] = heap[index2];
heap[index2] = temp;
}
@Override
public String toString() {
return Arrays.toString(heap);
}
}
Zastosowania max heap
Max heap ma szeroki zakres zastosowań, w tym:
* Sortowanie elementów w kolejności malejącej (sortowanie heap)
* Wyszukiwanie elementu o największej wartości
* Wybór k największych elementów z kolekcji
* Obliczanie median w strumieniu danych
Wnioski
Max heap to wydajna struktura danych, która umożliwia szybkie wyszukiwanie i wybieranie największych elementów. Implementacja max heap w Javie jest stosunkowo prosta i można ją wykorzystać do różnych zastosowań, takich jak sortowanie, wyszukiwanie i wybór elementów o najwyższej wartości.
Często zadawane pytania
1. Co to jest max heap?
Max heap to struktura danych w postaci drzewa binarnego, w której każdy węzeł jest większy lub równy swoim potomnym.
2. Jakie są najczęściej wykonywane operacje na max heap?
Najczęstsze operacje to: insert (wstawianie), extract max (usuwanie maksymalnego elementu), decrease key (zmniejszenie klucza), increase key (zwiększenie klucza) i delete (usuwanie).
3. Jak działa operacja bubble up?
Bubble up przesuwa element w górę drzewa, zamieniając go z jego rodzicem, dopóki nie znajdzie się na właściwym miejscu w stosunku do swoich potomnych.
4. Jak działa operacja bubble down?
Bubble down przesuwa element w dół drzewa, zamieniając go z jego większą wartością potomną, dopóki nie znajdzie się na właściwym miejscu w stosunku do swoich potomnych.
5. Jak zaimplementować max heap w Javie?
Aby zaimplementować max heap w Javie, można użyć tablicy do reprezentacji drzewa binarnego i zastosować zasady max heap podczas wykonywania operacji, takich jak insert, extract max i decrease key.
6. Jakie są zastosowania max heap?
Max heap jest często używany w algorytmach, takich jak sortowanie heap, wyszukiwanie najlepszego pierwszeństwa i wybór elementów o najwyższej wartości.
7. Jak użyć max heap do sortowania elementów w kolejności malejącej?
Aby posortować elementy w kolejności malejącej, można użyć max heap i powtarzać operację extract max, aż w heapie nie pozostaną żadne elementy.
8. Jak użyć max heap do znalezienia elementu o największej wartości?
Aby znaleźć element o największej wartości w max heap, wystarczy odczytać korzeń drzewa heap.
9. Jaka jest wydajność operacji na max heap?
Operacje na max heap, takie jak insert, extract max i decrease key, mają złożoność czasową O(log n), gdzie n jest liczbą elementów w