A Max-Heap apibrėžiamas kaip tipas Krūvos duomenų struktūra yra dvejetainio medžio tipas, kuris kompiuterių moksle dažniausiai naudojamas įvairiems tikslams, įskaitant duomenų rūšiavimą, paiešką ir tvarkymą.
Max-Heap duomenų struktūros įvadas
Max-Heap paskirtis ir naudojimo atvejai:
- Prioritetinė eilė: Vienas iš pagrindinių krūvos duomenų struktūros naudojimo būdų yra prioritetinių eilių įgyvendinimas.
- Krūvos rūšiavimas: Krūvos duomenų struktūra taip pat naudojama rūšiavimo algoritmuose.
- Atminties valdymas: Krūvos duomenų struktūra taip pat naudojama atminties valdymui. Kai programai reikia dinamiškai paskirstyti atmintį, ji naudoja krūvos duomenų struktūrą, kad galėtų sekti turimą atmintį.
- Dijkstra trumpiausio kelio algoritmas naudoja krūvos duomenų struktūrą, kad galėtų sekti viršūnes trumpiausiu keliu nuo šaltinio viršūnės.
Max-Heap duomenų struktūra skirtingomis kalbomis:
1. Max-Heap C++
Maksimali krūva gali būti įdiegta naudojant prioriteto_eilė konteineris iš Standartinė šablonų biblioteka (STL) . The prioriteto_eilė konteineris yra konteinerio adapterio tipas, suteikiantis galimybę saugoti elementus į eilę panašioje duomenų struktūroje, kurioje kiekvienas elementas turi su juo susietą prioritetą.
Synt ax: priority_queuemaxH;>2. Max-Heap Java
Java programoje maksimali krūva gali būti įdiegta naudojant PriorityQueue klasė nuo java.util paketą . PriorityQueue klasė yra prioritetinė eilė, kuri suteikia galimybę saugoti elementus į eilę panašioje duomenų struktūroje, kurioje kiekvienas elementas turi su juo susietą prioritetą.
Syntax : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());>3. Max-Heap Python
Python programoje maksimali krūva gali būti įdiegta naudojant heapq modulis, kuriame pateikiamos krūvos įgyvendinimo funkcijos. Konkrečiai, heapq modulis suteikia galimybę kurti ir valdyti krūvos duomenų struktūras.
Synt ax: heap = [] heapify(heap)>4. Max-Heap C#
C# kalboje maksimali krūva gali būti įdiegta naudojant PriorityQueue klasę iš Sistema.Kolekcijos.Bendroji vardų erdvė . PriorityQueue klasė yra prioritetinė eilė, kuri suteikia galimybę saugoti elementus į eilę panašioje duomenų struktūroje, kurioje kiekvienas elementas turi su juo susietą prioritetą.
Syntax: var maxHeap = new PriorityQueue((a, b) =>b - a);>>5. Max-Heap JavaScript
Maksimali krūva yra dvejetainis medis, kuriame kiekvieno mazgo reikšmė yra didesnė arba lygi jo antriniams. „JavaScript“ galite įdiegti maksimalų krūvą naudodami masyvą, kur pirmasis elementas žymi šakninį mazgą, o mazgo antrinės dalys indekse i yra prie indeksų 2i+1 ir 2i+2.
Skirtumas tarp Max ir Min Heap
Min. krūva Max Heap 1. Min-Heap raktas, esantis šakniniame mazge, turi būti mažesnis arba lygus tarp visų antrinių raktų. „Max-Heap“ šakniniame mazge esantis raktas turi būti didesnis arba lygus tarp visų antrinių raktų. 2. Min-Heap minimalus pagrindinis elementas, esantis šaknyje. Max-Heap didžiausias pagrindinis elementas, esantis šaknyje. 3. Min-Heap naudoja didėjantį prioritetą. Max-Heap naudoja mažėjantį prioritetą. 4. Konstruojant „Min-Heap“ pirmenybė teikiama mažiausiam elementui. „Max-Heap“ konstrukcijoje pirmenybė teikiama didžiausiam elementui. 5. Min-Heap mažiausias elementas yra pirmasis, kuris iškeliamas iš krūvos. Max-Heap didžiausias elementas yra pirmasis, kuris ištraukiamas iš krūvos. Vidinis Max-Heap duomenų struktūros įgyvendinimas:
A Minimali krūva paprastai vaizduojama kaip masyvas .
- Šakninis elementas bus adresu Arr[0] .
- Bet kuriam i-jam mazgui Arr[i].
- paliktas vaikas saugomas indekse 2i+1
- Dešinysis vaikas saugomas rodyklėje 2i+2
- Tėvas saugomas indekso aukšte ((i-1)/2)
Vidiniam „Max-Heap“ diegimui reikia 3 pagrindinių žingsnių:
- Įdėjimas : norint į krūvą įterpti naują elementą, jis įtraukiamas į masyvo pabaigą, o tada burbuliuojamas, kol atitinka krūvos savybę.
- Ištrynimas : norint ištrinti maksimalų elementą (krūvos šaknį), paskutinis masyvo elementas pakeičiamas šaknimis, o naujasis šaknis nuleidžiamas žemyn, kol atitinka krūvos savybę.
- Sukrauti : krūvos didinimo operacija gali būti naudojama norint sukurti didžiausią krūvą iš nerūšiuoto masyvo.
„Max-heap“ duomenų struktūros operacijos ir jų įgyvendinimas:
Štai keletas įprastų operacijų, kurias galima atlikti su krūvos duomenų struktūros duomenų struktūra,
1. Įterpimas į Max-Heap duomenų struktūrą :
Elementai gali būti įterpti į krūvą taikant panašų metodą, kaip aprašyta anksčiau, norint ištrinti. Idėja tokia:
- Pirmiausia padidinkite krūvos dydį 1, kad būtų galima išsaugoti naują elementą.
- Įdėkite naują elementą krūvos gale.
- Šis naujai įdėtas elementas gali iškraipyti Heap savybes savo tėvams. Taigi, norėdami išlaikyti krūvos savybes, padidinkite šį naujai įdėtą elementą, vadovaudamiesi metodu „iš apačios į viršų“.
Iliustracija:
Tarkime, kad krūva yra didžiausia krūva:
Įterpimas į maksimalų krūvą
Įterpimo operacijos įgyvendinimas Max-Heap:
C++
cast int į eilutę java
// 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 [tėvas]) {>>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 [tėvas]) {>>>// 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 [tėvas]) {>>// 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 [tėvas]) {>>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[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....>'''>>>Išvestis15 5 10 2 4 3>Laiko sudėtingumas: O(log(n)) ( kur n yra elementų skaičius krūvoje )
Pagalbinė erdvė: O(n)2. Ištrynimas Max-Heap duomenų struktūroje :
Elemento ištrynimas bet kurioje tarpinėje krūvos pozicijoje gali būti brangus, todėl galime tiesiog pakeisti elementą, kurį reikia ištrinti, paskutiniu elementu ir ištrinti paskutinį krūvos elementą.
- Pakeiskite šaknį arba elementą, kurį norite ištrinti, paskutiniu elementu.
- Ištrinkite paskutinį elementą iš krūvos.
- Kadangi paskutinis elementas dabar yra pagrindinio mazgo vietoje. Taigi, jis gali nesilaikyti krūvos savybės. Todėl surinkite paskutinį mazgą, esantį šaknies vietoje.
Iliustracija :
Tarkime, kad krūva yra didžiausia krūva:
Didžiausia krūvos duomenų struktūra
Elementas, kurį reikia ištrinti, yra root, ty 10.
Procesas :
Paskutinis elementas yra 4.
1 žingsnis: Paskutinį elementą pakeiskite šaknimi ir ištrinkite.
Max Heap
2 žingsnis : Sukaupti šaknį.
Galutinė krūva:
Max Heap
Ištrynimo operacijos įgyvendinimas „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; }>prasideda java>>Java
// Java program for implement deletion in Heaps>public>class>deletionHeap {>>// To heapify a subtree rooted with node i which is>>// an index in arr[].Nn is size of heap>>static>void>heapify(>int>arr[],>int>n,>int>i)>>{>>int>largest = i;>// Initialize largest as root>>int>l =>2>* i +>1>;>// left = 2*i + 1>>int>r =>2>* i +>2>;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i) {>>int>swap = arr[i];>>arr[i] = arr[largest];>>arr[largest] = swap;>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>>}>>// Function to delete the root from Heap>>static>int>deleteRoot(>int>arr[],>int>n)>>{>>// Get the last element>>int>lastElement = arr[n ->1>];>>// Replace root with first element>>arr[>0>] = lastElement;>>// Decrease size of heap by 1>>n = n ->1>;>>// heapify the root node>>heapify(arr, n,>0>);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size N */>>static>void>printArray(>int>arr[],>int>n)>>{>>for>(>int>i =>0>; i System.out.print(arr[i] + ' '); System.out.println(); } // Driver Code public static void main(String args[]) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[] = { 10, 5, 3, 2, 4 }; int n = arr.length; n = deleteRoot(arr, n); printArray(arr, n); } }>>>C#
// C# program for implement deletion in Heaps>using>System;>public>class>deletionHeap>{>>// To heapify a subtree rooted with node i which is>>// an index in arr[].Nn is size of heap>>static>void>heapify(>int>[]arr,>int>n,>int>i)>>{>>int>largest = i;>// Initialize largest as root>>int>l = 2 * i + 1;>// left = 2*i + 1>>int>r = 2 * i + 2;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i)>>{>>int>swap = arr[i];>>arr[i] = arr[largest];>>arr[largest] = swap;>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>>}>>// Function to delete the root from Heap>>static>int>deleteRoot(>int>[]arr,>int>n)>>{>>// Get the last element>>int>lastElement = arr[n - 1];>>// Replace root with first element>>arr[0] = lastElement;>>// Decrease size of heap by 1>>n = n - 1;>>// heapify the root node>>heapify(arr, n, 0);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size N */>>static>void>printArray(>int>[]arr,>int>n)>>{>>for>(>int>i = 0; i Console.Write(arr[i] + ' '); Console.WriteLine(); } // Driver Code public static void Main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int []arr = { 10, 5, 3, 2, 4 }; int n = arr.Length; n = deleteRoot(arr, n); printArray(arr, n); } } // This code is contributed by Ryuga>>>Javascript
>>// Javascript program for implement deletion in Heaps>>>// To heapify a subtree rooted with node i which is>>// an index in arr[].Nn is size of heap>>function>heapify(arr, n, i)>>{>>let largest = i;>// Initialize largest as root>>let l = 2 * i + 1;>// left = 2*i + 1>>let r = 2 * i + 2;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i)>>{>>let swap = arr[i];>>arr[i] = arr[largest];>>arr[largest] = swap;>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>>}>>// Function to delete the root from Heap>>function>deleteRoot(arr, n)>>{>>// Get the last element>>let lastElement = arr[n - 1];>>// Replace root with first element>>arr[0] = lastElement;>>// Decrease size of heap by 1>>n = n - 1;>>// heapify the root node>>heapify(arr, n, 0);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size N */>>function>printArray(arr, n)>>{>>for>(let i = 0; i document.write(arr[i] + ' '); document.write(''); } let arr = [ 10, 5, 3, 2, 4 ]; let n = arr.length; n = deleteRoot(arr, n); printArray(arr, n); // This code is contributed by divyeshrabdiya07.>>>Python3
# Python 3 program for implement deletion in Heaps># To heapify a subtree rooted with node i which is># an index of arr[] and n is the size of heap>def>heapify(arr, n, i):>>largest>=>i>#Initialize largest as root>>l>=>2>*>i>+>1># left = 2*i + 1>>r>=>2>*>i>+>2># right = 2*i + 2>>#If left child is larger than root>>if>(l and arr[l]>arr[didžiausias]): didžiausias = l #Jei dešinysis vaikas didesnis už didžiausią iki šiol if (r ir arr[r]> arr[didžiausias]): didžiausias = r # Jei didžiausias nėra šaknis if (didžiausias != i) : arr[i],arr[didžiausias]=arr[didžiausias],arr[i] #Rekursyviai įterpti paveiktą medį heapify(arr, n, didžiausias) #Funkcija ištrinti šaknį iš Heap def deleteRoot(arr): global n # Gauti paskutinį elementą lastElement = arr[n - 1] # Pakeisti šaknį paskutiniu elementu arr[0] = lastElement # Sumažinti krūvos dydį 1 n = n - 1 # sukrauti šakninį mazgą heapify(arr, n, 0) # Naudingoji funkcija spausdinti n dydžio masyvą def printArray(arr, n): i diapazone (n): print(arr[i],end=' ') print() # Tvarkyklės kodas, jei __name__ == '__main__': # Max-Heap masyvo atvaizdavimas # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot( arr) printArray(arr, n) # Šį kodą sukūrė Rajat Kumar.>>>5 4 3 2> Laiko sudėtingumas : O(log n), kur n yra elementų skaičius krūvoje
Pagalbinė erdvė: O(n)3.„Max-heap“ duomenų struktūros žvilgtelėjimo operacija:
Norint pasiekti maksimalų elementą (t. y. krūvos šaknį), grąžinama šakninio mazgo reikšmė. Žvilgtelėjimo į didžiausią krūvą laiko sudėtingumas yra O(1).
Maksimalus „Max Heap“ elementas
„Peek“ operacijos įgyvendinimas „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);>>>tokios svetainės kaip coomeetPython3
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)>>>IšvestisPeak element: 9>Laiko sudėtingumas :
- Didžiausioje krūvoje, įdiegtoje naudojant anmasyvasarba sąrašą, smailės elementą galima pasiekti pastoviu laiku O(1), nes jis visada yra krūvos šaknyje.
- Didžiausioje krūvoje, įdiegtoje naudojant advejetainis medis, piko elementą taip pat galima pasiekti per O (1) laiką, nes jis visada yra medžio šaknyje.
Pagalbinė erdvė: O(n)
4.„Max-heap“ duomenų struktūros „Heapify“ operacija:
Norint sukurti didžiausią krūvą iš nerūšiuoto masyvo, galima naudoti krūvos didinimo operaciją. Tai atliekama pradedant nuo paskutinio ne lapo mazgo ir pakartotinai atliekant burbulo mažinimo operaciją, kol visi mazgai patenkins krūvos savybę. Didžiausios krūvos krūvos sudėtingumas laiko atžvilgiu yra O(n).
„Heapify“ operacijos „Max-Heap“.
5.Paieškos operacija „Max-heap“ duomenų struktūroje:
Norint ieškoti elemento didžiausioje krūvoje, galima atlikti tiesinę paiešką masyve, kuris atstovauja krūvą. Tačiau linijinės paieškos laiko sudėtingumas yra O (n), o tai nėra efektyvu. Todėl paieška nėra dažniausiai naudojama operacija didžiausioje krūvoje.
Štai kodo pavyzdys, rodantis, kaip ieškoti elemento didžiausioje krūvoje naudojant std::rasti() :
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#
c++ pora
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>paskutinis) {>>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.'>)>>>IšvestisElement found in the max heap.>Laiko sudėtingumas : O(n), kur n yra krūvos dydis.
Pagalbinė erdvė : O(n),Max-Heap duomenų struktūros pritaikymai:
- Grupės rūšiavimo algoritmas: Krūvos duomenų struktūra yra krūvos rūšiavimo algoritmo, kuris yra efektyvus rūšiavimo algoritmas, kurio laiko sudėtingumas blogiausiu atveju yra O(n log n), pagrindas. Grupės rūšiavimo algoritmas naudojamas įvairiose programose, įskaitant duomenų bazių indeksavimą ir skaitinę analizę.
- Atminties valdymas: Krūvos duomenų struktūra naudojama atminties valdymo sistemose, siekiant dinamiškai paskirstyti ir panaikinti atmintį. Krūva naudojama atminties blokams saugoti, o krūvos duomenų struktūra naudojama efektyviai valdyti atminties blokus ir pagal poreikį juos paskirstyti programoms.
- Grafiniai algoritmai: Krūvos duomenų struktūra naudojama įvairiuose grafų algoritmuose, įskaitant Dijkstra algoritmą, Primo algoritmą ir Kruskal algoritmą. Šie algoritmai reikalauja efektyvaus prioriteto eilės diegimo, kurį galima pasiekti naudojant krūvos duomenų struktūrą.
- Darbo grafikas: Krūvos duomenų struktūra naudojama užduočių planavimo algoritmuose, kur užduotys suplanuojamos pagal jų prioritetą arba terminą. Krūvos duomenų struktūra leidžia efektyviai pasiekti aukščiausio prioriteto užduotį, todėl tai yra naudinga duomenų struktūra darbų planavimo programoms.
Max-Heap duomenų struktūros pranašumai:
- Efektyviai išlaikykite maksimalią vertę: Maksimali krūva leidžia nuolat pasiekti maksimalų krūvos elementą, todėl jis naudingas tais atvejais, kai reikia greitai rasti maksimalų elementą.
- Veiksmingos įterpimo ir ištrynimo operacijos: Įterpimo ir ištrynimo operacijų maksimalioje krūvoje laiko sudėtingumas yra O(log n), todėl jos yra veiksmingos didelėms elementų kolekcijoms.
- Prioritetinės eilės: Didžiausia krūva gali būti naudojama norint įdiegti prioritetinę eilę, kuri yra naudinga daugelyje programų, tokių kaip užduočių planavimas, užduočių prioritetų nustatymas ir įvykiais pagrįstas modeliavimas.
- Rūšiavimas: Didžiausia krūva gali būti naudojama rūšiuoti, kuri yra efektyvus rūšiavimo algoritmas, kurio laiko sudėtingumas blogiausiu atveju yra O(n log n).
- Erdvės efektyvumas: Maksimali krūva gali būti įgyvendinta kaip masyvas, kuriam reikia mažiau atminties, palyginti su kitomis duomenų struktūromis, tokiomis kaip dvejetainis paieškos medis arba susietas sąrašas.
Didžiausios krūvos duomenų struktūra yra naudingas ir efektyvus įrankis elementų rinkiniams prižiūrėti ir manipuliuoti, ypač kai reikia greitai pasiekti didžiausią elementą arba kai elementus reikia rūšiuoti arba nustatyti pagal prioritetus.
