A Max-Heap je definovaný ako typ Štruktúra údajov haldy je typ binárneho stromu, ktorý sa bežne používa v informatike na rôzne účely vrátane triedenia, vyhľadávania a organizovania údajov.
Úvod do dátovej štruktúry Max-Heap
Účel a prípady použitia Max-Heap:
- Prioritný front: Jedným z primárnych použití štruktúry údajov haldy je implementácia prioritných frontov.
- Zoradenie haldy: Štruktúra údajov haldy sa používa aj v triediacich algoritmoch.
- Správa pamäte: Štruktúra údajov haldy sa používa aj pri správe pamäte. Keď program potrebuje dynamicky alokovať pamäť, používa dátovú štruktúru haldy na sledovanie dostupnej pamäte.
- Dijkstrov algoritmus najkratšej cesty používa dátovú štruktúru haldy na sledovanie vrcholov s najkratšou cestou zo zdrojového vrcholu.
Štruktúra údajov Max-Heap v rôznych jazykoch:
1. Max-Heap v C++
Maximálna halda môže byť implementovaná pomocou prioritný_front kontajner z Štandardná knižnica šablón (STL) . The prioritný_front kontajner je typ adaptéra kontajnera, ktorý poskytuje spôsob ukladania prvkov do dátovej štruktúry podobnej frontu, v ktorej má každý prvok priradenú prioritu.
Synt ax: priority_queuemaxH;>2. Max-Heap v jazyku Java
V jazyku Java je možné implementovať maximálnu hromadu pomocou PriorityQueue triedy od balík java.util . Trieda PriorityQueue je prioritný front, ktorý poskytuje spôsob ukladania prvkov do dátovej štruktúry podobnej frontu, v ktorej má každý prvok priradenú prioritu.
Syntax : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());>3. Max-Heap v Pythone
V Pythone je možné implementovať maximálnu hromadu pomocou heapq modul, ktorý poskytuje funkcie na implementáciu hromady. Modul heapq konkrétne poskytuje spôsob vytvárania a manipulácie s dátovými štruktúrami haldy.
Synt ax: heap = [] heapify(heap)>4. Max-Heap v C#
V C# môže byť maximálna halda implementovaná pomocou triedy PriorityQueue z System.Collections.Generic namespace . Trieda PriorityQueue je prioritný front, ktorý poskytuje spôsob ukladania prvkov do dátovej štruktúry podobnej frontu, v ktorej má každý prvok priradenú prioritu.
Syntax: var maxHeap = new PriorityQueue((a, b) =>b - a);>5. Max-Heap v JavaScripte
Maximálna halda je binárny strom, v ktorom má každý uzol hodnotu väčšiu alebo rovnú jeho potomkom. V JavaScripte môžete implementovať maximálnu haldu pomocou poľa, kde prvý prvok predstavuje koreňový uzol a potomkovia uzla na indexe i sa nachádzajú na indexoch 2i+1 a 2i+2.
Syntax: const miaxHeap = new MaxHeap();>Rozdiel medzi maximálnou a minimálnou haldou
Min. halda Max Heap 1. V Min-Heap kľúč prítomný v koreňovom uzle musí byť menší alebo rovný medzi kľúčmi prítomnými u všetkých jeho potomkov. V Max-Heap kľúč prítomný v koreňovom uzle musí byť väčší alebo rovný medzi kľúčmi prítomnými vo všetkých jeho potomkoch. 2. V Min-Heap je minimálny kľúčový prvok prítomný v koreňovom adresári. V Max-Heap je maximálny kľúčový prvok prítomný v koreňovom adresári. 3. Min-Heap používa vzostupnú prioritu. Max-Heap používa zostupnú prioritu. 4. Pri konštrukcii min-hromady má prednosť najmenší prvok. Pri konštrukcii Max-Heap má prednosť najväčší prvok. 5. V Min-Heap je najmenší prvok prvý, ktorý sa vysype z haldy. V Max-Heap je najväčší prvok prvý, ktorý sa vysype z haldy. Interná implementácia dátovej štruktúry Max-Heap:
A Minimálna halda je zvyčajne reprezentovaná ako pole .
- Koreňový prvok bude v Arr[0] .
- Pre akýkoľvek i-tý uzol Arr[i].
- ľavé dieťa je uložené v indexe 2i+1
- Pravé dieťa je uložené v indexe 2i+2
- Rodič je uložený na poschodí indexu ((i-1)/2)
Interná implementácia Max-Heap vyžaduje 3 hlavné kroky:
- Vkladanie : Ak chcete do haldy vložiť nový prvok, pridá sa na koniec poľa a potom sa prebubláva, kým nespĺňa vlastnosť haldy.
- Vymazanie : Ak chcete odstrániť maximálny prvok (koreň haldy), posledný prvok v poli sa vymení za koreň a nový koreň sa prebubláva, kým nespĺňa vlastnosť haldy.
- Heapify : Operáciu heapify možno použiť na vytvorenie maximálnej haldy z nezoradeného poľa.
Operácie na dátovej štruktúre Max-heap a ich implementácia:
Tu sú niektoré bežné operácie, ktoré možno vykonať na dátovej štruktúre haldy,
1. Vloženie do dátovej štruktúry Max-Heap :
Prvky môžu byť vložené do haldy podľa podobného prístupu, ako je diskutované vyššie pre vymazanie. Cieľom je:
- Najprv zväčšite veľkosť haldy o 1, aby bolo možné uložiť nový prvok.
- Vložte nový prvok na koniec haldy.
- Tento novo vložený prvok môže skresliť vlastnosti Heap pre jeho rodičov. Takže, aby ste zachovali vlastnosti haldy, zväčšite tento novo vložený prvok podľa prístupu zdola nahor.
Ilustrácia:
Predpokladajme, že halda je maximálna halda ako:
Vloženie do maximálnej haldy
Implementácia operácie vkladania v Max-Heap:
C++
centos vs redhat
// 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[rodič]) {>>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[rodič]) {>>>// 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[rodič]) {>>// 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[rodič]) {>>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[rodič]:>>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....>'''>>>Výkon15 5 10 2 4 3>Časová zložitosť: O(log(n)) ( kde n je počet prvkov v halde )
Pomocný priestor: O(n)2. Odstránenie v dátovej štruktúre Max-Heap :
Vymazanie prvku na ktorejkoľvek pozícii medzičlánku v halde môže byť nákladné, takže môžeme jednoducho nahradiť prvok, ktorý sa má odstrániť, posledným prvkom a vymazať posledný prvok haldy.
- Nahraďte koreň alebo prvok, ktorý sa má odstrániť, posledným prvkom.
- Odstráňte posledný prvok z haldy.
- Keďže posledný prvok je teraz umiestnený na pozícii koreňového uzla. Takže nemusí nasledovať vlastnosť haldy. Preto navŕšte posledný uzol umiestnený na pozícii koreňa.
Ilustračné :
Predpokladajme, že halda je maximálna halda ako:
Štruktúra údajov maximálnej haldy
Prvok, ktorý sa má odstrániť, je root, t.j. 10.
Proces :
Posledným prvkom je 4.
Krok 1: Nahraďte posledný prvok rootom a odstráňte ho.
Max Heap
Krok 2 : Heapify root.
Konečná halda:
Max Heap
Implementácia operácie vymazania v 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>>vybrať ako>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[najväčší]): najväčší = l #Ak je pravé dieťa väčšie ako doteraz najväčšie if (r a arr[r]> arr[najväčšie]): najväčšie = r # Ak najväčšie nie je koreň if (najväčšie != i) : arr[i],arr[najväčší]=arr[najväčší],arr[i] #Rekurzívne heapify postihnutý podstrom heapify(arr, n, najväčší) #Funkcia na odstránenie koreňa z haldy def deleteRoot(arr): global n # Získať posledný prvok lastElement = arr[n - 1] # Nahradiť koreň posledným prvkom arr[0] = lastElement # Zmenšiť veľkosť haldy o 1 n = n - 1 # heapify koreňový uzol heapify(arr, n, 0) # Pomocná funkcia na tlač poľa veľkosti n def printArray(arr, n): pre i v rozsahu (n): print(arr[i],end=' ') print() # Kód ovládača, ak __name__ == '__main__': # Reprezentácia poľa Max-Heap # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot( arr) printArray(arr, n) # Tento kód prispel Rajat Kumar.>>>Výkon5 4 3 2>Časová zložitosť : O(log n), kde n je číslo prvkov v halde
Pomocný priestor: O(n)3.Operácia náhľadu na dátovej štruktúre Max-heap:
Na prístup k maximálnemu prvku (t. j. ku koreňu haldy) sa vráti hodnota koreňového uzla. Časová zložitosť náhľadu v maximálnej halde je O(1).
Vrcholový prvok maximálnej haldy
Implementácia operácie Peek v 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#
reťazec poľa v 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)>>>VýkonPeak element: 9>Časová zložitosť :
- V maximálnej hromade implementovanej pomocou anpolealebo zoznam, vrcholový prvok môže byť prístupný v konštantnom čase, O(1), pretože je vždy umiestnený v koreni haldy.
- V maximálnej hromade implementovanej pomocou abinárny strom, vrcholový prvok môže byť tiež prístupný v čase O(1), pretože sa vždy nachádza v koreni stromu.
Pomocný priestor: O(n)
4.Operácia Heapify na dátovej štruktúre Max-heap:
Operáciu heapify možno použiť na vytvorenie maximálnej haldy z nezoradeného poľa. To sa dosiahne tak, že sa začne v poslednom nelistovom uzle a opakovane sa vykoná operácia bubliny, kým všetky uzly nesplnia vlastnosť haldy. Časová zložitosť heapify v maximálnej halde je O(n).
Operácie Heapify v Max-Heap
5.Operácia vyhľadávania na dátovej štruktúre Max-heap:
Ak chcete vyhľadať prvok v maximálnej halde, možno vykonať lineárne vyhľadávanie v poli, ktoré predstavuje haldu. Časová zložitosť lineárneho vyhľadávania je však O(n), čo nie je efektívne. Preto vyhľadávanie nie je bežne používanou operáciou v maximálnej hromade.
Tu je príklad kódu, ktorý ukazuje, ako hľadať prvok v maximálnej hromade pomocou 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;>}>rok bol vynájdený počítač>>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>>teplota =>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>posledný) {>>break>;>>}>>int>rightChild = leftChild + 1;>>if>(rightChild <= last && heap[leftChild].CompareTo(heap[rightChild]) < 0) {>>leftChild = rightChild;>>}>>if>(heap[parent].CompareTo(heap[leftChild]) <0) {>>T tmp = heap[parent];>>heap[parent] = heap[leftChild];>>heap[leftChild] = tmp;>>parent = leftChild;>>}>else>{>>break>;>>}>>}>>return>frontItem;>>}>>public>T Peek() {>>return>heap[0];>>}>>public>int>Count {>>get>{>>return>heap.Count;>>}>>}>}>>>Javascript
const maxHeap =>new>PriorityQueue((a, b) =>b - a);>maxHeap.add(3);>// insert elements into the priority queue>maxHeap.add(1);>maxHeap.add(4);>maxHeap.add(1);>maxHeap.add(6);>const element = 6;>// element to search for>let found =>false>;>// Copy the max heap to a temporary queue and search for the element>const temp =>new>PriorityQueue(maxHeap);>while>(!temp.isEmpty()) {>if>(temp.poll() === element) {>found =>true>;>break>;>}>}>if>(found) {>console.log(>'Element found in the max heap.'>);>}>else>{>console.log(>'Element not found in the max heap.'>);>}>>>Python3
import>heapq>max_heap>=>[>10>,>8>,>7>,>6>,>5>,>3>,>2>,>1>]># example max heap>heapq._heapify_max(max_heap)>element>=>6># element to search for>found>=>False># Copy the max heap to a temporary list and search for the element>temp>=>list>(max_heap)>while>temp:>>if>heapq._heappop_max(temp)>=>=>element:>>found>=>True>>break>if>found:>>print>(>'Element found in the max heap.'>)>else>:>>print>(>'Element not found in the max heap.'>)>>>VýkonElement found in the max heap.>Časová zložitosť : O(n), kde n je veľkosť haldy.
Pomocný priestor : O(n),Aplikácie dátovej štruktúry Max-Heap:
- Algoritmus Heapsort: Štruktúra údajov haldy je základom pre algoritmus heapsort, čo je efektívny triediaci algoritmus s časovou zložitosťou najhoršieho prípadu O(n log n). Algoritmus heapsort sa používa v rôznych aplikáciách vrátane indexovania databáz a numerickej analýzy.
- Správa pamäte: Štruktúra údajov haldy sa používa v systémoch správy pamäte na dynamickú alokáciu a uvoľnenie pamäte. Halda sa používa na ukladanie pamäťových blokov a dátová štruktúra haldy sa používa na efektívne spravovanie pamäťových blokov a ich prideľovanie programom podľa potreby.
- Algoritmy grafov: Štruktúra údajov haldy sa používa v rôznych grafových algoritmoch, vrátane Dijkstrovho algoritmu, Primovho algoritmu a Kruskalovho algoritmu. Tieto algoritmy vyžadujú efektívnu implementáciu prioritného frontu, čo je možné dosiahnuť pomocou štruktúry údajov haldy.
- Plánovanie práce: Štruktúra údajov haldy sa používa v algoritmoch plánovania úloh, kde sú úlohy naplánované na základe ich priority alebo termínu. Štruktúra údajov haldy umožňuje efektívny prístup k úlohe s najvyššou prioritou, čo z nej robí užitočnú štruktúru údajov pre aplikácie plánovania úloh.
Výhody dátovej štruktúry Max-Heap:
- Efektívne udržujte maximálnu hodnotu: Maximálna halda umožňuje nepretržitý prístup k maximálnemu prvku v halde, čo je užitočné v aplikáciách, kde je potrebné rýchlo nájsť maximálny prvok.
- Efektívne operácie vkladania a odstraňovania: Operácie vloženia a vymazania v maximálnej halde majú časovú zložitosť O(log n), vďaka čomu sú efektívne pre veľké kolekcie prvkov.
- Prioritné fronty: Maximálnu haldu možno použiť na implementáciu prioritného frontu, čo je užitočné v mnohých aplikáciách, ako je plánovanie úloh, prioritizácia úloh a simulácia riadená udalosťami.
- Triedenie: Maximálnu haldu možno použiť na implementáciu heapsortu, čo je efektívny triediaci algoritmus, ktorý má v najhoršom prípade časovú zložitosť O(n log n).
- Priestorová efektívnosť: Maximálna halda môže byť implementovaná ako pole, ktoré vyžaduje menej pamäte v porovnaní s inými dátovými štruktúrami, ako je binárny vyhľadávací strom alebo prepojený zoznam.
Štruktúra údajov maximálnej haldy je užitočným a efektívnym nástrojom na údržbu a manipuláciu s kolekciami prvkov, najmä ak je potrebné rýchlo získať prístup k maximálnemu prvku alebo ak je potrebné prvky triediť alebo uprednostňovať.
