A Max-Heap este definit ca un tip de Structura de date heap este un tip de arbore binar care este utilizat în mod obișnuit în informatică în diverse scopuri, inclusiv sortarea, căutarea și organizarea datelor.
Introducere în structura de date Max-Heap
Scopul și cazurile de utilizare ale Max-Heap:
- Coada prioritară: Una dintre utilizările principale ale structurii de date heap este pentru implementarea cozilor prioritare.
- Sortare heap: Structura de date heap este, de asemenea, utilizată în algoritmii de sortare.
- Gestionarea memoriei: Structura de date heap este folosită și în gestionarea memoriei. Când un program trebuie să aloce memorie în mod dinamic, folosește structura de date heap pentru a ține evidența memoriei disponibile.
- Algoritmul cu calea cea mai scurtă a lui Dijkstra folosește o structură de date heap pentru a ține evidența vârfurilor cu calea cea mai scurtă de la vârful sursă.
Structura de date Max-Heap în diferite limbi:
1. Max-Heap în C++
Un heap maxim poate fi implementat folosind priority_queue recipient din Bibliotecă de șabloane standard (STL) . The priority_queue container este un tip de adaptor de container care oferă o modalitate de a stoca elemente într-o structură de date asemănătoare coadă, în care fiecare element are o prioritate asociată.
Synt ax: priority_queuemaxH;>2. Max-Heap în Java
În Java, un heap maxim poate fi implementat folosind PriorityQueue clasa de la pachetul java.util . Clasa PriorityQueue este o coadă de prioritate care oferă o modalitate de a stoca elemente într-o structură de date asemănătoare coadă, în care fiecare element are o prioritate asociată.
Syntax : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());>3. Max-Heap în Python
În Python, un heap maxim poate fi implementat folosind heapq modul, care oferă funcții pentru implementarea heap-urilor. Mai exact, modulul heapq oferă o modalitate de a crea și de a manipula structuri de date heap.
Synt ax: heap = [] heapify(heap)>4. Max-Heap în C#
În C#, un heap maxim poate fi implementat folosind clasa PriorityQueue din Sistem.Colecții.Spațiu de nume generic . Clasa PriorityQueue este o coadă de prioritate care oferă o modalitate de a stoca elemente într-o structură de date asemănătoare coadă, în care fiecare element are o prioritate asociată.
Syntax: var maxHeap = new PriorityQueue((a, b) =>b - a);>>>5. Max-Heap în JavaScript
Un heap maxim este un arbore binar în care fiecare nod are o valoare mai mare sau egală cu copiii săi. În JavaScript, puteți implementa un heap maxim folosind o matrice, unde primul element reprezintă nodul rădăcină și copiii unui nod la index i sunt situate la indici 2i+1 și 2i+2.
Diferența dintre Max și Min Heap
Min Heap Max Heap 1. Într-un Min-Heap, cheia prezentă la nodul rădăcină trebuie să fie mai mică sau egală cu cheile prezente la toți copiii săi. Într-un Max-Heap, cheia prezentă la nodul rădăcină trebuie să fie mai mare sau egală cu cheile prezente la toți copiii săi. 2. Într-un Min-Heap elementul cheie minim prezent la rădăcină. Într-un Max-Heap, elementul cheie maxim prezent la rădăcină. 3. Un Min-Heap folosește prioritatea ascendentă. Un Max-Heap folosește prioritatea descendentă. 4. În construcția unui Min-Heap, cel mai mic element are prioritate. În construcția unui Max-Heap, cel mai mare element are prioritate. 5. Într-un Min-Heap, cel mai mic element este primul care este scos din grămada. Într-un Max-Heap, cel mai mare element este primul care este scos din heap. Implementarea internă a structurii de date Max-Heap:
A Heap-ul min este de obicei reprezentat ca o matrice .
- Elementul rădăcină va fi la Arr[0] .
- Pentru orice nod i Arr[i].
- copilul stâng este stocat la index 2i+1
- Copilul drept este stocat la index 2i+2
- Părintele este stocat la etajul index ((i-1)/2)
Implementarea internă a Max-Heap necesită 3 pași majori:
- Inserare : Pentru a insera un nou element în heap, acesta este adăugat la sfârșitul matricei și apoi balonat până când satisface proprietatea heap.
- Ștergere : Pentru a șterge elementul maxim (rădăcina heap-ului), ultimul element din matrice este schimbat cu rădăcina, iar noua rădăcină este plasată în jos până când satisface proprietatea heap.
- Heapify : O operație heapify poate fi folosită pentru a crea un heap maxim dintr-o matrice nesortată.
Operațiuni pe structura de date Max-heap și implementarea lor:
Iată câteva operațiuni comune care pot fi efectuate pe o structură de date Heap Data Structure,
1. Inserarea în structura de date Max-Heap :
Elementele pot fi inserate în heap urmând o abordare similară cu cea discutată mai sus pentru ștergere. Ideea este de a:
- Măriți mai întâi dimensiunea heap-ului cu 1, astfel încât să poată stoca noul element.
- Introduceți noul element la capătul grămezii.
- Acest element nou introdus poate distorsiona proprietățile Heap pentru părinții săi. Așadar, pentru a păstra proprietățile Heap, îngrămădiți acest element nou inserat urmând o abordare de jos în sus.
Ilustrare:
Să presupunem că Heap-ul este un Max-Heap ca:
Inserarea în grămada maximă
Implementarea operației de inserare în Max-Heap:
C++
programare java numere prime
// 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[părinte]) {>>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]>>>>) {> >// 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[părinte]) {>>>// 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[părinte]) {>>// 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[părinte]) {>>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]>>>>:> >if>arr[i]>arr[părinte]:>>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....>'''>>>Ieșire15 5 10 2 4 3>Complexitatea timpului: O(log(n)) ( unde n este numărul de elemente din heap )
Spațiu auxiliar: Pe)2. Ștergerea în structura de date Max-Heap :
Ștergerea unui element în orice poziție intermediară din heap poate fi costisitoare, așa că putem pur și simplu înlocui elementul de șters cu ultimul element și șterge ultimul element din heap.
- Înlocuiți rădăcina sau elementul de șters cu ultimul element.
- Ștergeți ultimul element din Heap.
- Deoarece ultimul element este acum plasat în poziția nodului rădăcină. Deci, este posibil să nu urmeze proprietatea heap. Prin urmare, înghesuiți ultimul nod plasat la poziția rădăcinii.
Ilustrare :
Să presupunem că Heap-ul este un Max-Heap ca:
Structura de date Max Heap
Elementul de șters este root, adică 10.
Proces :
Ultimul element este 4.
Pasul 1: Înlocuiți ultimul element cu root și ștergeți-l.
Max Heap
Pasul 2 : Heapify rădăcină.
Heap final:
Max Heap
Implementarea operațiunii de ștergere în 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
elimina primul caracter din excel
// 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[cel mai mare]): cel mai mare = l #Dacă copilul drept este mai mare decât cel mai mare până acum dacă (r și arr[r]> arr[mai mare]): cel mai mare = r # Dacă cel mai mare nu este rădăcină dacă (cel mai mare != i) : arr[i],arr[largest]=arr[largest],arr[i] #Recursiv heapify sub-arborele afectat heapify(arr, n, cei mai mari) #Funcție pentru a șterge rădăcina din Heap def deleteRoot(arr): global n # Obțineți ultimul element lastElement = arr[n - 1] # Înlocuiți rădăcina cu ultimul element arr[0] = lastElement # Reduceți dimensiunea heap-ului cu 1 n = n - 1 # heapify nodul rădăcină heapify(arr, n, 0) # O funcție utilitar pentru a tipări o matrice de dimensiune n def printArray(arr, n): pentru i în interval(n): print(arr[i],end=' ') print() # Cod driver if __name__ == '__main__': # Reprezentare matrice a Max-Heap # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot( arr) printArray(arr, n) # Acest cod este contribuit de Rajat Kumar.>>>>șir în tabloul c5 4 3 2> Complexitatea timpului : O(log n) unde n este niciun element din heap
Spațiu auxiliar: Pe)3.Operațiune de vizualizare pe Structura de date Max-heap:
Pentru a accesa elementul maxim (adică rădăcina heap-ului), este returnată valoarea nodului rădăcină. Complexitatea timpului de peek într-un heap maxim este O(1).
Elementul de vârf al Max-Heap
Implementarea operațiunii Peek în 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]>>>>.heap[largestChildIndex]) {> >largestChildIndex = leftChildIndex;>>}>>if>(rightChildIndex <>this>.heap.length &&>this>.heap[rightChildIndex]>>>>.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)>>>IeșirePeak element: 9>Complexitatea timpului :
- Într-un heap maxim implementat folosind unmatricesau o listă, elementul de vârf poate fi accesat în timp constant, O(1), deoarece este întotdeauna situat la rădăcina heap-ului.
- Într-un heap maxim implementat folosind aarbore binar, elementul de vârf poate fi accesat și în timpul O(1), deoarece este întotdeauna situat la rădăcina arborelui.
Spațiu auxiliar: Pe)
4.Operațiune Heapify pe Max-heap Data Structure:
O operație heapify poate fi folosită pentru a crea un heap maxim dintr-o matrice nesortată. Acest lucru se face pornind de la ultimul nod care nu este frunză și efectuând în mod repetat operația de bule până când toate nodurile satisfac proprietatea heap. Complexitatea de timp a heapify într-un heap maxim este O(n).
Operațiuni Heapify în Max-Heap
5.Operațiune de căutare pe Structura de date Max-heap:
Pentru a căuta un element în heap-ul maxim, se poate efectua o căutare liniară peste matricea care reprezintă heap-ul. Cu toate acestea, complexitatea în timp a unei căutări liniare este O(n), care nu este eficientă. Prin urmare, căutarea nu este o operațiune utilizată în mod obișnuit într-un heap maxim.
Iată un exemplu de cod care arată cum să căutați un element într-un heap maxim folosind 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>ultimul) {>>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.'>);>}>unde sunt setările browserului>>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.'>)>>>IeșireElement found in the max heap.>Complexitatea timpului : O(n), unde n este dimensiunea mormanului.
Spațiu auxiliar : Pe),Aplicații ale structurii de date Max-Heap:
- Algoritmul Heapsort: Structura de date heap este baza pentru algoritmul heapsort, care este un algoritm de sortare eficient cu o complexitate de timp în cel mai rău caz de O(n log n). Algoritmul heapsort este utilizat în diverse aplicații, inclusiv indexarea bazelor de date și analiza numerică.
- Gestionarea memoriei: Structura de date heap este utilizată în sistemele de gestionare a memoriei pentru a aloca și dezaloca memoria în mod dinamic. Heap-ul este folosit pentru a stoca blocurile de memorie, iar structura de date heap este utilizată pentru a gestiona eficient blocurile de memorie și a le aloca programelor după cum este necesar.
- Algoritmi grafici: Structura de date heap este utilizată în diverși algoritmi de grafic, inclusiv algoritmul lui Dijkstra, algoritmul lui Prim și algoritmul lui Kruskal. Acești algoritmi necesită implementare eficientă a cozii de prioritate, care poate fi realizată folosind structura de date heap.
- Programarea postului: Structura de date heap este utilizată în algoritmii de programare a sarcinilor, în care sarcinile sunt programate pe baza priorității sau a termenului limită. Structura de date heap permite accesul eficient la sarcina cu cea mai mare prioritate, ceea ce o face o structură de date utilă pentru aplicațiile de programare a joburilor.
Avantajele structurii de date Max-Heap:
- Menține eficient valoarea maximă: Un heap maxim permite accesul în timp constant la elementul maxim din heap, ceea ce îl face util în aplicațiile în care elementul maxim trebuie găsit rapid.
- Operații eficiente de inserare și ștergere: Operațiile de inserare și ștergere într-un heap maxim au o complexitate de timp de O(log n), ceea ce le face eficiente pentru colecții mari de elemente.
- Cozi prioritare: Un heap maxim poate fi folosit pentru a implementa o coadă de prioritate, care este utilă în multe aplicații, cum ar fi programarea sarcinilor, prioritizarea sarcinilor și simularea bazată pe evenimente.
- Triere: Un heap maxim poate fi folosit pentru a implementa heapsort, care este un algoritm de sortare eficient care are o complexitate de timp în cel mai rău caz de O(n log n).
- Eficiența spațiului: Un heap maxim poate fi implementat ca o matrice, care necesită mai puțină memorie în comparație cu alte structuri de date, cum ar fi un arbore de căutare binar sau o listă legată.
Structura de date max heap este un instrument util și eficient pentru menținerea și manipularea colecțiilor de elemente, în special atunci când elementul maxim trebuie accesat rapid sau atunci când elementele trebuie sortate sau prioritizate.
