Struktura danych sterty

W tym samouczku dowiesz się, czym jest struktura danych sterty. Znajdziesz również działające przykłady operacji na stertach w językach C, C ++, Java i Python.

Struktura danych sterty jest kompletnym drzewem binarnym, które spełnia właściwość sterty . Jest również nazywany stertą binarną .

Kompletne drzewo binarne to specjalne drzewo binarne, w którym

  • każdy poziom, z wyjątkiem ostatniego, jest wypełniony
  • wszystkie węzły są tak daleko, jak to możliwe

Właściwość sterty to właściwość węzła, w którym

  • (dla maksymalnego sterty) klucz każdego węzła jest zawsze większy niż jego węzeł / węzły potomne, a klucz węzła głównego jest największy spośród wszystkich innych węzłów;
  • (dla sterty minimalnej) klucz każdego węzła jest zawsze mniejszy niż węzeł / węzły potomne, a klucz węzła głównego jest najmniejszy spośród wszystkich innych węzłów.

Operacje na stercie

Poniżej opisano niektóre z ważnych operacji wykonywanych na stercie wraz z ich algorytmami.

Heapify

Heapify to proces tworzenia struktury danych sterty z drzewa binarnego. Służy do tworzenia sterty minimalnej lub maksymalnej.

  1. Niech tablica wejściowa będzie
  2. Utwórz pełne drzewo binarne z tablicy
  3. Zacznij od pierwszego indeksu węzła nie będącego liściem, którego indeks jest określony przez n/2 - 1.
  4. Ustaw bieżący element ijako largest.
  5. Indeks lewego dziecka jest podawany przez, 2i + 1a prawe dziecko przez 2i + 2.
    Jeśli leftChildjest większe niż currentElement(tj. Element w ithindeksie), ustaw leftChildIndexjako największe.
    Jeśli rightChildjest większe niż element w largest, ustaw rightChildIndexjako largest.
  6. Zamień largestzcurrentElement
  7. Powtarzaj kroki 3-7, aż poddrzewa również zostaną ułożone w stos.

Algorytm

 Heapify(array, size, i) set i as largest leftChild = 2i + 1 rightChild = 2i + 2 if leftChild > array(largest) set leftChildIndex as largest if rightChild > array(largest) set rightChildIndex as largest swap array(i) and array(largest)

Aby utworzyć Max-Heap:

 MaxHeap(array, size) loop from the first index of non-leaf node down to zero call heapify

W przypadku sterty Min-Heap oba leftChildi rightChildmuszą być mniejsze niż element nadrzędny dla wszystkich węzłów.

Wstaw element do sterty

Algorytm wstawiania w Max Heap

 If there is no node, create a newNode. else (a node is already present) insert the newNode at the end (last node from left to right.) heapify the array
  1. Wstaw nowy element na końcu drzewka.
  2. Ułóż drzewo.

W przypadku sterty minimalnej powyższy algorytm jest modyfikowany tak, aby parentNodebył zawsze mniejszy niż newNode.

Usuń element ze sterty

Algorytm usuwania w Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Wybierz element do usunięcia.
  2. Zamień go z ostatnim elementem.
  3. Usuń ostatni element.
  4. Ułóż drzewo.

W przypadku sterty minimalnej powyższy algorytm jest modyfikowany tak, że oba childNodessą większe niż currentNode.

Peek (Find max / min)

Operacja Peek zwraca maksymalny element z Max Heap lub minimalny element z Min Heap bez usuwania węzła.

Zarówno dla sterty Max, jak i sterty min

 zwraca rootNode

Wyciąg-Max / Min

Extract-Max zwraca węzeł z maksymalną wartością po usunięciu go z Max Heap, natomiast Extract-Min zwraca węzeł z minimum po usunięciu go z Min Heap.

Przykłady w Pythonie, Javie, C / C ++

Python Java C C ++ 
 # Max-Heap data structure in Python def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r if largest != i: arr(i),arr(largest) = arr(largest),arr(i) heapify(arr, n, largest) def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum); for i in range((size//2)-1, -1, -1): heapify(array, size, i) def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size-1) = array(size-1), array(i) array.remove(num) for i in range((len(array)//2)-1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr)) 
  // Max-Heap data structure in Java 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(); ) 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); ) )
 // Max-Heap data structure in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) void deleteRoot(int array(), int num) ( int i; for (i = 0; i  = 0; i--) ( heapify(array, size, i); ) ) void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); ) 
 // Max-Heap data structure in C++ #include #include using namespace std; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(vector &hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i  = 0; i--) ( heapify(hT, i); ) ) void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )

Aplikacje struktury danych sterty

  • Sterta jest używana podczas implementowania kolejki priorytetowej.
  • Algorytm Dijkstry
  • Sortowanie na stosie

Interesujące artykuły...