A Maksymalny stos jest zdefiniowany jako rodzaj Struktura danych sterty to rodzaj drzewa binarnego powszechnie stosowanego w informatyce do różnych celów, w tym do sortowania, wyszukiwania i organizowania danych.

Wprowadzenie do struktury danych Max-Heap

Cel i przypadki użycia Max-Heap:

• Kolejka priorytetowa: Jednym z głównych zastosowań struktury danych sterty jest implementacja kolejek priorytetowych.
• Sortowanie sterty: Struktura danych sterty jest również wykorzystywana w algorytmach sortowania.
• Zarządzanie pamięcią: Struktura danych sterty jest również wykorzystywana w zarządzaniu pamięcią. Kiedy program musi dynamicznie przydzielać pamięć, wykorzystuje strukturę danych sterty do śledzenia dostępnej pamięci.
• Algorytm najkrótszej ścieżki Dijkstry wykorzystuje strukturę danych sterty do śledzenia wierzchołków o najkrótszej ścieżce od wierzchołka źródłowego.

Struktura danych Max-Heap w różnych językach:

1. Max-Heap w C++

Maksymalną stertę można zaimplementować za pomocą metody kolejka priorytetowa pojemnik z Standardowa biblioteka szablonów (STL) . The kolejka priorytetowa kontener to typ adaptera kontenera, który umożliwia przechowywanie elementów w strukturze danych przypominającej kolejkę, w której każdy element ma przypisany priorytet.

  Synt  ax: priority_queuemaxH;>

2. Max-Heap w Javie

W Javie maksymalną stertę można zaimplementować za pomocą metody Kolejka priorytetowa klasa od pakiet java.util . Klasa PriorityQueue to kolejka priorytetowa, która umożliwia przechowywanie elementów w strukturze danych przypominającej kolejkę, w której każdy element ma powiązany z nim priorytet.

  Syntax  : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());>

3. Max-Heap w Pythonie

W Pythonie maksymalną stertę można zaimplementować za pomocą metody sterta moduł, który udostępnia funkcje implementujące sterty. W szczególności moduł heapq umożliwia tworzenie struktur danych sterty i manipulowanie nimi.

  Synt  ax: heap = []  heapify(heap)>

4. Maksymalna sterta w C#

W języku C# maksymalną stertę można zaimplementować przy użyciu klasy PriorityQueue z pliku System.Collections.Generic przestrzeń nazw . Klasa PriorityQueue to kolejka priorytetowa, która umożliwia przechowywanie elementów w strukturze danych przypominającej kolejkę, w której każdy element ma powiązany z nim priorytet.

  Syntax:   var maxHeap = new PriorityQueue((a, b) =>b - a);>

5. Max-Heap w JavaScript

Maksymalna sterta to drzewo binarne, w którym każdy węzeł ma wartość większą lub równą swoim dzieciom. W JavaScript możesz zaimplementować maksymalną stertę za pomocą tablicy, gdzie pierwszy element reprezentuje węzeł główny, a dzieci węzła o indeksie I znajdują się na indeksach 2i+1 I 2i+2.

Syntax: const miaxHeap = new MaxHeap();>

Różnica między maksymalną i minimalną stertą

	Min. sterta	Maksymalna sterta
1.	W Min-Heap klucz obecny w węźle głównym musi być mniejszy lub równy spośród kluczy obecnych u wszystkich jego dzieci.	W Max-Heap klucz obecny w węźle głównym musi być większy lub równy spośród kluczy obecnych u wszystkich jego dzieci.
2.	W Min-Heap minimalny kluczowy element obecny w katalogu głównym.	W Max-Heap maksymalny kluczowy element obecny w katalogu głównym.
3.	Min-Heap używa rosnącego priorytetu.	Max-Heap używa malejącego priorytetu.
4.	W konstrukcji Min-Heap priorytet ma najmniejszy element.	W konstrukcji Max-Heap priorytet ma największy element.
5.	W Min-Heap najmniejszy element jest pierwszym, który zostanie wyrzucony ze sterty.	W Max-Heap największy element jest pierwszym, który zostanie wyrzucony ze sterty.

Wewnętrzna implementacja struktury danych Max-Heap:

A Minimalna sterta jest zwykle reprezentowana jako tablica .

• Element główny będzie w Arr[0] .
• Dla dowolnego i-węzła Arr[i].
  • lewe dziecko jest przechowywane w indeksie 2i+1
  • Prawe dziecko jest przechowywane w indeksie 2i+2
  • Rodzic jest przechowywany na poziomie indeksu ((i-1)/2)

Wewnętrzna implementacja Max-Heap wymaga 3 głównych kroków:

1. Wprowadzenie : Aby wstawić nowy element do sterty, jest on dodawany na końcu tablicy, a następnie przesuwany w górę, aż spełni wymagania właściwości sterty.
2. Usunięcie : Aby usunąć maksymalny element (korzeń sterty), ostatni element tablicy jest zamieniany z pierwiastkiem, a nowy pierwiastek jest usuwany aż do spełnienia właściwości sterty.
3. Zgromadź : Operacji heapify można użyć do utworzenia maksymalnej sterty z nieposortowanej tablicy.

Operacje na strukturze danych Max-heap i ich implementacja:

Oto kilka typowych operacji, które można wykonać na strukturze danych Heap Data Structure:

1. Wstawienie do struktury danych Max-Heap :

Elementy można wstawiać na stertę, stosując podobne podejście, jak omówiono powyżej w przypadku usuwania. Pomysł jest taki:

• Najpierw zwiększ rozmiar sterty o 1, aby mógł przechowywać nowy element.
• Wstaw nowy element na końcu sterty.
• Ten nowo wstawiony element może zniekształcić właściwości Heap dla jego rodziców. Zatem, aby zachować właściwości sterty, przechowaj nowo wstawiony element na stosie, stosując podejście oddolne.

Ilustracja:

Załóżmy, że sterta jest stertą maksymalną jako:

Wstawienie do sterty Max

Implementacja operacji wstawiania w Max-Heap:

C++

ogranicznik Java

// C++ program to insert new element to Heap> #include> using> namespace> std;> #define MAX 1000 // Max size of Heap> // Function to heapify ith node in a Heap> // of size n following a Bottom-up approach> void> heapify(>int> arr[],>int> n,>int> i)> {> >// Find parent> >int> parent = (i - 1) / 2;> >if> (arr[parent]>0) {> >// For Max-Heap> >// If current node is greater than its parent> >// Swap both of them and call heapify again> >// for the parent> >if> (arr[i]>arr[nadrzędny]) {> >swap(arr[i], arr[parent]);> >// Recursively heapify the parent node> >heapify(arr, n, parent);> >}> >}> }> // Function to insert a new node to the Heap> void> insertNode(>int> arr[],>int>& n,>int> Key)> {> >// Increase the size of Heap by 1> >n = n + 1;> >// Insert the element at end of Heap> >arr[n - 1] = Key;> >// Heapify the new node following a> >// Bottom-up approach> >heapify(arr, n, n - 1);> }> // A utility function to print array of size n> void> printArray(>int> arr[],>int> n)> {> >for> (>int> i = 0; i cout << arr[i] << ' '; cout << ' '; } // Driver Code int main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[MAX] = { 10, 5, 3, 2, 4 }; int n = 5; int key = 15; insertNode(arr, n, key); printArray(arr, n); // Final Heap will be: // 15 // / // 5 10 // / / // 2 4 3 return 0; }>

>

>

Jawa

// Java program for implementing insertion in Heaps> public> class> insertionHeap {> >// Function to heapify ith node in a Heap> >// of size n following a Bottom-up approach> >static> void> heapify(>int>[] arr,>int> n,>int> i)> >{> >// Find parent> >int> parent = (i ->1>) />2>;> > >if> (arr[parent]>>0>) {> >// For Max-Heap> >// If current node is greater than its parent> >// Swap both of them and call heapify again> >// for the parent> >if> (arr[i]>arr[nadrzędny]) {> > >// swap arr[i] and arr[parent]> >int> temp = arr[i];> >arr[i] = arr[parent];> >arr[parent] = temp;> > >// Recursively heapify the parent node> >heapify(arr, n, parent);> >}> >}> >}> >// Function to insert a new node to the heap.> >static> int> insertNode(>int>[] arr,>int> n,>int> Key)> >{> >// Increase the size of Heap by 1> >n = n +>1>;> > >// Insert the element at end of Heap> >arr[n ->1>] = Key;> > >// Heapify the new node following a> >// Bottom-up approach> >heapify(arr, n, n ->1>);> > >// return new size of Heap> >return> n;> >}> >/* A utility function to print array of size n */> >static> void> printArray(>int>[] arr,>int> n)> >{> >for> (>int> i =>0>; i System.out.println(arr[i] + ' '); System.out.println(); } // Driver Code public static void main(String args[]) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 // maximum size of the array int MAX = 1000; int[] arr = new int[MAX]; // initializing some values arr[0] = 10; arr[1] = 5; arr[2] = 3; arr[3] = 2; arr[4] = 4; // Current size of the array int n = 5; // the element to be inserted int Key = 15; // The function inserts the new element to the heap and // returns the new size of the array n = insertNode(arr, n, Key); printArray(arr, n); // Final Heap will be: // 15 // / // 5 10 // / / // 2 4 3 } } // The code is contributed by Gautam goel>

>

>

C#

// C# program for implementing insertion in Heaps> using> System;> public> class> insertionHeap {> >// Function to heapify ith node in a Heap of size n following a Bottom-up approach> >static> void> heapify(>int>[] arr,>int> n,>int> i) {> >// Find parent> >int> parent = (i - 1) / 2;> >if> (arr[parent]>0) {> >// For Max-Heap> >// If current node is greater than its parent> >// Swap both of them and call heapify again> >// for the parent> >if> (arr[i]>arr[nadrzędny]) {> >// swap arr[i] and arr[parent]> >int> temp = arr[i];> >arr[i] = arr[parent];> >arr[parent] = temp;> >// Recursively heapify the parent node> >heapify(arr, n, parent);> >}> >}> >}> >// Function to insert a new node to the heap.> >static> int> insertNode(>int>[] arr,>int> n,>int> Key) {> >// Increase the size of Heap by 1> >n = n + 1;> >// Insert the element at end of Heap> >arr[n - 1] = Key;> >// Heapify the new node following a> >// Bottom-up approach> >heapify(arr, n, n - 1);> >// return new size of Heap> >return> n;> >}> >/* A utility function to print array of size n */> >static> void> printArray(>int>[] arr,>int> n) {> >for> (>int> i = 0; i Console.WriteLine(arr[i] + ' '); Console.WriteLine(''); } public static void Main(string[] args) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 // maximum size of the array int MAX = 1000; int[] arr = new int[MAX]; // initializing some values arr[0] = 10; arr[1] = 5; arr[2] = 3; arr[3] = 2; arr[4] = 4; // Current size of the array int n = 5; // the element to be inserted int Key = 15; // The function inserts the new element to the heap and // returns the new size of the array n = insertNode(arr, n, Key); printArray(arr, n); // Final Heap will be: // 15 // / // 5 10 // / / // 2 4 3 } } // This code is contributed by ajaymakvana.>

>

>

JavaScript

// Javascript program for implement insertion in Heaps> // To heapify a subtree rooted with node i which is> // an index in arr[].Nn is size of heap> let MAX = 1000;> // Function to heapify ith node in a Heap of size n following a Bottom-up approach> function> heapify(arr, n, i)> {> >// Find parent> >let parent = Math.floor((i-1)/2);> >if> (arr[parent]>= 0) {> >// For Max-Heap> >// If current node is greater than its parent> >// Swap both of them and call heapify again> >// for the parent> >if> (arr[i]>arr[nadrzędny]) {> >let temp = arr[i];> >arr[i] = arr[parent];> >arr[parent] = temp;> >// Recursively heapify the parent node> >heapify(arr, n, parent);> >}> >}> }> // Function to insert a new node to the Heap> function> insertNode(arr, n, Key)> {> >// Increase the size of Heap by 1> >n = n + 1;> >// Insert the element at end of Heap> >arr[n - 1] = Key;> >// Heapify the new node following a> >// Bottom-up approach> >heapify(arr, n, n - 1);> > >return> n;> }> /* A utility function to print array of size N */> function> printArray(arr, n)> {> >for> (let i = 0; i console.log(arr[i] + ' '); console.log(''); } let arr = [ 10, 5, 3, 2, 4 ]; let n = arr.length; let key = 15; n = insertNode(arr, n, key); printArray(arr, n); // This code is contributed by ajaymakvana>

>

>

Python3

# program to insert new element to Heap> # Function to heapify ith node in a Heap> # of size n following a Bottom-up approach> def> heapify(arr, n, i):> >parent>=> int>(((i>->1>)>/>2>))> ># For Max-Heap> ># If current node is greater than its parent> ># Swap both of them and call heapify again> ># for the parent> >if> arr[parent]>>0>:> >if> arr[i]>arr[nadrzędny]:> >arr[i], arr[parent]>=> arr[parent], arr[i]> ># Recursively heapify the parent node> >heapify(arr, n, parent)> # Function to insert a new node to the Heap> def> insertNode(arr, key):> >global> n> ># Increase the size of Heap by 1> >n>+>=> 1> ># Insert the element at end of Heap> >arr.append(key)> ># Heapify the new node following a> ># Bottom-up approach> >heapify(arr, n, n>->1>)> # A utility function to print array of size n> def> printArr(arr, n):> >for> i>in> range>(n):> >print>(arr[i], end>=>' '>)> # Driver Code> # Array representation of Max-Heap> '''> >10> >/> >5 3> >/> >2 4> '''> arr>=> [>10>,>5>,>3>,>2>,>4>,>1>,>7>]> n>=> 7> key>=> 15> insertNode(arr, key)> printArr(arr, n)> # Final Heap will be:> '''> >15> >/> 5 10> / /> 2 4 3> Code is written by Rajat Kumar....> '''>

>

>

Wyjście

15 5 10 2 4 3>

Złożoność czasowa: O(log(n)) ( gdzie n jest liczbą elementów na stercie )
Przestrzeń pomocnicza: NA)

2. Usunięcie struktury danych Max-Heap :

Usunięcie elementu z dowolnej pośredniej pozycji sterty może być kosztowne, dlatego możemy po prostu zastąpić usuwany element ostatnim elementem i usunąć ostatni element sterty.

• Zastąp korzeń lub element do usunięcia ostatnim elementem.
• Usuń ostatni element ze sterty.
• Ponieważ ostatni element jest teraz umieszczony w pozycji węzła głównego. Może więc nie być zgodny z właściwością sterty. Dlatego złóż ostatni węzeł umieszczony w miejscu korzenia.

Ilustracja :

Załóżmy, że sterta jest stertą maksymalną jako:

Struktura danych maksymalnej sterty

Elementem do usunięcia jest root, czyli 10.

Proces :

Ostatnim elementem jest 4.

Krok 1: Zamień ostatni element na root i usuń go.

Maksymalna sterta

Krok 2 : Obsyp korzeń.

Ostatnia sterta:

Maksymalna sterta

Implementacja operacji usuwania w Max-Heap:

C++

// C++ program for implement deletion in Heaps> #include> using> namespace> std;> // To heapify a subtree rooted with node i which is> // an index of arr[] and n is the size of heap> void> heapify(>int> arr[],>int> n,>int> i)> {> >int> largest = i;>// Initialize largest as root> >int> l = 2 * i + 1;>// left = 2*i + 1> >int> r = 2 * i + 2;>// right = 2*i + 2> >// If left child is larger than root> >if> (l arr[largest])> >largest = l;> >// If right child is larger than largest so far> >if> (r arr[largest])> >largest = r;> >// If largest is not root> >if> (largest != i) {> >swap(arr[i], arr[largest]);> >// Recursively heapify the affected sub-tree> >heapify(arr, n, largest);> >}> }> // Function to delete the root from Heap> void> deleteRoot(>int> arr[],>int>& n)> {> >// Get the last element> >int> lastElement = arr[n - 1];> >// Replace root with last element> >arr[0] = lastElement;> >// Decrease size of heap by 1> >n = n - 1;> >// heapify the root node> >heapify(arr, n, 0);> }> /* A utility function to print array of size n */> void> printArray(>int> arr[],>int> n)> {> >for> (>int> i = 0; i cout << arr[i] << ' '; cout << ' '; } // Driver Code int main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[] = { 10, 5, 3, 2, 4 }; int n = sizeof(arr) / sizeof(arr[0]); deleteRoot(arr, n); printArray(arr, n); return 0; }>

>

zaczyna się od Javy

>

Jawa

// Java program for implement deletion in Heaps> public> class> deletionHeap {> >// To heapify a subtree rooted with node i which is> >// an index in arr[].Nn is size of heap> >static> void> heapify(>int> arr[],>int> n,>int> i)> >{> >int> largest = i;>// Initialize largest as root> >int> l =>2> * i +>1>;>// left = 2*i + 1> >int> r =>2> * i +>2>;>// right = 2*i + 2> >// If left child is larger than root> >if> (l arr[largest])> >largest = l;> >// If right child is larger than largest so far> >if> (r arr[largest])> >largest = r;> >// If largest is not root> >if> (largest != i) {> >int> swap = arr[i];> >arr[i] = arr[largest];> >arr[largest] = swap;> >// Recursively heapify the affected sub-tree> >heapify(arr, n, largest);> >}> >}> >// Function to delete the root from Heap> >static> int> deleteRoot(>int> arr[],>int> n)> >{> >// Get the last element> >int> lastElement = arr[n ->1>];> >// Replace root with first element> >arr[>0>] = lastElement;> >// Decrease size of heap by 1> >n = n ->1>;> >// heapify the root node> >heapify(arr, n,>0>);> >// return new size of Heap> >return> n;> >}> >/* A utility function to print array of size N */> >static> void> printArray(>int> arr[],>int> n)> >{> >for> (>int> i =>0>; i System.out.print(arr[i] + ' '); System.out.println(); } // Driver Code public static void main(String args[]) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[] = { 10, 5, 3, 2, 4 }; int n = arr.length; n = deleteRoot(arr, n); printArray(arr, n); } }>

>

>

C#

// C# program for implement deletion in Heaps> using> System;> public> class> deletionHeap> {> >// To heapify a subtree rooted with node i which is> >// an index in arr[].Nn is size of heap> >static> void> heapify(>int> []arr,>int> n,>int> i)> >{> >int> largest = i;>// Initialize largest as root> >int> l = 2 * i + 1;>// left = 2*i + 1> >int> r = 2 * i + 2;>// right = 2*i + 2> >// If left child is larger than root> >if> (l arr[largest])> >largest = l;> >// If right child is larger than largest so far> >if> (r arr[largest])> >largest = r;> >// If largest is not root> >if> (largest != i)> >{> >int> swap = arr[i];> >arr[i] = arr[largest];> >arr[largest] = swap;> >// Recursively heapify the affected sub-tree> >heapify(arr, n, largest);> >}> >}> >// Function to delete the root from Heap> >static> int> deleteRoot(>int> []arr,>int> n)> >{> >// Get the last element> >int> lastElement = arr[n - 1];> >// Replace root with first element> >arr[0] = lastElement;> >// Decrease size of heap by 1> >n = n - 1;> >// heapify the root node> >heapify(arr, n, 0);> >// return new size of Heap> >return> n;> >}> >/* A utility function to print array of size N */> >static> void> printArray(>int> []arr,>int> n)> >{> >for> (>int> i = 0; i Console.Write(arr[i] + ' '); Console.WriteLine(); } // Driver Code public static void Main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int []arr = { 10, 5, 3, 2, 4 }; int n = arr.Length; n = deleteRoot(arr, n); printArray(arr, n); } } // This code is contributed by Ryuga>

>

>

JavaScript

> >// Javascript program for implement deletion in Heaps> > >// To heapify a subtree rooted with node i which is> >// an index in arr[].Nn is size of heap> >function> heapify(arr, n, i)> >{> >let largest = i;>// Initialize largest as root> >let l = 2 * i + 1;>// left = 2*i + 1> >let r = 2 * i + 2;>// right = 2*i + 2> >// If left child is larger than root> >if> (l arr[largest])> >largest = l;> >// If right child is larger than largest so far> >if> (r arr[largest])> >largest = r;> >// If largest is not root> >if> (largest != i)> >{> >let swap = arr[i];> >arr[i] = arr[largest];> >arr[largest] = swap;> >// Recursively heapify the affected sub-tree> >heapify(arr, n, largest);> >}> >}> >// Function to delete the root from Heap> >function> deleteRoot(arr, n)> >{> >// Get the last element> >let lastElement = arr[n - 1];> >// Replace root with first element> >arr[0] = lastElement;> >// Decrease size of heap by 1> >n = n - 1;> >// heapify the root node> >heapify(arr, n, 0);> >// return new size of Heap> >return> n;> >}> >/* A utility function to print array of size N */> >function> printArray(arr, n)> >{> >for> (let i = 0; i document.write(arr[i] + ' '); document.write(''); } let arr = [ 10, 5, 3, 2, 4 ]; let n = arr.length; n = deleteRoot(arr, n); printArray(arr, n); // This code is contributed by divyeshrabdiya07.>

>

>

Python3

# Python 3 program for implement deletion in Heaps> # To heapify a subtree rooted with node i which is> # an index of arr[] and n is the size of heap> def> heapify(arr, n, i):> >largest>=> i>#Initialize largest as root> >l>=> 2> *> i>+> 1> # left = 2*i + 1> >r>=> 2> *> i>+> 2> # right = 2*i + 2> >#If left child is larger than root> >if> (l and arr[l]>arr[największy]): największy = l #Jeśli prawe dziecko jest większe od największego dotychczas if (r i arr[r]> arr[największy]): największy = r # Jeśli największe nie jest pierwiastkiem if (największy != i) : arr[i],arr[largest]=arr[largest],arr[i] #Rekursywnie zbuduj poddrzewo, którego to dotyczy, heapify(arr, n, największy) #Funkcja usuwająca korzeń ze sterty def DeleteRoot(arr): global n # Pobierz ostatni element lastElement = arr[n - 1] # Zastąp korzeń ostatnim elementem arr[0] = lastElement # Zmniejsz rozmiar sterty o 1 n = n - 1 # zasyp węzeł główny heapify(arr, n, 0) # Funkcja narzędziowa do drukowania tablicy o rozmiarze n def printArray(arr, n): for i in range(n): print(arr[i],end=' ') print() # Kod sterownika if __name__ == '__main__': # Reprezentacja tablicowa Max-Heap # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) DeleteRoot( arr) printArray(arr, n) # Ten kod został napisany przez Rajata Kumara.>

>

>

Wyjście

5 4 3 2>

Złożoność czasowa : O(log n) gdzie n oznacza liczbę elementów na stercie
Przestrzeń pomocnicza: NA)

3.Operacja podglądu na strukturze danych z maksymalną stertą:

Aby uzyskać dostęp do maksymalnego elementu (tj. korzenia sterty), zwracana jest wartość węzła głównego. Złożoność czasowa zaglądania na maksymalną stertę wynosi O(1).

Szczytowy element maksymalnej sterty

Implementacja operacji Peek w Max-Heap:

C++

#include> #include> int> main() {> >// Create a max heap with some elements using a priority_queue> >std::priority_queue<>int>>maxHeap;> >maxHeap.push(9);> >maxHeap.push(8);> >maxHeap.push(7);> >maxHeap.push(6);> >maxHeap.push(5);> >maxHeap.push(4);> >maxHeap.push(3);> >maxHeap.push(2);> >maxHeap.push(1);> >// Get the peak element (i.e., the largest element)> >int> peakElement = maxHeap.top();> >// Print the peak element> >std::cout <<>'Peak element: '> << peakElement << std::endl;> >return> 0;> }>

>

>

Jawa

import> java.util.PriorityQueue;> public> class> GFG {> >public> static> void> main(String[] args) {> >// Create a max heap with some elements using a PriorityQueue> >PriorityQueue maxHeap =>new> PriorityQueue((a, b) ->b - a);> >maxHeap.add(>9>);> >maxHeap.add(>8>);> >maxHeap.add(>7>);> >maxHeap.add(>6>);> >maxHeap.add(>5>);> >maxHeap.add(>4>);> >maxHeap.add(>3>);> >maxHeap.add(>2>);> >maxHeap.add(>1>);> >// Get the peak element (i.e., the largest element)> >int> peakElement = maxHeap.peek();> >// Print the peak element> >System.out.println(>'Peak element: '> + peakElement);> >}> }>

>

>

C#

using> System;> using> System.Collections.Generic;> public> class> GFG {> >public> static> void> Main() {> >// Create a min heap with some elements using a PriorityQueue> >var> maxHeap =>new> PriorityQueue<>int>>();> >maxHeap.Enqueue(9);> >maxHeap.Enqueue(8);> >maxHeap.Enqueue(7);> >maxHeap.Enqueue(6);> >maxHeap.Enqueue(5);> >maxHeap.Enqueue(4);> >maxHeap.Enqueue(3);> >maxHeap.Enqueue(2);> >maxHeap.Enqueue(1);> >// Get the peak element (i.e., the smallest element)> >int> peakElement = maxHeap.Peek();> >// Print the peak element> >Console.WriteLine(>'Peak element: '> + peakElement);> >}> }> // Define a PriorityQueue class that uses a max heap> class> PriorityQueue>where> T : IComparable {> >private> List heap;> >public> PriorityQueue() {> >this>.heap =>new> List();> >}> >public> int> Count {> >get> {>return> this>.heap.Count; }> >}> >public> void> Enqueue(T item) {> >this>.heap.Add(item);> >this>.BubbleUp(>this>.heap.Count - 1);> >}> >public> T Dequeue() {> >T item =>this>.heap[0];> >int> lastIndex =>this>.heap.Count - 1;> >this>.heap[0] =>this>.heap[lastIndex];> >this>.heap.RemoveAt(lastIndex);> >this>.BubbleDown(0);> >return> item;> >}> >public> T Peek() {> >return> this>.heap[0];> >}> >private> void> BubbleUp(>int> index) {> >while> (index>0) {> >int> parentIndex = (index - 1) / 2;> >if> (>this>.heap[parentIndex].CompareTo(>this>.heap[index])>= 0) {> >break>;> >}> >Swap(parentIndex, index);> >index = parentIndex;> >}> >}> >private> void> BubbleDown(>int> index) {> >while> (index <>this>.heap.Count) {> >int> leftChildIndex = index * 2 + 1;> >int> rightChildIndex = index * 2 + 2;> >int> largestChildIndex = index;> >if> (leftChildIndex <>this>.heap.Count &&>this>.heap[leftChildIndex].CompareTo(>this>.heap[largestChildIndex])>0) {> >largestChildIndex = leftChildIndex;> >}> >if> (rightChildIndex <>this>.heap.Count &&>this>.heap[rightChildIndex].CompareTo(>this>.heap[largestChildIndex])>0) {> >largestChildIndex = rightChildIndex;> >}> >if> (largestChildIndex == index) {> >break>;> >}> >Swap(largestChildIndex, index);> >index = largestChildIndex;> >}> >}> >private> void> Swap(>int> i,>int> j) {> >T temp =>this>.heap[i];> >this>.heap[i] =>this>.heap[j];> >this>.heap[j] = temp;> >}> }>

>

>

JavaScript

// Define a MaxHeap class that uses an array> class MaxHeap {> >constructor() {> >this>.heap = [];> >}> >push(item) {> >this>.heap.push(item);> >this>.bubbleUp(>this>.heap.length - 1);> >}> >pop() {> >let item =>this>.heap[0];> >let lastIndex =>this>.heap.length - 1;> >this>.heap[0] =>this>.heap[lastIndex];> >this>.heap.pop();> >this>.bubbleDown(0);> >return> item;> >}> >peak() {> >return> this>.heap[0];> >}> >bubbleUp(index) {> >while> (index>0) {> >let parentIndex = Math.floor((index - 1) / 2);> >if> (>this>.heap[parentIndex]>=>this>.heap[index]) {> >break>;> >}> >this>.swap(parentIndex, index);> >index = parentIndex;> >}> >}> >bubbleDown(index) {> >while> (index <>this>.heap.length) {> >let leftChildIndex = index * 2 + 1;> >let rightChildIndex = index * 2 + 2;> >let largestChildIndex = index;> >if> (leftChildIndex <>this>.heap.length &&>this>.heap[leftChildIndex]>>this>.heap[largestChildIndex]) {> >largestChildIndex = leftChildIndex;> >}> >if> (rightChildIndex <>this>.heap.length &&>this>.heap[rightChildIndex]>>this>.heap[largestChildIndex]) {> >largestChildIndex = rightChildIndex;> >}> >if> (largestChildIndex === index) {> >break>;> >}> >this>.swap(largestChildIndex, index);> >index = largestChildIndex;> >}> >}> >swap(i, j) {> >let temp =>this>.heap[i];> >this>.heap[i] =>this>.heap[j];> >this>.heap[j] = temp;> >}> }> // Create a max heap with some elements using an array> let maxHeap =>new> MaxHeap();> maxHeap.push(9);> maxHeap.push(8);> maxHeap.push(7);> maxHeap.push(6);> maxHeap.push(5);> maxHeap.push(4);> maxHeap.push(3);> maxHeap.push(2);> maxHeap.push(1);> // Get the peak element (i.e., the largest element)> let peakElement = maxHeap.peak();> // Print the peak element> console.log(>'Peak element: '> + peakElement);>

>

>

Python3

przykłady systemów operacyjnych

import> heapq> # Create a max heap with some elements using a list> max_heap>=> [>1>,>2>,>3>,>4>,>5>,>6>,>7>,>8>,>9>]> heapq.heapify(max_heap)> # Get the peak element (i.e., the largest element)> peak_element>=> heapq.nlargest(>1>, max_heap)[>0>]> # Print the peak element> print>(>'Peak element:'>, peak_element)>

>

>

Wyjście

Peak element: 9>

Złożoność czasowa :

• W maksymalnej stercie zaimplementowanej przy użyciu plikuszyklub listę, dostęp do elementu szczytowego można uzyskać w stałym czasie O(1), ponieważ zawsze znajduje się on w korzeniu sterty.
• W maksymalnej stercie zaimplementowanej przy użyciu adrzewo binarne, dostęp do elementu szczytowego można uzyskać również w czasie O(1), ponieważ zawsze znajduje się on u korzenia drzewa.

Przestrzeń pomocnicza: NA)

4.Operacja Heapify na strukturze danych z maksymalną stertą:

Operacji heapify można użyć do utworzenia maksymalnej sterty z nieposortowanej tablicy. Odbywa się to poprzez rozpoczęcie od ostatniego węzła innego niż liść i wielokrotne wykonywanie operacji bąbelkowania, aż wszystkie węzły spełnią właściwość sterty. Złożoność czasowa sterty na maksymalnej stercie wynosi O(n).

Operacje Heapify w Max-Heap

5.Operacja wyszukiwania w strukturze danych o maksymalnej stercie:

Aby wyszukać element na maksymalnej stercie, można przeprowadzić wyszukiwanie liniowe w tablicy reprezentującej stertę. Jednakże złożoność czasowa przeszukiwania liniowego wynosi O(n), co nie jest efektywne. Dlatego wyszukiwanie nie jest powszechnie stosowaną operacją na maksymalnej stercie.

Oto przykładowy kod pokazujący, jak szukać elementu na maksymalnej stercie za pomocą std::znajdź() :

C++

#include> #include // for std::priority_queue> using> namespace> std;> int> main() {> >std::priority_queue<>int>>max_heap;> >// example max heap> > >max_heap.push(10);> >max_heap.push(9);> >max_heap.push(8);> >max_heap.push(6);> >max_heap.push(4);> >int> element = 6;>// element to search for> >bool> found =>false>;> >// Copy the max heap to a temporary queue and search for the element> >std::priority_queue<>int>>temp = max_heap;> >while> (!temp.empty()) {> >if> (temp.top() == element) {> >found =>true>;> >break>;> >}> >temp.pop();> >}> >if> (found) {> >std::cout <<>'Element found in the max heap.'> << std::endl;> >}>else> {> >std::cout <<>'Element not found in the max heap.'> << std::endl;> >}> >return> 0;> }>

>

>

Jawa

import> java.util.PriorityQueue;> public> class> GFG {> >public> static> void> main(String[] args) {> >PriorityQueue maxHeap =>new> PriorityQueue((a, b) ->b - a);> >maxHeap.add(>3>);>// insert elements into the priority queue> >maxHeap.offer(>1>);> >maxHeap.offer(>4>);> >maxHeap.offer(>1>);> >maxHeap.offer(>6>);> >int> element =>6>;>// element to search for> >boolean> found =>false>;> >// Copy the max heap to a temporary queue and search for the element> >PriorityQueue temp =>new> PriorityQueue(maxHeap);> >while> (!temp.isEmpty()) {> >if> (temp.poll() == element) {> >found =>true>;> >break>;> >}> >}> >if> (found) {> >System.out.println(>'Element found in the max heap.'>);> >}>else> {> >System.out.println(>'Element not found in the max heap.'>);> >}> >}> }>

>

>

C#

using> System;> using> System.Collections.Generic;> class> Program {> >static> void> Main(>string>[] args) {> >// Create a max heap with some elements using a PriorityQueue> >PriorityQueue<>int>>maxHeap =>new> PriorityQueue<>int>>();> >maxHeap.Enqueue(10);> >maxHeap.Enqueue(9);> >maxHeap.Enqueue(8);> >maxHeap.Enqueue(6);> >maxHeap.Enqueue(4);> >int> element = 6;>// element to search for> >bool> found =>false>;> >// Copy the max heap to a temporary queue and search for the element> >PriorityQueue<>int>>temperatura =>new> PriorityQueue<>int>>(maxHeap);> >while> (temp.Count>0) {> >if> (temp.Peek() == element) {> >found =>true>;> >break>;> >}> >temp.Dequeue();> >}> >if> (found) {> >Console.WriteLine(>'Element found in the max heap.'>);> >}>else> {> >Console.WriteLine(>'Element not found in the max heap.'>);> >}> >}> }> // PriorityQueue class> class> PriorityQueue>where> T : IComparable {> >private> List heap =>new> List();> >public> void> Enqueue(T item) {> >heap.Add(item);> >int> child = heap.Count - 1;> >while> (child>0) {> >int> parent = (child - 1) / 2;> >if> (heap[child].CompareTo(heap[parent])>0) {> >T tmp = heap[child];> >heap[child] = heap[parent];> >heap[parent] = tmp;> >child = parent;> >}>else> {> >break>;> >}> >}> >}> >public> T Dequeue() {> >int> last = heap.Count - 1;> >T frontItem = heap[0];> >heap[0] = heap[last];> >heap.RemoveAt(last);> >last--;> >int> parent = 0;> >while> (>true>) {> >int> leftChild = parent * 2 + 1;> >if> (leftChild>ostatni) {> >break>;> >}> >int> rightChild = leftChild + 1;> >if> (rightChild <= last && heap[leftChild].CompareTo(heap[rightChild]) < 0) {> >leftChild = rightChild;> >}> >if> (heap[parent].CompareTo(heap[leftChild]) <0) {> >T tmp = heap[parent];> >heap[parent] = heap[leftChild];> >heap[leftChild] = tmp;> >parent = leftChild;> >}>else> {> >break>;> >}> >}> >return> frontItem;> >}> >public> T Peek() {> >return> heap[0];> >}> >public> int> Count {> >get> {> >return> heap.Count;> >}> >}> }>

drzewo binarne przejścia sprzedaży wysyłkowej

>

>

JavaScript

const maxHeap =>new> PriorityQueue((a, b) =>b - a);> maxHeap.add(3);>// insert elements into the priority queue> maxHeap.add(1);> maxHeap.add(4);> maxHeap.add(1);> maxHeap.add(6);> const element = 6;>// element to search for> let found =>false>;> // Copy the max heap to a temporary queue and search for the element> const temp =>new> PriorityQueue(maxHeap);> while> (!temp.isEmpty()) {> if> (temp.poll() === element) {> found =>true>;> break>;> }> }> if> (found) {> console.log(>'Element found in the max heap.'>);> }>else> {> console.log(>'Element not found in the max heap.'>);> }>

>

>

Python3

import> heapq> max_heap>=> [>10>,>8>,>7>,>6>,>5>,>3>,>2>,>1>]># example max heap> heapq._heapify_max(max_heap)> element>=> 6> # element to search for> found>=> False> # Copy the max heap to a temporary list and search for the element> temp>=> list>(max_heap)> while> temp:> >if> heapq._heappop_max(temp)>=>=> element:> >found>=> True> >break> if> found:> >print>(>'Element found in the max heap.'>)> else>:> >print>(>'Element not found in the max heap.'>)>

>

>

Wyjście

Element found in the max heap.>

Złożoność czasowa : O(n), gdzie n jest rozmiarem sterty.
Przestrzeń pomocnicza : NA),

Zastosowania struktury danych Max-Heap:

• Algorytm sortowania stertowego: Struktura danych sterty jest podstawą algorytmu sortowania sterty, który jest wydajnym algorytmem sortowania o złożoności czasowej w najgorszym przypadku wynoszącej O(n log n). Algorytm sortowania sterty jest używany w różnych zastosowaniach, w tym w indeksowaniu baz danych i analizie numerycznej.
• Zarządzanie pamięcią: Struktura danych sterty jest używana w systemach zarządzania pamięcią do dynamicznego przydzielania i zwalniania pamięci. Sterta służy do przechowywania bloków pamięci, a struktura danych sterty służy do efektywnego zarządzania blokami pamięci i przydzielania ich programom w razie potrzeby.
• Algorytmy wykresów: Struktura danych sterty jest wykorzystywana w różnych algorytmach grafowych, w tym w algorytmie Dijkstry, algorytmie Prima i algorytmie Kruskala. Algorytmy te wymagają wydajnej implementacji kolejki priorytetowej, co można osiągnąć za pomocą struktury danych sterty.
• Planowanie pracy: Struktura danych sterty jest wykorzystywana w algorytmach planowania zadań, w których zadania są planowane na podstawie ich priorytetu lub terminu realizacji. Struktura danych sterty umożliwia efektywny dostęp do zadań o najwyższym priorytecie, co czyni ją użyteczną strukturą danych dla aplikacji do planowania zadań.

Zalety struktury danych Max-Heap:

• Skutecznie utrzymuj maksymalną wartość: Maksymalna sterta umożliwia stały dostęp do maksymalnego elementu na stercie, co czyni ją przydatną w aplikacjach, w których trzeba szybko znaleźć maksymalny element.
• Wydajne operacje wstawiania i usuwania: Operacje wstawiania i usuwania na maksymalnej stercie mają złożoność czasową O(log n), co czyni je efektywnymi w przypadku dużych kolekcji elementów.
• Kolejki priorytetowe: Maksymalną stertę można wykorzystać do zaimplementowania kolejki priorytetowej, co jest przydatne w wielu zastosowaniach, takich jak planowanie zadań, ustalanie priorytetów zadań i symulacja sterowana zdarzeniami.
• Sortowanie: Do zaimplementowania sortowania na stercie można użyć maksymalnej sterty, która jest wydajnym algorytmem sortowania, którego złożoność czasowa w najgorszym przypadku wynosi O(n log n).
• Efektywność przestrzenna: Maksymalną stertę można zaimplementować jako tablicę, która wymaga mniej pamięci w porównaniu z innymi strukturami danych, takimi jak drzewo wyszukiwania binarnego lub lista połączona.

Struktura danych maksymalnej sterty to przydatne i wydajne narzędzie do utrzymywania kolekcji elementów i manipulowania nimi, szczególnie gdy trzeba szybko uzyskać dostęp do maksymalnego elementu lub gdy elementy wymagają sortowania lub ustalania priorytetów.