A Max-Heap ist als eine Art von definiert Die Heap-Datenstruktur ist eine Art Binärbaum, der in der Informatik häufig für verschiedene Zwecke verwendet wird, einschließlich Sortieren, Suchen und Organisieren von Daten.
Einführung in die Max-Heap-Datenstruktur
Zweck und Anwendungsfälle von Max-Heap:
- Prioritätswarteschlange: Eine der Hauptverwendungen der Heap-Datenstruktur ist die Implementierung von Prioritätswarteschlangen.
- Heap-Sortierung: Die Heap-Datenstruktur wird auch in Sortieralgorithmen verwendet.
- Speicherverwaltung: Die Heap-Datenstruktur wird auch in der Speicherverwaltung verwendet. Wenn ein Programm Speicher dynamisch zuweisen muss, verwendet es die Heap-Datenstruktur, um den verfügbaren Speicher zu verfolgen.
- Dijkstras Algorithmus für den kürzesten Weg verwendet eine Heap-Datenstruktur, um die Scheitelpunkte mit dem kürzesten Weg vom Quellscheitelpunkt zu verfolgen.
Max-Heap-Datenstruktur in verschiedenen Sprachen:
1. Max-Heap in C++
Ein maximaler Heap kann mit implementiert werden Prioritätswarteschlange Behälter aus der Standardvorlagenbibliothek (STL) . Der Prioritätswarteschlange Container ist eine Art Containeradapter, der eine Möglichkeit bietet, Elemente in einer warteschlangenähnlichen Datenstruktur zu speichern, in der jedem Element eine Priorität zugeordnet ist.
Synt ax: priority_queuemaxH;>2. Max-Heap in Java
In Java kann ein maximaler Heap mithilfe von implementiert werden Prioritätswarteschlange Klasse von java.util-Paket . Die PriorityQueue-Klasse ist eine Prioritätswarteschlange, die eine Möglichkeit bietet, Elemente in einer warteschlangenähnlichen Datenstruktur zu speichern, in der jedem Element eine Priorität zugeordnet ist.
Syntax : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());>3. Max-Heap in Python
In Python kann ein maximaler Heap mithilfe von implementiert werden Heapq Modul, das Funktionen zur Implementierung von Heaps bereitstellt. Insbesondere bietet das Heapq-Modul eine Möglichkeit, Heap-Datenstrukturen zu erstellen und zu bearbeiten.
Synt ax: heap = [] heapify(heap)>4. Max-Heap in C#
In C# kann ein maximaler Heap mithilfe der PriorityQueue-Klasse aus implementiert werden System.Collections.Generic-Namespace . Die PriorityQueue-Klasse ist eine Prioritätswarteschlange, die eine Möglichkeit bietet, Elemente in einer warteschlangenähnlichen Datenstruktur zu speichern, in der jedem Element eine Priorität zugeordnet ist.
Syntax: var maxHeap = new PriorityQueue((a, b) =>b - a);>5. Max-Heap in JavaScript
Ein Max-Heap ist ein Binärbaum, in dem jeder Knoten einen Wert hat, der größer oder gleich dem Wert seiner untergeordneten Knoten ist. In JavaScript können Sie einen maximalen Heap mithilfe eines Arrays implementieren, wobei das erste Element den Wurzelknoten und die untergeordneten Elemente eines Knotens den Index darstellen ich befinden sich an Indizes 2i+1 Und 2i+2.
Syntax: const miaxHeap = new MaxHeap();>Unterschied zwischen Max- und Min-Heap
Min. Heap Max Heap 1. In einem Min-Heap muss der am Wurzelknoten vorhandene Schlüssel kleiner oder gleich den Schlüsseln aller seiner untergeordneten Knoten sein. In einem Max-Heap muss der am Wurzelknoten vorhandene Schlüssel größer oder gleich den Schlüsseln aller seiner untergeordneten Knoten sein. 2. In einem Min-Heap das minimale Schlüsselelement, das im Stammverzeichnis vorhanden ist. In einem Max-Heap das maximale Schlüsselelement, das im Stammverzeichnis vorhanden ist. 3. Ein Min-Heap verwendet die aufsteigende Priorität. Ein Max-Heap verwendet die absteigende Priorität. 4. Beim Aufbau eines Min-Heaps hat das kleinste Element Vorrang. Beim Aufbau eines Max-Heaps hat das größte Element Vorrang. 5. In einem Min-Heap wird das kleinste Element als erstes aus dem Heap entfernt. In einem Max-Heap wird das größte Element als erstes aus dem Heap entfernt. Interne Implementierung der Max-Heap-Datenstruktur:
A Min. Heap wird normalerweise als Array dargestellt .
- Das Stammelement befindet sich unter Arr[0] .
- Für jeden i-ten Knoten Arr[i].
- Das linke untergeordnete Element wird im Index gespeichert 2i+1
- Das rechte Kind wird im Index gespeichert 2i+2
- Das übergeordnete Element wird auf der Indexebene gespeichert ((i-1)/2)
Die interne Implementierung des Max-Heap erfordert drei Hauptschritte:
- Einfügen : Um ein neues Element in den Heap einzufügen, wird es am Ende des Arrays hinzugefügt und dann nach oben gesprudelt, bis es die Heap-Eigenschaft erfüllt.
- Streichung : Um das maximale Element (den Stamm des Heaps) zu löschen, wird das letzte Element im Array mit dem Stamm ausgetauscht und der neue Stamm wird nach unten verschoben, bis er die Heap-Eigenschaft erfüllt.
- Aufhäufen : Eine Heapify-Operation kann verwendet werden, um einen maximalen Heap aus einem unsortierten Array zu erstellen.
Operationen an der Max-Heap-Datenstruktur und ihre Implementierung:
Hier sind einige allgemeine Vorgänge, die für eine Heap-Datenstruktur-Datenstruktur ausgeführt werden können:
1. Einfügen in die Max-Heap-Datenstruktur :
Elemente können nach einem ähnlichen Ansatz wie oben zum Löschen in den Heap eingefügt werden. Die Idee ist:
- Erhöhen Sie zunächst die Heap-Größe um 1, damit das neue Element gespeichert werden kann.
- Fügen Sie das neue Element am Ende des Heaps ein.
- Dieses neu eingefügte Element kann die Eigenschaften von Heap für seine übergeordneten Elemente verzerren. Um also die Eigenschaften von Heap beizubehalten, häufen Sie dieses neu eingefügte Element nach einem Bottom-up-Ansatz.
Illustration:
Angenommen, der Heap ist ein Max-Heap wie folgt:
Einfügung in den Max-Heap
Implementierung der Einfügeoperation in Max-Heap:
C++
unsigned int c Programmierung
// 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[parent]) {>>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; }>>>Java
// 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[parent]) {>>>// 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[parent]) {>>// 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[parent]) {>>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[parent]:>>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....>'''>>>Ausgabe15 5 10 2 4 3>Zeitkomplexität: O(log(n)) ( wobei n die Anzahl der Elemente im Heap ist )
Hilfsraum: An)2. Löschen in der Max-Heap-Datenstruktur :
Das Löschen eines Elements an einer beliebigen Zwischenposition im Heap kann kostspielig sein. Daher können wir einfach das zu löschende Element durch das letzte Element ersetzen und das letzte Element des Heaps löschen.
- Ersetzen Sie den Stamm oder das zu löschende Element durch das letzte Element.
- Löschen Sie das letzte Element aus dem Heap.
- Da das letzte Element nun an der Position des Wurzelknotens platziert ist. Daher folgt es möglicherweise nicht der Heap-Eigenschaft. Heapifizieren Sie daher den letzten Knoten, der an der Position der Wurzel platziert ist.
Illustration :
Angenommen, der Heap ist ein Max-Heap wie folgt:
Max. Heap-Datenstruktur
Das zu löschende Element ist root, also 10.
Verfahren :
Das letzte Element ist 4.
Schritt 1: Ersetzen Sie das letzte Element durch root und löschen Sie es.
binäre BaumtypenMax Heap
Schritt 2 : Wurzel aufhäufen.
Letzter Haufen:
Max Heap
Implementierung des Löschvorgangs in 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; }>>>Java
// 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[größte]): größte = l #Wenn das rechte Kind größer als bisher größte ist, wenn (r und arr[r]> arr[größte]): größte = r # Wenn größte nicht Wurzel ist, wenn (größte != i) : arr[i],arr[largest]=arr[largest],arr[i] #Rekursive Heapifizierung des betroffenen Teilbaums heapify(arr, n, most) #Funktion zum Löschen der Wurzel aus dem Heap def deleteRoot(arr): global n # Letztes Element abrufen lastElement = arr[n - 1] # Wurzel durch letztes Element ersetzen arr[0] = lastElement # Größe des Heaps um 1 verringern n = n - 1 # Den Wurzelknoten aufhäufen heapify(arr, n, 0) # Eine Dienstprogrammfunktion zum Drucken eines Arrays der Größe n def printArray(arr, n): for i in range(n): print(arr[i],end=' ') print() # Treibercode, wenn __name__ == '__main__': # Array-Darstellung von Max-Heap # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot( arr) printArray(arr, n) # Dieser Code wurde von Rajat Kumar beigesteuert.>>>Ausgabe5 4 3 2>Zeitkomplexität : O(log n) wobei n die Anzahl der Elemente im Heap ist
Hilfsraum: An)3.Peek-Vorgang für die Max-Heap-Datenstruktur:
Um auf das maximale Element (d. h. die Wurzel des Heaps) zuzugreifen, wird der Wert des Wurzelknotens zurückgegeben. Die zeitliche Komplexität von Peek in einem Max-Heap beträgt O(1).
Peak-Element von Max-Heap
Implementierung der Peek-Operation in 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;>}>>>Java
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);>>}>}>>Java erhält das aktuelle Datum>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
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)>>>AusgabePeak element: 9>Zeitkomplexität :
- In einem maximalen Heap, der mit einem implementiert wirdArrayoder einer Liste kann auf das Peak-Element in konstanter Zeit O(1) zugegriffen werden, da es sich immer an der Wurzel des Heaps befindet.
- In einem maximalen Heap, der mit a implementiert wirdBinärbaum, kann auf das Peak-Element auch in O(1)-Zeit zugegriffen werden, da es sich immer an der Wurzel des Baums befindet.
Hilfsraum: An)
4.Heapify-Vorgang für die Max-Heap-Datenstruktur:
Eine Heapify-Operation kann verwendet werden, um aus einem unsortierten Array einen maximalen Heap zu erstellen. Dazu wird am letzten Nicht-Blattknoten begonnen und der Bubble-Down-Vorgang wiederholt ausgeführt, bis alle Knoten die Heap-Eigenschaft erfüllen. Die zeitliche Komplexität der Heapifizierung in einem maximalen Heap beträgt O(n).
Heapify-Operationen in Max-Heap
5.Suchvorgang für die Max-Heap-Datenstruktur:
Um nach einem Element im maximalen Heap zu suchen, kann eine lineare Suche über das Array durchgeführt werden, das den Heap darstellt. Die zeitliche Komplexität einer linearen Suche beträgt jedoch O(n), was nicht effizient ist. Daher ist die Suche kein häufig verwendeter Vorgang in einem maximalen Heap.
Hier ist ein Beispielcode, der zeigt, wie man mit nach einem Element in einem Max-Heap sucht std::find() :
So finden Sie versteckte Dinge auf AndroidC++
#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;>}>>>Java
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>>temp =>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>zuletzt) {>>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;>>}>>}>}>>>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.'>)>>>AusgabeElement found in the max heap.>Zeitkomplexität : O(n), wobei n die Größe des Heaps ist.
Hilfsraum : An),Anwendungen der Max-Heap-Datenstruktur:
- Heapsort-Algorithmus: Die Heap-Datenstruktur ist die Grundlage für den Heapsort-Algorithmus, der ein effizienter Sortieralgorithmus mit einer Zeitkomplexität im ungünstigsten Fall von O(n log n) ist. Der Heapsort-Algorithmus wird in verschiedenen Anwendungen verwendet, einschließlich der Datenbankindizierung und der numerischen Analyse.
- Speicherverwaltung: Die Heap-Datenstruktur wird in Speicherverwaltungssystemen verwendet, um Speicher dynamisch zuzuweisen und freizugeben. Der Heap wird zum Speichern der Speicherblöcke verwendet, und die Heap-Datenstruktur wird verwendet, um die Speicherblöcke effizient zu verwalten und sie Programmen nach Bedarf zuzuweisen.
- Graphalgorithmen: Die Heap-Datenstruktur wird in verschiedenen Graphalgorithmen verwendet, einschließlich des Dijkstra-Algorithmus, des Prim-Algorithmus und des Kruskal-Algorithmus. Diese Algorithmen erfordern eine effiziente Implementierung der Prioritätswarteschlange, die mithilfe der Heap-Datenstruktur erreicht werden kann.
- Arbeit planen: Die Heap-Datenstruktur wird in Jobplanungsalgorithmen verwendet, bei denen Aufgaben basierend auf ihrer Priorität oder Frist geplant werden. Die Heap-Datenstruktur ermöglicht einen effizienten Zugriff auf die Aufgabe mit der höchsten Priorität und ist somit eine nützliche Datenstruktur für Jobplanungsanwendungen.
Vorteile der Max-Heap-Datenstruktur:
- Den Maximalwert effizient aufrechterhalten: Ein Max-Heap ermöglicht den konstanten Zugriff auf das maximale Element im Heap, was ihn für Anwendungen nützlich macht, bei denen das maximale Element schnell gefunden werden muss.
- Effiziente Einfüge- und Löschvorgänge: Die Einfüge- und Löschvorgänge in einem Max-Heap haben eine zeitliche Komplexität von O(log n), was sie für große Elementsammlungen effizient macht.
- Prioritätswarteschlangen: Ein Max-Heap kann zum Implementieren einer Prioritätswarteschlange verwendet werden, was in vielen Anwendungen wie Jobplanung, Aufgabenpriorisierung und ereignisgesteuerter Simulation nützlich ist.
- Sortierung: Ein Max-Heap kann zur Implementierung von Heapsort verwendet werden, einem effizienten Sortieralgorithmus, der im ungünstigsten Fall eine Zeitkomplexität von O(n log n) aufweist.
- Raumeffizienz: Ein Max-Heap kann als Array implementiert werden, was im Vergleich zu anderen Datenstrukturen wie einem binären Suchbaum oder einer verknüpften Liste weniger Speicher benötigt.
Die Max-Heap-Datenstruktur ist ein nützliches und effizientes Werkzeug zum Verwalten und Bearbeiten von Elementsammlungen, insbesondere wenn schnell auf das maximale Element zugegriffen werden muss oder wenn Elemente sortiert oder priorisiert werden müssen.
