Wdrożenie struktury danych Max Heap w języku Java
Wprowadzenie
Max heap, czyli kopiec maksymalny, to wyspecjalizowana forma drzewa binarnego. Charakteryzuje się tym, że wartość każdego węzła jest większa lub równa wartości jego węzłów potomnych. Ta struktura danych ma szerokie zastosowanie w różnorodnych algorytmach. Wykorzystuje się ją m.in. w sortowaniu przez kopcowanie (heap sort), przy implementacji kolejek priorytetowych oraz w procesach wyboru elementów o najwyższej wartości.
Implementacja kopca maksymalnego w środowisku Java jest stosunkowo nieskomplikowana. Drzewo binarne można skutecznie odwzorować za pomocą tablicy. Aby zagwarantować zachowanie struktury kopca maksymalnego, stosuje się następujące reguły:
- Węzeł nadrzędny: Każdy węzeł posiada dokładnie jeden węzeł nadrzędny, którego wartość jest zawsze większa lub równa wartości danego węzła.
- Węzły podrzędne: Każdy węzeł może posiadać maksymalnie dwa węzły podrzędne, których wartości są zawsze mniejsze lub równe wartości danego węzła.
- Wysokość drzewa: Wysokość drzewa kopca jest nie większa niż log₂n, gdzie n oznacza liczbę elementów w drzewie.
Operacje dostępne w kopcu maksymalnym
Do najczęściej wykonywanych operacji na kopcu maksymalnym zalicza się:
Wstawianie (Insert)
Proces wstawiania nowego elementu do kopca maksymalnego polega na umieszczeniu go na końcu tablicy, a następnie na przywróceniu właściwej struktury kopca za pomocą operacji „przesuwania w górę” (ang. bubble up). Operacja bubble up polega na przemieszczaniu dodanego elementu w górę drzewa poprzez zamianę jego pozycji z węzłem nadrzędnym, aż do osiągnięcia odpowiedniego miejsca w strukturze kopca.
Pobieranie Maksimum (Extract Max)
Pobranie elementu o największej wartości z kopca maksymalnego odbywa się poprzez zastąpienie go ostatnim elementem w tablicy, a następnie przywrócenie struktury kopca za pomocą operacji „przesuwania w dół” (ang. bubble down). Bubble down polega na przemieszczaniu elementu w dół drzewa, dokonując zamian z jego większym z węzłów potomnych, aż do momentu, kiedy element znajdzie się na właściwej pozycji w strukturze kopca.
Zmniejszenie Klucza (Decrease Key)
Operacja ta polega na modyfikacji wartości danego elementu w kopcu maksymalnym w taki sposób, aby ją zmniejszyć. Po zmniejszeniu wartości elementu konieczne jest przywrócenie struktury kopca przy pomocy operacji bubble up, aby zapewnić, że element zachowa właściwą relację z węzłami potomnymi.
Zwiększenie Klucza (Increase Key)
W tym przypadku modyfikujemy wartość elementu kopca maksymalnego, zwiększając ją. Wymaga to przywrócenia struktury kopca z wykorzystaniem operacji bubble down, aby zagwarantować, że element pozostanie w odpowiedniej relacji z węzłami potomnymi.
Usuwanie (Delete)
Operacja ta umożliwia usunięcie wybranego elementu z kopca maksymalnego. W pierwszej kolejności obniżamy wartość elementu do ujemnej nieskończoności za pomocą operacji decrease key, a następnie stosujemy operację extract max, aby całkowicie usunąć element z drzewa.
Implementacja w języku Java
Poniżej przedstawiono przykładowy kod implementujący kopiec maksymalny w języku 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("Nowa wartość musi być mniejsza lub równa aktualnej wartości.");
}
heap[index] = value;
bubbleUp(index);
}
public void increaseKey(int index, int value) {
if (value < heap[index]) {
throw new IllegalArgumentException("Nowa wartość musi być większa lub równa aktualnej wartości.");
}
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 kopca maksymalnego
Kopiec maksymalny znajduje szerokie zastosowanie w wielu obszarach, w tym:
- Sortowanie elementów w porządku malejącym (sortowanie przez kopcowanie).
- Wyszukiwanie elementu o największej wartości.
- Selekcja k największych elementów z danego zbioru.
- Obliczanie mediany w strumieniu danych.
Podsumowanie
Kopiec maksymalny to efektywna struktura danych, która pozwala na szybkie wyszukiwanie i wybieranie elementów o największej wartości. Implementacja kopca maksymalnego w języku Java jest stosunkowo prosta i może być używana w wielu różnych zastosowaniach, takich jak sortowanie, wyszukiwanie i wybór elementów o najwyższej wartości.
Najczęściej zadawane pytania
1. Czym jest kopiec maksymalny (max heap)?
Kopiec maksymalny to rodzaj struktury danych opartej na drzewie binarnym, gdzie każdy węzeł posiada wartość większą lub równą wartościom swoich węzłów potomnych.
2. Jakie operacje najczęściej wykonuje się na kopcu maksymalnym?
Najczęściej wykorzystywane operacje to: wstawianie (insert), pobieranie maksimum (extract max), zmniejszanie klucza (decrease key), zwiększanie klucza (increase key) oraz usuwanie (delete).
3. Na czym polega operacja „przesuwania w górę” (bubble up)?
Operacja bubble up polega na przemieszczaniu elementu w górę drzewa poprzez zamianę jego pozycji z węzłem nadrzędnym, aż do osiągnięcia właściwego miejsca w strukturze kopca.
4. Na czym polega operacja „przesuwania w dół” (bubble down)?
Bubble down to operacja polegająca na przemieszczaniu elementu w dół drzewa poprzez zamiany z większym z jego węzłów potomnych, aż do momentu, gdy znajdzie się on na odpowiedniej pozycji w strukturze kopca.
5. Jak zaimplementować kopiec maksymalny w języku Java?
Aby utworzyć kopiec maksymalny w Javie, można użyć tablicy do reprezentowania drzewa binarnego, a podczas wykonywania operacji takich jak wstawianie, pobieranie maksimum, czy zmniejszanie klucza, należy przestrzegać zasad struktury kopca maksymalnego.
6. Jakie są zastosowania kopca maksymalnego?
Kopiec maksymalny jest często stosowany w algorytmach, takich jak sortowanie przez kopcowanie, tworzenie kolejek priorytetowych oraz wybór elementów o najwyższej wartości.
7. Jak za pomocą kopca maksymalnego posortować elementy w porządku malejącym?
Aby posortować elementy w porządku malejącym, możemy wykorzystać kopiec maksymalny i powtarzać operację pobierania maksimum (extract max) do momentu, gdy kopiec pozostanie pusty.
8. Jak znaleźć element o największej wartości w kopcu maksymalnym?
Element o największej wartości w kopcu maksymalnym jest zawsze umieszczony w korzeniu drzewa.
9. Jaka jest złożoność obliczeniowa operacji na kopcu maksymalnym?
Operacje na kopcu maksymalnym, takie jak wstawianie, pobieranie maksimum, czy zmniejszanie klucza, charakteryzują się złożonością czasową rzędu O(log n), gdzie n oznacza liczbę elementów w kopcu.
newsblog.pl