what is heap data structure java
W tym samouczku wyjaśniono, czym jest struktura danych sterty Java i powiązane koncepcje, takie jak Min Heap, Max Heap, Heap Sort, Stack vs Heap z przykładami:
Sterta to specjalna struktura danych w Javie. Sterta jest strukturą danych opartą na drzewie i można ją sklasyfikować jako pełne drzewo binarne. Wszystkie węzły sterty są ułożone w określonej kolejności.
=> Odwiedź tutaj, aby zobaczyć serię szkoleń Java dla wszystkich
Czego się nauczysz:
- Struktura danych sterty w języku Java
- Stos Vs Heap w Javie
- Wniosek
Struktura danych sterty w języku Java
W strukturze danych sterty węzeł główny jest porównywany ze swoimi potomkami i porządkowany zgodnie z kolejnością. Więc jeśli a jest węzłem głównym, a b jest jego dzieckiem, to właściwość klucz (a)> = klucz (b) wygeneruje maksymalną stertę.
Powyższa relacja między węzłem głównym a węzłem podrzędnym jest nazywana „Właściwością sterty”.
W zależności od kolejności węzłów nadrzędny-podrzędny sterta ma zazwyczaj dwa typy:
# 1) Max-Heap :W Max-Heap klucz węzła głównego jest największym ze wszystkich kluczy w stercie. Należy się upewnić, że ta sama właściwość jest prawdą dla wszystkich poddrzew w stercie rekurencyjnie.
Poniższy diagram przedstawia przykładowy maksymalny stos. Zauważ, że węzeł główny jest większy niż jego dzieci.
# 2) Min-Heap :W przypadku sterty Min-Heap klucz węzła głównego jest najmniejszym lub minimalnym spośród wszystkich innych kluczy obecnych w stercie. Podobnie jak w Max heap, ta właściwość powinna być rekurencyjnie prawdziwa we wszystkich pozostałych poddrzewach w stercie.
Przykład, drzewa Min-sterty, pokazano poniżej. Jak widać, klucz główny jest najmniejszym ze wszystkich pozostałych kluczy w stercie.
Struktury danych sterty można używać w następujących obszarach:
- Sterty są głównie używane do wdrażania kolejek priorytetowych.
- W szczególności min-sterta może być używana do określania najkrótszych ścieżek między wierzchołkami na wykresie.
Jak już wspomniano, struktura danych sterty jest kompletnym drzewem binarnym, które spełnia właściwość sterty dla roota i dzieci. Ta sterta jest również nazywana jako sterta binarna .
Binary Heap
Sterta binarna spełnia następujące właściwości:
- Sterta binarna to kompletne drzewo binarne. W pełnym drzewie binarnym wszystkie poziomy z wyjątkiem ostatniego są całkowicie wypełnione. Na ostatnim poziomie klawisze są tak daleko, jak to możliwe.
- Spełnia właściwość sterty. Sterta binarna może mieć wartość max lub min-sterta, w zależności od właściwości sterty, którą spełnia.
Sterta binarna jest zwykle reprezentowana jako tablica. Ponieważ jest to kompletne drzewo binarne, można je łatwo przedstawić jako tablicę. Tak więc w reprezentacji tablicowej sterty binarnej elementem głównym będzie A [0], gdzie A jest tablicą używaną do reprezentowania sterty binarnej.
Więc ogólnie dla każdego ithwęzeł w binarnej reprezentacji tablicy sterty, A [i], możemy reprezentować indeksy innych węzłów, jak pokazano poniżej.
| A [(i-1) / 2] | Reprezentuje węzeł nadrzędny |
|---|---|
| Dostęp jest szybszy. | Wolniej niż stos. |
| A [(2 * i) +1] | Reprezentuje lewy węzeł podrzędny |
| A [(2 * i) +2] | Reprezentuje prawy węzeł podrzędny |
Rozważmy następujący stos binarny:
Tablica reprezentująca powyższą minimalną stertę binarną jest następująca:
Jak pokazano powyżej, przez stertę przechodzi się zgodnie z kolejność poziomu tzn. elementy są przemieszczane od lewej do prawej na każdym poziomie. Kiedy elementy na jednym poziomie są wyczerpane, przechodzimy do następnego poziomu.
Następnie zaimplementujemy stertę binarną w Javie.
Poniższy program demonstruje binarną stertę w Javie.
import java.util.*; class BinaryHeap { private static final int d= 2; private int[] heap; private int heapSize; //BinaryHeap constructor with default size public BinaryHeap(int capacity){ heapSize = 0; heap = new int[ capacity+1]; Arrays.fill(heap, -1); } //is heap empty? public boolean isEmpty(){ return heapSize==0; } //is heap full? public boolean isFull(){ return heapSize == heap.length; } //return parent private int parent(int i){ return (i-1)/d; } //return kth child private int kthChild(int i,int k){ return d*i +k; } //insert new element into the heap public void insert(int x){ if(isFull()) throw new NoSuchElementException('Heap is full, No space to insert new element'); heap[heapSize++] = x; heapifyUp(heapSize-1); } //delete an element from the heap at given position public int delete(int x){ if(isEmpty()) throw new NoSuchElementException('Heap is empty, No element to delete'); int key = heap[x]; heap[x] = heap[heapSize -1]; heapSize--; heapifyDown(x); return key; } //maintain heap property during insertion private void heapifyUp(int i) { int temp = heap[i]; while(i>0 && temp > heap[parent(i)]){ heap[i] = heap[parent(i)]; i = parent(i); } heap[i] = temp; } //maintain heap property during deletion private void heapifyDown(int i){ int child; int temp = heap[i]; while(kthChild(i, 1) heap[rightChild]?leftChild:rightChild; } //print the heap public void printHeap() { System.out.print('nHeap = '); for (int i = 0; i Wynik:
nHeap = 7 4 6 1 3 2 5
Min Heap w Javie
Min-sterta w Javie to kompletne drzewo binarne. W przypadku min-heap węzeł główny jest mniejszy niż wszystkie inne węzły w stercie. Ogólnie rzecz biorąc, kluczowa wartość każdego węzła wewnętrznego jest mniejsza lub równa jego węzłom podrzędnym.
Jeśli chodzi o tablicową reprezentację sterty min, jeśli węzeł jest przechowywany w pozycji „i”, to jego lewy węzeł potomny jest przechowywany na pozycji 2i + 1, a następnie prawy węzeł potomny znajduje się na pozycji 2i + 2. Pozycja (i-1) / 2 zwraca węzeł nadrzędny.
Poniżej wymienione są różne operacje obsługiwane przez min-heap.
# 1) Wstaw (): Początkowo nowy klucz jest dodawany na końcu drzewa. Jeśli klucz jest większy niż jego węzeł nadrzędny, zachowywana jest właściwość sterty. W przeciwnym razie musimy przejść klucz w górę, aby wypełnić właściwość sterty. Operacja wstawiania w sterty min zajmuje O (log n) czasu.
# 2) extractMin (): Ta operacja usuwa minimalny element ze sterty. Zauważ, że właściwość sterty powinna zostać zachowana po usunięciu elementu głównego (elementu min) ze sterty. Cała operacja zajmuje O (Logn).
# 3) getMin (): getMin () zwraca korzeń sterty, który jest jednocześnie elementem minimum. Ta operacja jest wykonywana w czasie O (1).
Poniżej podano przykładowe drzewo dla sterty Min.
Powyższy diagram przedstawia drzewo min-sterty. Widzimy, że korzeń drzewa jest minimalnym elementem w drzewie. Ponieważ korzeń znajduje się w położeniu 0, jego lewe dziecko znajduje się w 2 * 0 + 1 = 1, a prawe dziecko w 2 * 0 + 2 = 2.
Algorytm minimalnej sterty
Poniżej podano algorytm budowania minimalnej sterty.
procedure build_minheap Array Arr: of size N => array of elements { repeat for (i = N/2 ; i >= 1 ; i--) call procedure min_heapify (A, i); } procedure min_heapify (var A[ ] , var i, var N) { var left = 2*i; var right = 2*i+1; var smallest; if(left <= N and A[left] < A[ i ] ) smallest = left; else smallest = i; if(right <= N and A[right] < A[smallest] ) smallest = right; if(smallest != i) { swap A[ i ] and A[ smallest ]); call min_heapify (A, smallest,N); } }Implementacja sterty min w Javie
Stertę min możemy zaimplementować za pomocą tablicy lub kolejek priorytetowych. Implementacja min-sterty przy użyciu kolejek priorytetowych jest domyślną implementacją, ponieważ kolejka priorytetowa jest implementowana jako min-sterta.
Poniższy program Java implementuje stertę min przy użyciu tablic. Tutaj używamy reprezentacji tablicowej dla sterty, a następnie stosujemy funkcję heapify, aby zachować właściwość sterty każdego elementu dodanego do sterty. Na koniec wyświetlamy stertę.
class Min_Heap { private int[] HeapArray; private int size; private int maxsize; private static final int FRONT = 1; //constructor to initialize the HeapArray public Min_Heap(int maxsize) { this.maxsize = maxsize; this.size = 0; HeapArray = new int[this.maxsize + 1]; HeapArray[0] = Integer.MIN_VALUE; } // returns parent position for the node private int parent(int pos) { return pos / 2; } // returns the position of left child private int leftChild(int pos) { return (2 * pos); } // returns the position of right child private int rightChild(int pos) { return (2 * pos) + 1; } // checks if the node is a leaf node private boolean isLeaf(int pos) { if (pos >= (size / 2) && pos HeapArray[leftChild(pos)] || HeapArray[pos] > HeapArray[rightChild(pos)]) { // swap with left child and then heapify the left child if (HeapArray[leftChild(pos)] = maxsize) { return; } HeapArray[++size] = element; int current = size; while (HeapArray[current] = 1; pos--) { minHeapify(pos); } } // remove and return the heap elment public int remove() { int popped = HeapArray[FRONT]; HeapArray[FRONT] = HeapArray[size--]; minHeapify(FRONT); return popped; } } class Main{ public static void main(String[] arg) { //construct a min heap from given data System.out.println('The Min Heap is '); Min_Heap minHeap = new Min_Heap(7); minHeap.insert(12); minHeap.insert(15); minHeap.insert(30); minHeap.insert(40); minHeap.insert(50); minHeap.insert(90); minHeap.insert(45); minHeap.minHeap(); //display the min heap contents minHeap.display(); //display root node of the min heap System.out.println('The Min val(root node):' + minHeap.remove()); } } Wynik:
Max Heap w Javie
Maksymalna sterta jest również kompletnym drzewem binarnym. W sterty maksymalnej węzeł główny jest większy lub równy węzłom podrzędnym. Ogólnie rzecz biorąc, wartość dowolnego węzła wewnętrznego w maksymalnym stercie jest większa lub równa jego węzłom podrzędnym.
Podczas gdy max heap jest mapowany na tablicę, jeśli którykolwiek węzeł jest przechowywany w pozycji „i”, to jego lewy element potomny jest przechowywany w 2i +1, a prawy podrzędny w 2i + 2.
Typowa sterta Max będzie wyglądać tak, jak pokazano poniżej:
Na powyższym diagramie widzimy, że węzeł główny jest największy w stercie, a jego węzły potomne mają wartości mniejsze niż węzeł główny.
Podobnie jak min-sterta, maksymalna sterta może być również reprezentowana jako tablica.
Więc jeśli A jest tablicą reprezentującą stertę Max, to A [0] jest węzłem głównym. Podobnie, jeśli A [i] jest dowolnym węzłem na maksymalnym stercie, to poniżej znajdują się inne sąsiednie węzły, które można przedstawić za pomocą tablicy.
- A [(i-1) / 2] reprezentuje węzeł macierzysty A [i].
- A [(2i +1)] reprezentuje lewy węzeł potomny A [i].
- A [2i + 2] zwraca prawy węzeł potomny A [i].
Poniżej podano operacje, które można wykonać na Max Heap.
# 1) Wstaw: Operacja wstawiania wstawia nową wartość w drzewie maksymalnego sterty. Jest wstawiany na końcu drzewa. Jeśli nowy klucz (wartość) jest mniejszy niż jego węzeł nadrzędny, zachowywana jest właściwość sterty. W przeciwnym razie drzewo musi zostać uformowane na stosie, aby zachować właściwość sterty.
Złożoność czasowa operacji wstawiania wynosi O (log n).
# 2) ExtractMax: Operacja ExtractMax usuwa maksymalny element (root) z maksymalnego sterty. Operacja tworzy również stertę maksymalną, aby zachować właściwość sterty. Złożoność czasowa tej operacji wynosi O (log n).
# 3) getMax: Operacja getMax zwraca węzeł główny maksymalnego sterty o złożoności czasowej O (1).
Poniższy program Java implementuje stertę maksymalną. Używamy tutaj ArrayList do reprezentowania maksymalnych elementów sterty.
import java.util.ArrayList; class Heap { void heapify(ArrayList hT, int i) { int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) { int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); } } void insert(ArrayList hT, int newNum) { int size = hT.size(); if (size == 0) { hT.add(newNum); } else { hT.add(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } void deleteNode(ArrayList hT, int num) { int size = hT.size(); int i; for (i = 0; i = 0; j--) { heapify(hT, j); } } void printArray(ArrayList array, int size) { for (Integer i : array) { System.out.print(i + ' '); } System.out.println(); } } class Main{ public static void main(String args[]) { ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println('Max-Heap array: '); h.printArray(array, size); h.deleteNode(array, 4); System.out.println('After deleting an element: '); h.printArray(array, size); } } Wynik:
Min sterta kolejki priorytetowej w Javie
Struktura danych kolejki priorytetowej w Javie może być bezpośrednio używana do reprezentowania sterty min. Domyślnie kolejka priorytetowa implementuje min-heap.
Poniższy program demonstruje minimalną stertę w Javie przy użyciu Priority Queue.
import java.util.*; class Main { public static void main(String args[]) { // Create priority queue object PriorityQueue pQueue_heap = new PriorityQueue(); // Add elements to the pQueue_heap using add() pQueue_heap.add(100); pQueue_heap.add(30); pQueue_heap.add(20); pQueue_heap.add(40); // Print the head (root node of min heap) using peek method System.out.println('Head (root node of min heap):' + pQueue_heap.peek()); // Print min heap represented using PriorityQueue System.out.println('
Min heap as a PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // remove head (root of min heap) using poll method pQueue_heap.poll(); System.out.println('
Min heap after removing root node:'); //print the min heap again Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } Wynik:
Maksymalna sterta kolejki priorytetowej w Javie
Aby przedstawić maksymalną stertę w Javie za pomocą kolejki Priority, musimy użyć Collections.reverseOrder do odwrócenia min-sterty. Kolejka priorytetowa bezpośrednio reprezentuje minimalną stertę w Javie.
Zaimplementowaliśmy Max Heap za pomocą kolejki Priority w poniższym programie.
import java.util.*; class Main { public static void main(String args[]) { // Create empty priority queue //with Collections.reverseOrder to represent max heap PriorityQueue pQueue_heap = new PriorityQueue(Collections.reverseOrder()); // Add items to the pQueue using add() pQueue_heap.add(10); pQueue_heap.add(90); pQueue_heap.add(20); pQueue_heap.add(40); // Printing all elements of max heap System.out.println('The max heap represented as PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // Print the highest priority element (root of max heap) System.out.println('
Head value (root node of max heap):' + pQueue_heap.peek()); // remove head (root node of max heap) with poll method pQueue_heap.poll(); //print the max heap again System.out.println('
Max heap after removing root: '); Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } Wynik:
Sortowanie na stosie w języku Java
Sortowanie na stosie jest techniką sortowania porównawczego podobną do sortowania przez wybór, w której dla każdej iteracji wybieramy maksymalny element tablicy. Sortowanie na stosie wykorzystuje strukturę danych Heap i sortuje elementy, tworząc minimalną lub maksymalną stertę z elementów tablicy do sortowania.
Omówiliśmy już, że w sterty min i max węzeł główny zawiera odpowiednio minimalny i maksymalny element tablicy. W przypadku sortowania na stosie element główny sterty (min lub max) jest usuwany i przenoszony do posortowanej tablicy. Pozostała sterta jest następnie składowana w celu utrzymania właściwości sterty.
Musimy więc wykonać dwa kroki rekurencyjnie, aby posortować podaną tablicę za pomocą sortowania stosu.
- Zbuduj stertę z podanej tablicy.
- Kilkakrotnie usuń element główny ze sterty i przenieś go do posortowanej tablicy. Usyp pozostałą stertę.
We wszystkich przypadkach złożoność czasowa sortowania stosu wynosi O (n log n). Złożoność przestrzeni wynosi O (1).
Algorytm sortowania sterty w Javie
Poniżej podano algorytmy sortowania stosu do sortowania podanej tablicy w porządku rosnącym i malejącym.
# 1) Algorytm sortowania stosu do sortowania w porządku rosnącym:
- Utwórz maksymalną stertę dla danej tablicy do posortowania.
- Usuń element główny (maksymalna wartość w tablicy wejściowej) i przenieś go do posortowanej tablicy. Umieść ostatni element tablicy w katalogu głównym.
- Przygotuj nowy katalog główny sterty.
- Powtarzaj kroki 1 i 2, aż cała tablica zostanie posortowana.
# 2) Algorytm sortowania stosu do sortowania w porządku malejącym:
- Skonstruuj min Heap dla podanej tablicy.
- Usuń rdzeń (minimalna wartość w tablicy) i zamień go na ostatni element tablicy.
- Przygotuj nowy katalog główny sterty.
- Powtarzaj kroki 1 i 2, aż cała tablica zostanie posortowana.
Implementacja sortowania na stosie w Javie
Poniższy program Java używa sortowania stosu do sortowania tablicy w porządku rosnącym. W tym celu najpierw konstruujemy maksymalną stertę, a następnie rekurencyjnie wymieniamy i stosujemy element główny, jak określono w powyższym algorytmie.
import java.util.*; class HeapSort{ public void heap_sort(int heap_Array[]) { int heap_len = heap_Array.length; // construct max heap for (int i = heap_len / 2 - 1; i >= 0; i--) { heapify(heap_Array, heap_len, i); } // Heap sort for (int i = heap_len - 1; i >= 0; i--) { int temp = heap_Array[0]; heap_Array[0] = heap_Array[i]; heap_Array[i] = temp; // Heapify root element heapify(heap_Array, i, 0); } } void heapify(int heap_Array[], int n, int i) { // find largest value int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left heap_Array[largest]) largest = left; if (right heap_Array[largest]) largest = right; // recursively heapify and swap if root is not the largest if (largest != i) { int swap = heap_Array[i]; heap_Array[i] = heap_Array[largest]; heap_Array[largest] = swap; heapify(heap_Array, n, largest); } } } class Main{ public static void main(String args[]) { //define input array and print it int heap_Array[] = {6,2,9,4,10,15,1,13}; System.out.println('Input Array:' + Arrays.toString(heap_Array)); //call HeapSort method for given array HeapSort hs = new HeapSort(); hs.heap_sort(heap_Array); //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(heap_Array)); } } Wynik:
Całkowita złożoność czasowa techniki sortowania na stosie wynosi O (nlogn). Złożoność czasowa techniki heapify wynosi O (logn). Podczas gdy złożoność czasowa budowy hałdy wynosi O (n).
Stos Vs Heap w Javie
Przedstawmy teraz tabelarycznie niektóre różnice między strukturą danych stosu a stertą.
Stos Sterta Stos to liniowa struktura danych. Sterta to hierarchiczna struktura danych. Zgodnie z kolejnością LIFO (Last In, First Out). Przemieszczanie jest w kolejności poziomów. Używany głównie do przydzielania pamięci statycznej. Używany do dynamicznej alokacji pamięci. Pamięć jest przydzielana w sposób ciągły. Pamięć jest przydzielana w losowych lokalizacjach. Rozmiar stosu jest ograniczony w zależności od systemu operacyjnego. System operacyjny nie wymusza żadnych ograniczeń rozmiaru sterty. Stos ma dostęp tylko do zmiennych lokalnych. Sterta ma przypisane zmienne globalne. Alokacja / zwalnianie pamięci odbywa się automatycznie. Przydział / cofnięcie alokacji musi zostać wykonany ręcznie przez programistę. Stos można zaimplementować za pomocą Arrays, Linked List, ArrayList itp. Lub dowolnych innych liniowych struktur danych. Sterta jest implementowana przy użyciu tablic lub drzew. Koszt utrzymania, jeśli mniej. Bardziej kosztowne w utrzymaniu. Może powodować niedobór pamięci, ponieważ pamięć jest ograniczona. Nie brakuje pamięci, ale może cierpieć z powodu fragmentacji pamięci.
Często Zadawane Pytania
P # 1) Czy stack jest szybszy niż Heap?
Odpowiedź: Stos jest szybszy niż sterta, ponieważ dostęp jest liniowy w porównaniu ze stertą.
P # 2) Do czego służy sterta?
Odpowiedź: Sterta jest najczęściej używana w algorytmach, które znajdują minimalną lub najkrótszą ścieżkę między dwoma punktami, takich jak algorytm Dijkstry, do sortowania za pomocą sortowania sterty, do implementacji kolejki priorytetowej (min-sterta) itp.
P # 3) Co to jest sterta? Jakie są jego rodzaje?
Odpowiedź: Sterta to hierarchiczna struktura danych oparta na drzewie. Sterta to kompletne drzewo binarne. Sterty są dwojakiego rodzaju, tj. Sterta maksymalna, w której węzeł główny jest największy ze wszystkich węzłów; Sterta minimalna, w której węzeł główny jest najmniejszym lub minimalnym spośród wszystkich kluczy.
P # 4) Jakie są zalety Heap w porównaniu ze stosem?
darmowy program do tworzenia kopii zapasowych dla systemu Windows 7
Odpowiedź: Główną zaletą sterty nad stosem jest sterta, pamięć jest alokowana dynamicznie, a zatem nie ma ograniczeń co do ilości pamięci, którą można wykorzystać. Po drugie, na stosie można alokować tylko zmienne lokalne, podczas gdy możemy również alokować zmienne globalne na stercie.
P # 5) Czy Heap może mieć duplikaty?
Odpowiedź: Tak, nie ma ograniczeń co do posiadania węzłów ze zduplikowanymi kluczami w stercie, ponieważ sterta jest kompletnym drzewem binarnym i nie spełnia właściwości drzewa wyszukiwania binarnego.
Wniosek
W tym samouczku omówiliśmy typy sterty i sortowania sterty przy użyciu typów sterty. Widzieliśmy również szczegółową implementację jego typów w Javie.
=> Sprawdź idealny przewodnik szkoleniowy języka Java tutaj.
rekomendowane lektury
- Java Graph Tutorial - Jak zaimplementować strukturę danych grafowych
- Wprowadzenie do struktur danych w C ++
- Sortuj na stosie w C ++ z przykładami
- Struktura danych drzewa AVL i sterty w C ++
- Struktura danych drzewa binarnego w C ++
- Struktura danych kolejki w C ++ z ilustracjami
- Struktura danych listy połączonej cyklicznie w C ++ z ilustracją
- Podstawy języka Java: składnia języka Java, klasa języka Java i podstawowe pojęcia dotyczące języka Java
