A Max-Heap es defineix com un tipus de L'estructura de dades de pila és un tipus d'arbre binari que s'utilitza habitualment en informàtica per a diversos propòsits, com ara ordenar, cercar i organitzar dades.
Introducció a l'estructura de dades Max-Heap
Propòsit i casos d'ús de Max-Heap:
- Cua de prioritats: Un dels usos principals de l'estructura de dades d'heap és per implementar cues de prioritat.
- Ordenació de pila: L'estructura de dades de pila també s'utilitza en algorismes d'ordenació.
- Gestió de la memòria: L'estructura de dades de pila també s'utilitza en la gestió de la memòria. Quan un programa necessita assignar memòria dinàmicament, utilitza l'estructura de dades de pila per fer un seguiment de la memòria disponible.
- Algorisme del camí més curt de Dijkstra utilitza una estructura de dades de pila per fer un seguiment dels vèrtexs amb el camí més curt des del vèrtex font.
Estructura de dades Max-Heap en diferents idiomes:
1. Max-Heap en C++
Es pot implementar un munt màxim mitjançant el priority_queue contenidor del Biblioteca de plantilles estàndard (STL) . El priority_queue El contenidor és un tipus d'adaptador de contenidor que proporciona una manera d'emmagatzemar elements en una estructura de dades semblant a una cua en la qual cada element té una prioritat associada.
Synt ax: priority_queuemaxH;>2. Max-Heap a Java
A Java, es pot implementar un munt màxim mitjançant el PriorityQueue classe des de paquet java.util . La classe PriorityQueue és una cua de prioritats que proporciona una manera d'emmagatzemar elements en una estructura de dades semblant a una cua en la qual cada element té una prioritat associada.
Syntax : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());>3. Max-Heap a Python
A Python, es pot implementar un munt màxim mitjançant el heapq mòdul, que proporciona funcions per implementar munts. Concretament, el mòdul heapq proporciona una manera de crear i manipular estructures de dades d'heap.
Synt ax: heap = [] heapify(heap)>4. Max-Heap en C#
En C#, es pot implementar un munt màxim mitjançant la classe PriorityQueue de la System.Collections.Generic namespace . La classe PriorityQueue és una cua de prioritats que proporciona una manera d'emmagatzemar elements en una estructura de dades semblant a una cua en la qual cada element té una prioritat associada.
Syntax: var maxHeap = new PriorityQueue((a, b) =>b - a);>>>5. Max-Heap en JavaScript
Un munt màxim és un arbre binari on cada node té un valor superior o igual als seus fills. A JavaScript, podeu implementar un munt màxim mitjançant una matriu, on el primer element representa el node arrel i els fills d'un node a l'índex. i es troben en els índexs 2i+1 i 2i+2.
Diferència entre Max i Min Heap
Min Heap Munt màxim 1. En un Min-Heap, la clau present al node arrel ha de ser menor o igual que entre les claus presents a tots els seus fills. En un Max-Heap, la clau present al node arrel ha de ser més gran o igual que entre les claus presents a tots els seus fills. 2. En un Min-Heap l'element clau mínim present a l'arrel. En un Max-Heap l'element clau màxim present a l'arrel. 3. Un Min-Heap utilitza la prioritat ascendent. Un Max-Heap utilitza la prioritat descendent. 4. En la construcció d'un Min-Heap, l'element més petit té prioritat. En la construcció d'un Max-Heap, l'element més gran té prioritat. 5. En un munt min, l'element més petit és el primer que surt del munt. En un Max-Heap, l'element més gran és el primer que surt del munt. Implementació interna de l'estructura de dades Max-Heap:
A El munt mínim es representa normalment com una matriu .
- L'element arrel estarà a Arriba[0] .
- Per a qualsevol node i Arr[i].
- el fill esquerre s'emmagatzema a l'índex 2i+1
- El nen dret s'emmagatzema a l'índex 2i+2
- El pare s'emmagatzema al pis de l'índex ((i-1)/2)
La implementació interna del Max-Heap requereix 3 passos principals:
- Inserció : Per inserir un element nou a l'emmagatzematge dinàmic, s'afegeix al final de la matriu i, a continuació, s'hi fa bombolles fins que compleix la propietat del munt.
- Supressió : Per suprimir l'element màxim (l'arrel de la pila), l'últim element de la matriu s'intercanvia amb l'arrel i la nova arrel s'esborra fins que compleixi la propietat de l'munt.
- Heapify : Es pot utilitzar una operació d'heapify per crear un munt màxim a partir d'una matriu no ordenada.
Operacions sobre l'estructura de dades de màxim munt i la seva implementació:
A continuació, es mostren algunes operacions habituals que es poden realitzar en una estructura de dades d'estructura de dades d'heap,
1. Inserció a l'estructura de dades Max-Heap :
Els elements es poden inserir a la pila seguint un enfocament similar al que s'ha comentat anteriorment per a la supressió. La idea és:
- Primer augmenteu la mida de l'emmagatzematge en 1, de manera que pugui emmagatzemar el nou element.
- Inseriu el nou element al final de l'Heap.
- Aquest element recentment inserit pot distorsionar les propietats de Heap per als seus pares. Per tant, per mantenir les propietats de Heap, amuntegueu aquest element recentment inserit seguint un enfocament de baix a dalt.
Il·lustració:
Suposem que el munt és un munt màxim com:
Inserció a Max Heap
Implementació de l'operació d'inserció a Max-Heap:
C++
convertir cadena en interger
// 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>>>Python 3
# 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....>'''>retornant una matriu java>>Sortida15 5 10 2 4 3>Complexitat temporal: O(log(n)) ( on n és el nombre d'elements del munt )
Espai auxiliar: O(n)2. Supressió a l'estructura de dades Max-Heap :
Suprimir un element en qualsevol posició intermèdia del munt pot ser costós, de manera que simplement podem substituir l'element que s'ha d'esborrar per l'últim element i suprimir l'últim element del munt.
- Substituïu l'arrel o l'element que s'ha de suprimir per l'últim element.
- Suprimeix l'últim element del munt.
- Com que l'últim element es col·loca ara a la posició del node arrel. Per tant, és possible que no segueixi la propietat heap. Per tant, amuntegueu l'últim node situat a la posició de l'arrel.
Il·lustració :
Suposem que el munt és un munt màxim com:
Estructura de dades d'heap màxim
L'element que s'ha de suprimir és root, és a dir, 10.
Procés :
L'últim element és 4.
Pas 1: Substituïu l'últim element per root i suprimiu-lo.
Munt màxim
Pas 2 : Heapify arrel.
Munt final:
Munt màxim
Implementació de l'operació de supressió a 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.>>>Python 3
# 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[més gran]): més gran = l #Si el fill dret és més gran que el més gran fins ara si (r i arr[r]> arr[més gran]): més gran = r # Si el més gran no és arrel si (més gran != i) : arr[i],arr[plus gran]=arr[més gran],arr[i] #Amuntega recursivament el subarbre afectat heapify(arr, n, major) #Funció per eliminar l'arrel de l'heap def deleteRoot(arr): global n # Obteniu l'últim element lastElement = arr[n - 1] # Substituïu l'arrel per l'últim element arr[0] = lastElement # Reduïu la mida de l'heap en 1 n = n - 1 # heapify el node arrel heapify(arr, n, 0) # Una funció d'utilitat per imprimir una matriu de mida n def printArray(arr, n): per a i en rang(n): print(arr[i],end=' ') print() # Codi del controlador si __name__ == '__main__': # Representació de matriu de Max-Heap # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot( arr) printArray(arr, n) # Aquest codi és aportat per Rajat Kumar.>>>números romans de l'1 al 100>5 4 3 2> Complexitat temporal : O(log n) on n és el nombre d'elements de la pila
Espai auxiliar: O(n)3.Operació d'ull a l'estructura de dades de màxim munt:
Per accedir a l'element màxim (és a dir, l'arrel de la pila), es retorna el valor del node arrel. La complexitat temporal del peek en un munt màxim és O(1).
Element pic de Max- Heap
Implementació de l'operació Peek a 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);>>>Python 3
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)>>>SortidaPeak element: 9>Complexitat temporal :
- En un munt màxim implementat amb unmatriuo una llista, es pot accedir a l'element pic en temps constant, O(1), ja que sempre es troba a l'arrel del munt.
- En un munt màxim implementat mitjançant aarbre binari, també es pot accedir a l'element pic en temps O(1), ja que sempre es troba a l'arrel de l'arbre.
Espai auxiliar: O(n)
4.Operació Heapify a l'estructura de dades Max-heap:
Es pot utilitzar una operació d'heapify per crear un munt màxim a partir d'una matriu no ordenada. Això es fa començant a l'últim node que no és full i realitzant repetidament l'operació de bombolla avall fins que tots els nodes compleixin la propietat de l'munt. La complexitat temporal d'heapify en un munt màxim és O(n).
Heapify operacions a Max-Heap
5.Operació de cerca a l'estructura de dades de màxim munt:
Per cercar un element al munt màxim, es pot realitzar una cerca lineal sobre la matriu que representa el munt. Tanmateix, la complexitat temporal d'una cerca lineal és O(n), que no és eficient. Per tant, la cerca no és una operació d'ús habitual en un munt màxim.
Aquí hi ha un exemple de codi que mostra com cercar un element en un munt màxim utilitzant std::find() :
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>>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>últim) {>>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
java string comparat
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.'>);>}>>>Python 3
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.'>)>>>SortidaElement found in the max heap.>Complexitat temporal : O(n), on n és la mida del munt.
Espai Auxiliar : O(n),Aplicacions de l'estructura de dades Max-Heap:
- Algorisme d'heapsort: L'estructura de dades d'heap és la base de l'algorisme heapsort, que és un algorisme d'ordenació eficient amb una complexitat temporal en el pitjor dels casos de O(n log n). L'algorisme heapsort s'utilitza en diverses aplicacions, inclosa la indexació de bases de dades i l'anàlisi numèrica.
- Gestió de la memòria: L'estructura de dades de pila s'utilitza en sistemes de gestió de memòria per assignar i desassignar memòria dinàmicament. El munt s'utilitza per emmagatzemar els blocs de memòria i l'estructura de dades del munt s'utilitza per gestionar de manera eficient els blocs de memòria i assignar-los als programes segons sigui necessari.
- Algorismes gràfics: L'estructura de dades de pila s'utilitza en diversos algorismes de gràfics, inclosos l'algoritme de Dijkstra, l'algoritme de Prim i l'algoritme de Kruskal. Aquests algorismes requereixen una implementació eficient de la cua de prioritats, que es pot aconseguir mitjançant l'estructura de dades heap.
- Programació de treballs: L'estructura de dades de pila s'utilitza en algorismes de programació de treballs, on les tasques es programen en funció de la seva prioritat o data límit. L'estructura de dades de pila permet un accés eficient a la tasca de màxima prioritat, la qual cosa la converteix en una estructura de dades útil per a aplicacions de programació de treballs.
Avantatges de l'estructura de dades Max-Heap:
- Mantenir eficientment el valor màxim: Un munt màxim permet l'accés en temps constant a l'element màxim del munt, cosa que el fa útil en aplicacions on s'ha de trobar ràpidament l'element màxim.
- Operacions d'inserció i supressió eficients: Les operacions d'inserció i supressió en un munt màxim tenen una complexitat temporal de O(log n), cosa que les fa eficients per a grans col·leccions d'elements.
- Cues de prioritat: Es pot utilitzar un munt màxim per implementar una cua de prioritats, que és útil en moltes aplicacions com ara la programació de treballs, la priorització de tasques i la simulació basada en esdeveniments.
- Classificació: Es pot utilitzar un munt màxim per implementar l'heapsort, que és un algorisme d'ordenació eficient que té una complexitat temporal en el pitjor dels casos de O(n log n).
- Eficiència espacial: Es pot implementar un munt màxim com a matriu, que requereix menys memòria en comparació amb altres estructures de dades, com ara un arbre de cerca binari o una llista enllaçada.
L'estructura de dades d'emmagatzematge màxim és una eina útil i eficient per mantenir i manipular col·leccions d'elements, especialment quan cal accedir ràpidament a l'element màxim o quan cal ordenar o prioritzar els elements.
