INLEIDING TOT MAX-HEAP – TUTORIALS VOOR GEGEVENSSTRUCTUUR EN ALGORITMEN - TECHCODEVIEW.COM

A Max-hoop wordt gedefinieerd als een soort De heap-gegevensstructuur is een soort binaire boom die in de informatica vaak wordt gebruikt voor verschillende doeleinden, waaronder het sorteren, zoeken en organiseren van gegevens.

Inleiding tot de Max-Heap-gegevensstructuur

Doel en gebruiksscenario's van Max-Heap:

Prioriteits-rij: Een van de belangrijkste toepassingen van de heap-gegevensstructuur is het implementeren van prioriteitswachtrijen.

Hoopsoort: De heap-gegevensstructuur wordt ook gebruikt in sorteeralgoritmen.

Geheugen management: De heap-gegevensstructuur wordt ook gebruikt bij geheugenbeheer. Wanneer een programma geheugen dynamisch moet toewijzen, gebruikt het de heap-gegevensstructuur om het beschikbare geheugen bij te houden.

Het kortste pad-algoritme van Dijkstra gebruikt een heap-datastructuur om de hoekpunten met het kortste pad vanaf het bronpunt bij te houden.

Max-Heap-gegevensstructuur in verschillende talen:

1. Max-heap in C++

Een maximale heap kan worden geïmplementeerd met behulp van de prioriteits-rij container uit de Standaardsjabloonbibliotheek (STL) . De prioriteits-rij container is een type containeradapter die een manier biedt om elementen op te slaan in een wachtrij-achtige gegevensstructuur waarin aan elk element een prioriteit is gekoppeld.
  Synt  ax: priority_queuemaxH;>
2. Max Heap in Java

In Java kan een max heap worden geïmplementeerd met behulp van de Prioriteits-rij klasse uit java.util-pakket . De PriorityQueue-klasse is een prioriteitswachtrij die een manier biedt om elementen op te slaan in een wachtrij-achtige gegevensstructuur waarin aan elk element een prioriteit is gekoppeld.
  Syntax  : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());>
3. Max-Heap in Python

In Python kan een max heap worden geïmplementeerd met behulp van de hoopq module, die functies biedt voor het implementeren van heaps. Concreet biedt de heapq-module een manier om heap-datastructuren te creëren en te manipuleren.
  Synt  ax: heap = []  heapify(heap)>
4. Max-heap in C#

In C# kan een max heap worden geïmplementeerd met behulp van de klasse PriorityQueue uit de System.Collections.Generieke naamruimte . De PriorityQueue-klasse is een prioriteitswachtrij die een manier biedt om elementen op te slaan in een wachtrij-achtige gegevensstructuur waarin aan elk element een prioriteit is gekoppeld.
  Syntax:   var maxHeap = new PriorityQueue((a, b) =>b-a);>
5. Max-Heap in JavaScript

Een max heap is een binaire boom waarin elk knooppunt een waarde heeft die groter is dan of gelijk is aan de onderliggende knooppunten. In JavaScript kun je een max heap implementeren met behulp van een array, waarbij het eerste element het hoofdknooppunt vertegenwoordigt, en de onderliggende elementen van een knooppunt op de index i bevinden zich op indices 2i+1 En 2i+2.
Syntax: const miaxHeap = new MaxHeap();>
Verschil tussen Max en Min Heap

Min hoop Max hoop

1. In een Min-Heap moet de sleutel die aanwezig is op het hoofdknooppunt kleiner zijn dan of gelijk zijn aan de sleutels die aanwezig zijn op alle onderliggende knooppunten. In een Max-Heap moet de sleutel die aanwezig is op het hoofdknooppunt groter zijn dan of gelijk zijn aan de sleutels die aanwezig zijn op alle onderliggende knooppunten.

2. In een Min-Heap het minimale sleutelelement dat aanwezig is in de root. In een Max-Heap het maximale sleutelelement dat aanwezig is in de root.

3. Een Min-Heap gebruikt de oplopende prioriteit. Een Max-Heap gebruikt de aflopende prioriteit.

4. Bij de constructie van een Min-Heap heeft het kleinste element prioriteit. Bij de constructie van een Max-Heap heeft het grootste element prioriteit.

5. In een Min-Heap wordt het kleinste element als eerste uit de hoop gehaald. In een Max-Heap wordt het grootste element als eerste uit de hoop gehaald.

Interne implementatie van Max-Heap-gegevensstructuur:

A Min heap wordt doorgaans weergegeven als een array .

Het hoofdelement bevindt zich op Arr[0] .

Voor elk it-knooppunt Arr[i].

het linkerkind wordt opgeslagen bij de index 2i+1

Het rechterkind wordt opgeslagen bij de index 2i+2

De ouder wordt opgeslagen op de indexvloer ((i-1)/2)

De interne implementatie van de Max-Heap vereist 3 belangrijke stappen:

Plaatsing : Om een nieuw element in de heap in te voegen, wordt het aan het einde van de array toegevoegd en vervolgens omhoog geborreld totdat het voldoet aan de heap-eigenschap.

Verwijdering : Om het maximale element (de root van de heap) te verwijderen, wordt het laatste element in de array verwisseld met de root, en wordt de nieuwe root naar beneden geborreld totdat deze voldoet aan de heap-eigenschap.

Heapify : Een heapify-bewerking kan worden gebruikt om een maximale heap te maken van een ongesorteerde array.

Bewerkingen op de Max-heap-gegevensstructuur en hun implementatie:

Hier zijn enkele algemene bewerkingen die kunnen worden uitgevoerd op een Heap Data Structure-datastructuur:

1. Invoeging in Max-Heap-gegevensstructuur :

Elementen kunnen in de heap worden ingevoegd volgens een vergelijkbare aanpak als hierboven besproken voor verwijdering. Het idee is om:

Vergroot eerst de heapgrootte met 1, zodat het nieuwe element erin kan worden opgeslagen.

Plaats het nieuwe element aan het einde van de Heap.

Dit nieuw ingevoegde element kan de eigenschappen van Heap voor zijn ouders vervormen. Om de eigenschappen van Heap te behouden, moet u dit nieuw ingevoegde element dus opstapelen volgens een bottom-up benadering.

Illustratie:

Stel dat de Heap een Max-Heap is als:

Invoeging in Max-heap

Implementatie van invoegbewerking in Max-Heap:

C++

gelijkwaardigheid wetten

// 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[ouder]) {> >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[ouder]) {> > >// 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[ouder]) {> >// 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[ouder]) {> >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[ouder]:> >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....> '''>
>
>
Uitvoer
15 5 10 2 4 3>
Tijdcomplexiteit: O(log(n)) ( waarbij n het aantal elementen in de heap is )
Hulpruimte: Op)

2. Verwijdering in Max-Heap-gegevensstructuur :

Het verwijderen van een element op een tussenliggende positie in de heap kan kostbaar zijn, dus we kunnen eenvoudigweg het te verwijderen element vervangen door het laatste element en het laatste element van de heap verwijderen.

Vervang de root of het element dat moet worden verwijderd door het laatste element.

Verwijder het laatste element uit de heap.

Omdat het laatste element nu op de positie van het rootknooppunt wordt geplaatst. Het volgt dus mogelijk niet de heap-eigenschap. Heap daarom het laatste knooppunt op dat op de positie van de wortel is geplaatst.

Illustratie :

Stel dat de Heap een Max-Heap is als:

Max Heap-gegevensstructuur

Het te verwijderen element is root, d.w.z. 10.

Proces :

Het laatste element is 4.

Stap 1: Vervang het laatste element door root en verwijder het.

Max Hoop

Stap 2 : Heapify-wortel.

Laatste hoop:

Max hoop

Implementatie van verwijderingsbewerking 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); } }>

gekoppelde lijst
>
>
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[grootste]): grootste = l #Als het rechterkind groter is dan de grootste tot nu toe als (r en arr[r]> arr[grootste]): grootste = r # Als de grootste geen wortel is if (grootste != i) : arr[i],arr[grootste]=arr[grootste],arr[i] #Heapify de betreffende subboom recursief heapify(arr, n, grootste) #Functie om de root uit Heap te verwijderen def deleteRoot(arr): global n # Haal het laatste element op lastElement = arr[n - 1] # Vervang root door het laatste element arr[0] = lastElement # Verklein de grootte van de heap met 1 n = n - 1 # heapify het hoofdknooppunt heapify(arr, n, 0) # Een hulpprogramma voor het afdrukken van een array met de grootte n def printArray(arr, n): for i in range(n): print(arr[i],end=' ') print() # Drivercode if __name__ == '__main__': # Array-weergave van Max-Heap # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot( arr) printArray(arr, n) # Deze code is bijgedragen door Rajat Kumar.>
>
>
Uitvoer
5 4 3 2>
Tijdcomplexiteit : O(log n) waarbij n het aantal elementen in de heap is
Hulpruimte: Op)

3.Peek-bewerking op Max-heap-gegevensstructuur:

Om toegang te krijgen tot het maximale element (dat wil zeggen de wortel van de heap), wordt de waarde van het hoofdknooppunt geretourneerd. De tijdscomplexiteit van kijkje in een maximale hoop is O(1).

Piekelement van maximale hoop
git-opdrachten voor push

Implementatie van Peek-bewerking 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);> >}> }>
>
>
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)>
>
>
Uitvoer
Peak element: 9>
Tijdcomplexiteit :

In een maximale heap geïmplementeerd met behulp van eenreeksof een lijst, kan het peak-element in constante tijd worden benaderd, O(1), omdat het zich altijd in de root van de heap bevindt.

In een maximale heap geïmplementeerd met behulp van abinaire boom, is het piekelement ook toegankelijk in O(1) tijd, omdat het zich altijd aan de wortel van de boom bevindt.

Hulpruimte: Op)

4.Heapify-bewerking op Max-heap-gegevensstructuur:

Een heapify-bewerking kan worden gebruikt om een maximale heap te maken van een ongesorteerde array. Dit wordt gedaan door te beginnen bij het laatste niet-bladknooppunt en herhaaldelijk de bubble-down-operatie uit te voeren totdat alle knooppunten voldoen aan de heap-eigenschap. De tijdscomplexiteit van heapify in een maximale heap is O(n).

Heapify-bewerkingen in Max-Heap

5.Zoekbewerking op de Max-heap-gegevensstructuur:

Om naar een element in de max heap te zoeken, kan een lineaire zoekopdracht worden uitgevoerd over de array die de heap vertegenwoordigt. De tijdscomplexiteit van een lineaire zoekopdracht is echter O(n), wat niet efficiënt is. Daarom is zoeken geen veelgebruikte bewerking in een maximale heap.

Hier is een voorbeeldcode die laat zien hoe u naar een element in een max heap kunt zoeken met behulp van std::vind() :

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;> }>
>
>
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>>temperatuur =>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>laatste) {> >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

np.som

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.'>)>
>
>
Uitvoer
Element found in the max heap.>
Tijdcomplexiteit : O(n), waarbij n de grootte van de hoop is.
Hulpruimte : Op),

Toepassingen van Max-Heap-gegevensstructuur:

Heapsort-algoritme: De heap-gegevensstructuur vormt de basis voor het heapsort-algoritme, een efficiënt sorteeralgoritme met een tijdscomplexiteit in het slechtste geval van O(n log n). Het heapsort-algoritme wordt in verschillende toepassingen gebruikt, waaronder database-indexering en numerieke analyse.

Geheugen management: De heap-gegevensstructuur wordt gebruikt in geheugenbeheersystemen om geheugen dynamisch toe te wijzen en de toewijzing ervan ongedaan te maken. De heap wordt gebruikt om de geheugenblokken op te slaan, en de heap-datastructuur wordt gebruikt om de geheugenblokken efficiënt te beheren en indien nodig aan programma's toe te wijzen.

Grafiekalgoritmen: De heap-gegevensstructuur wordt gebruikt in verschillende grafiekalgoritmen, waaronder het algoritme van Dijkstra, het algoritme van Prim en het algoritme van Kruskal. Deze algoritmen vereisen een efficiënte implementatie van prioriteitswachtrijen, wat kan worden bereikt met behulp van de heap-datastructuur.

Taakplanning: De heap-gegevensstructuur wordt gebruikt in taakplanningsalgoritmen, waarbij taken worden gepland op basis van hun prioriteit of deadline. De heap-datastructuur maakt efficiënte toegang tot de taak met de hoogste prioriteit mogelijk, waardoor het een nuttige datastructuur is voor taakplanningstoepassingen.

Voordelen van Max-Heap-gegevensstructuur:

Efficiënt de maximale waarde behouden: Een max heap maakt constante toegang tot het maximale element in de heap mogelijk, wat het handig maakt in toepassingen waarbij het maximale element snel moet worden gevonden.

Efficiënte invoeg- en verwijderbewerkingen: De invoeg- en verwijderbewerkingen in een maximale heap hebben een tijdscomplexiteit van O(log n), waardoor ze efficiënt zijn voor grote verzamelingen elementen.

Prioritaire wachtrijen: Een max heap kan worden gebruikt om een prioriteitswachtrij te implementeren, wat handig is in veel toepassingen, zoals taakplanning, taakprioritering en gebeurtenisgestuurde simulatie.

Sorteren: Een max heap kan worden gebruikt om heapsort te implementeren, wat een efficiënt sorteeralgoritme is met een tijdscomplexiteit in het slechtste geval van O(n log n).

Ruimte-efficiëntie: Een max heap kan worden geïmplementeerd als een array, waardoor minder geheugen nodig is in vergelijking met andere datastructuren zoals een binaire zoekboom of een gekoppelde lijst.

Max heap-gegevensstructuur is een nuttig en efficiënt hulpmiddel voor het onderhouden en manipuleren van verzamelingen elementen, vooral wanneer het maximale element snel moet worden benaderd of wanneer elementen moeten worden gesorteerd of geprioriteerd.

	Min hoop	Max hoop
1.	In een Min-Heap moet de sleutel die aanwezig is op het hoofdknooppunt kleiner zijn dan of gelijk zijn aan de sleutels die aanwezig zijn op alle onderliggende knooppunten.	In een Max-Heap moet de sleutel die aanwezig is op het hoofdknooppunt groter zijn dan of gelijk zijn aan de sleutels die aanwezig zijn op alle onderliggende knooppunten.
2.	In een Min-Heap het minimale sleutelelement dat aanwezig is in de root.	In een Max-Heap het maximale sleutelelement dat aanwezig is in de root.
3.	Een Min-Heap gebruikt de oplopende prioriteit.	Een Max-Heap gebruikt de aflopende prioriteit.
4.	Bij de constructie van een Min-Heap heeft het kleinste element prioriteit.	Bij de constructie van een Max-Heap heeft het grootste element prioriteit.
5.	In een Min-Heap wordt het kleinste element als eerste uit de hoop gehaald.	In een Max-Heap wordt het grootste element als eerste uit de hoop gehaald.

Inleiding tot Max-Heap – Tutorials voor gegevensstructuur en algoritmen

Max-Heap-gegevensstructuur in verschillende talen:

1. Max-heap in C++

2. Max Heap in Java

3. Max-Heap in Python

4. Max-heap in C#

5. Max-Heap in JavaScript

Verschil tussen Max en Min Heap

Interne implementatie van Max-Heap-gegevensstructuur:

Bewerkingen op de Max-heap-gegevensstructuur en hun implementatie:

1. Invoeging in Max-Heap-gegevensstructuur :

Implementatie van invoegbewerking in Max-Heap:

C++

Java

C#

Javascript

Python3

2. Verwijdering in Max-Heap-gegevensstructuur :

Implementatie van verwijderingsbewerking in Max-Heap:

C++

Java

C#

Javascript

Python3

3.Peek-bewerking op Max-heap-gegevensstructuur:

Implementatie van Peek-bewerking in Max-Heap:

C++

Java

C#

Javascript

Python3

4.Heapify-bewerking op Max-heap-gegevensstructuur:

5.Zoekbewerking op de Max-heap-gegevensstructuur:

C++

Java

C#

Javascript

Python3

Toepassingen van Max-Heap-gegevensstructuur:

Voordelen van Max-Heap-gegevensstructuur: