A Max-Heap määritellään tyypiksi Keon tietorakenne on eräänlainen binääripuu, jota käytetään yleisesti tietojenkäsittelytieteessä eri tarkoituksiin, kuten tietojen lajitteluun, etsimiseen ja järjestämiseen.
Johdatus Max-Heap-tietorakenteeseen
Max-Heapin tarkoitus ja käyttötapaukset:
- Prioriteettijono: Yksi keon tietorakenteen ensisijaisista käyttötavoista on prioriteettijonojen toteuttaminen.
- Keon lajittelu: Keon tietorakennetta käytetään myös lajittelualgoritmeissa.
- Muistinhallinta: Keon tietorakennetta käytetään myös muistinhallinnassa. Kun ohjelman on varattava muistia dynaamisesti, se käyttää keon tietorakennetta seuratakseen käytettävissä olevaa muistia.
- Dijkstran lyhimmän polun algoritmi käyttää kasatietorakennetta seuratakseen pisteitä, joilla on lyhin polku lähdepisteestä.
Max-Heap-tietorakenne eri kielillä:
1. Max-Heap C++:ssa
Max kasa voidaan toteuttaa käyttämällä prioriteettijono kontti Standard Template Library (STL) . The prioriteettijono säiliö on eräänlainen säiliösovitin, joka tarjoaa tavan tallentaa elementtejä jonomaiseen tietorakenteeseen, jossa jokaiselle elementille on liitetty prioriteetti.
Synt ax: priority_queuemaxH;>2. Max-Heap Javassa
Javassa maksimikeko voidaan toteuttaa käyttämällä PriorityQueue luokasta alkaen java.util-paketti . PriorityQueue-luokka on prioriteettijono, joka tarjoaa tavan tallentaa elementtejä jonomaiseen tietorakenteeseen, jossa jokaiselle elementille on liitetty prioriteetti.
Syntax : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());>3. Max-Heap Pythonissa
Pythonissa maksimikeko voidaan toteuttaa käyttämällä kasaq moduuli, joka tarjoaa toimintoja kasojen toteuttamiseen. Erityisesti heapq-moduuli tarjoaa tavan luoda ja käsitellä kasatietorakenteita.
Synt ax: heap = [] heapify(heap)>4. Max-Heap C#:ssa
C#:ssa maksimikeko voidaan toteuttaa käyttämällä PriorityQueue-luokkaa osoitteesta System.Collections.Generic namespace . PriorityQueue-luokka on prioriteettijono, joka tarjoaa tavan tallentaa elementtejä jonomaiseen tietorakenteeseen, jossa jokaiselle elementille on liitetty prioriteetti.
Syntax: var maxHeap = new PriorityQueue((a, b) =>b - a);>>5. Max-Heap JavaScriptissä
Max kasko on binääripuu, jossa jokaisella solmulla on arvo suurempi tai yhtä suuri kuin sen lapsi. JavaScriptissä voit toteuttaa maksimikeon käyttämällä taulukkoa, jossa ensimmäinen elementti edustaa juurisolmua ja solmun lapsia indeksissä. i sijaitsevat indekseissä 2i+1 ja 2i+2.
Ero Max ja Min Heap välillä
Min Kasko Max Heap 1. Min-Keapissa juurisolmussa olevan avaimen on oltava pienempi tai yhtä suuri kuin kaikissa sen lapsissa olevien avainten joukossa. Max-Keapissa juurisolmussa olevan avaimen on oltava suurempi tai yhtä suuri kuin kaikissa sen lapsissa olevien avainten joukossa. 2. Min-Heapissa juuressa oleva vähimmäisavainelementti. Max-Keapissa juuressa oleva suurin avainelementti. 3. Min-Heap käyttää nousevaa prioriteettia. Max-Heap käyttää laskevaa prioriteettia. 4. Min-Heapin rakenteessa pienin elementti on etusijalla. Max-Heapin rakenteessa suurin elementti on etusijalla. 5. Min-keossa pienin elementti ponnahtaa ensimmäisenä kasasta. Max-Keossa suurin elementti ponnahtaa kasasta ensimmäisenä. Max-Heap-tietorakenteen sisäinen toteutus:
A Vähimmäiskeko esitetään tyypillisesti taulukkona .
- Juurielementti on osoitteessa Arr[0] .
- Kaikille i:lle solmulle Arr[i].
- vasen lapsi tallennetaan hakemistoon 2i+1
- Oikea lapsi on tallennettu hakemistoon 2i+2
- Vanhempi säilytetään hakemistokerroksessa ((i-1)/2)
Max-Heapin sisäinen käyttöönotto vaatii kolme päävaihetta:
- Lisäys : Jos haluat lisätä uuden elementin kasaan, se lisätään taulukon loppuun ja kuplitetaan, kunnes se täyttää keon ominaisuuden.
- Poistaminen : Maksimielementin (keon juuren) poistamiseksi taulukon viimeinen elementti vaihdetaan juuren kanssa ja uutta juuria kuplitetaan, kunnes se täyttää keon ominaisuuden.
- Kasata kasaan : Kekotustoimintoa voidaan käyttää maksimikeon luomiseen lajittelemattomasta taulukosta.
Max-keap-tietorakenteen toiminnot ja niiden toteutus:
Tässä on joitain yleisiä toimintoja, jotka voidaan suorittaa Keon tietorakenteen tietorakenteelle,
1. Lisäys Max-Heap-tietorakenteeseen :
Elementit voidaan lisätä kasaan noudattamalla samanlaista lähestymistapaa kuin edellä on käsitelty poistoa varten. Ideana on:
- Kasvata ensin keon kokoa yhdellä, jotta se voi tallentaa uuden elementin.
- Lisää uusi elementti kasan loppuun.
- Tämä äskettäin lisätty elementti voi vääristää Keon ominaisuuksia vanhemmilleen. Joten kasan ominaisuuksien säilyttämiseksi kasa tämä vasta lisätty elementti alhaalta ylös -lähestymistapaa noudattaen.
Kuva:
Oletetaan, että kasa on Max-Heap:
Lisäys Max kasaan
Lisäystoiminnon toteutus Max-Heapissa:
C++
kuinka monta näppäintä näppäimistössä on
// 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[vanhempi]) {>>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[vanhempi]) {>>>// 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[vanhempi]) {>>// 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[vanhempi]) {>>let temp = arr[i];>>arr[i] = arr[parent];>>arr[parent] = temp;>>// Recursively heapify the parent node>>heapify(arr, n, parent);>>}>>}>}>// Function to insert a new node to the Heap>function>insertNode(arr, n, Key)>{>>// Increase the size of Heap by 1>>n = n + 1;>>// Insert the element at end of Heap>>arr[n - 1] = Key;>>// Heapify the new node following a>>// Bottom-up approach>>heapify(arr, n, n - 1);>>>return>n;>}>/* A utility function to print array of size N */>function>printArray(arr, n)>{>>for>(let i = 0; i console.log(arr[i] + ' '); console.log(''); } let arr = [ 10, 5, 3, 2, 4 ]; let n = arr.length; let key = 15; n = insertNode(arr, n, key); printArray(arr, n); // This code is contributed by ajaymakvana>>>Python 3
# program to insert new element to Heap># Function to heapify ith node in a Heap># of size n following a Bottom-up approach>def>heapify(arr, n, i):>>parent>=>int>(((i>->1>)>/>2>))>># For Max-Heap>># If current node is greater than its parent>># Swap both of them and call heapify again>># for the parent>>if>arr[parent]>>>:> >if>arr[i]>arr[vanhempi]:>>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....>'''>>>Lähtö15 5 10 2 4 3>Aika monimutkaisuus: O(log(n)) ( missä n on keon elementtien lukumäärä )
Aputila: Päällä)2. Poisto Max-Heap-tietorakenteessa :
Elementin poistaminen mistä tahansa keon välipaikasta voi olla kallista, joten voimme yksinkertaisesti korvata poistettavan elementin viimeisellä elementillä ja poistaa keon viimeisen elementin.
- Korvaa poistettava juuri tai elementti viimeisellä elementillä.
- Poista viimeinen elementti keosta.
- Koska viimeinen elementti on nyt sijoitettu juurisolmun paikkaan. Joten se ei välttämättä seuraa kasan ominaisuutta. Siksi kasaa viimeinen juuren paikkaan sijoitettu solmu.
Kuva :
Oletetaan, että kasa on Max-Heap:
Max Keon tietorakenne
Poistettava elementti on root, eli 10.
Käsitellä asiaa :
Viimeinen elementti on 4.
Vaihe 1: Korvaa viimeinen elementti rootilla ja poista se.
Max Heap
Vaihe 2 : Kasaa juuri.
Viimeinen kasa:
Max Heap
Poistotoiminnon toteutus Max-Heapissa:
C++
muuntaa charista int javaksi
// C++ program for implement deletion in Heaps>#include>using>namespace>std;>// To heapify a subtree rooted with node i which is>// an index of arr[] and n is the size of heap>void>heapify(>int>arr[],>int>n,>int>i)>{>>int>largest = i;>// Initialize largest as root>>int>l = 2 * i + 1;>// left = 2*i + 1>>int>r = 2 * i + 2;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i) {>>swap(arr[i], arr[largest]);>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>}>// Function to delete the root from Heap>void>deleteRoot(>int>arr[],>int>& n)>{>>// Get the last element>>int>lastElement = arr[n - 1];>>// Replace root with last element>>arr[0] = lastElement;>>// Decrease size of heap by 1>>n = n - 1;>>// heapify the root node>>heapify(arr, n, 0);>}>/* A utility function to print array of size n */>void>printArray(>int>arr[],>int>n)>{>>for>(>int>i = 0; i cout << arr[i] << ' '; cout << ' '; } // Driver Code int main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[] = { 10, 5, 3, 2, 4 }; int n = sizeof(arr) / sizeof(arr[0]); deleteRoot(arr, n); printArray(arr, n); return 0; }>>>Java
// Java program for implement deletion in Heaps>public>class>deletionHeap {>>// To heapify a subtree rooted with node i which is>>// an index in arr[].Nn is size of heap>>static>void>heapify(>int>arr[],>int>n,>int>i)>>{>>int>largest = i;>// Initialize largest as root>>int>l =>2>* i +>1>;>// left = 2*i + 1>>int>r =>2>* i +>2>;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i) {>>int>swap = arr[i];>>arr[i] = arr[largest];>>arr[largest] = swap;>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>>}>>// Function to delete the root from Heap>>static>int>deleteRoot(>int>arr[],>int>n)>>{>>// Get the last element>>int>lastElement = arr[n ->1>];>>// Replace root with first element>>arr[>0>] = lastElement;>>// Decrease size of heap by 1>>n = n ->1>;>>// heapify the root node>>heapify(arr, n,>0>);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size N */>>static>void>printArray(>int>arr[],>int>n)>>{>>for>(>int>i =>0>; i System.out.print(arr[i] + ' '); System.out.println(); } // Driver Code public static void main(String args[]) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[] = { 10, 5, 3, 2, 4 }; int n = arr.length; n = deleteRoot(arr, n); printArray(arr, n); } }>>>C#
// C# program for implement deletion in Heaps>using>System;>public>class>deletionHeap>{>>// To heapify a subtree rooted with node i which is>>// an index in arr[].Nn is size of heap>>static>void>heapify(>int>[]arr,>int>n,>int>i)>>{>>int>largest = i;>// Initialize largest as root>>int>l = 2 * i + 1;>// left = 2*i + 1>>int>r = 2 * i + 2;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i)>>{>>int>swap = arr[i];>>arr[i] = arr[largest];>>arr[largest] = swap;>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>>}>>// Function to delete the root from Heap>>static>int>deleteRoot(>int>[]arr,>int>n)>>{>>// Get the last element>>int>lastElement = arr[n - 1];>>// Replace root with first element>>arr[0] = lastElement;>>// Decrease size of heap by 1>>n = n - 1;>>// heapify the root node>>heapify(arr, n, 0);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size N */>>static>void>printArray(>int>[]arr,>int>n)>>{>>for>(>int>i = 0; i Console.Write(arr[i] + ' '); Console.WriteLine(); } // Driver Code public static void Main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int []arr = { 10, 5, 3, 2, 4 }; int n = arr.Length; n = deleteRoot(arr, n); printArray(arr, n); } } // This code is contributed by Ryuga>>>Javascript
>>// Javascript program for implement deletion in Heaps>>>// To heapify a subtree rooted with node i which is>>// an index in arr[].Nn is size of heap>>function>heapify(arr, n, i)>>{>>let largest = i;>// Initialize largest as root>>let l = 2 * i + 1;>// left = 2*i + 1>>let r = 2 * i + 2;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i)>>{>>let swap = arr[i];>>arr[i] = arr[largest];>>arr[largest] = swap;>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>>}>>// Function to delete the root from Heap>>function>deleteRoot(arr, n)>>{>>// Get the last element>>let lastElement = arr[n - 1];>>// Replace root with first element>>arr[0] = lastElement;>>// Decrease size of heap by 1>>n = n - 1;>>// heapify the root node>>heapify(arr, n, 0);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size N */>>function>printArray(arr, n)>>{>>for>(let i = 0; i document.write(arr[i] + ' '); document.write(''); } let arr = [ 10, 5, 3, 2, 4 ]; let n = arr.length; n = deleteRoot(arr, n); printArray(arr, n); // This code is contributed by divyeshrabdiya07.>>>Python 3
# Python 3 program for implement deletion in Heaps># To heapify a subtree rooted with node i which is># an index of arr[] and n is the size of heap>def>heapify(arr, n, i):>>largest>=>i>#Initialize largest as root>>l>=>2>*>i>+>1># left = 2*i + 1>>r>=>2>*>i>+>2># right = 2*i + 2>>#If left child is larger than root>>if>(l and arr[l]>arr[suurin]): suurin = l #Jos oikea lapsi on suurempi kuin suurin tähän mennessä if (r ja arr[r]> arr[suurin]): suurin = r # Jos suurin ei ole juuri if (suurin != i) : arr[i],arr[suurin]=arr[suurin],arr[i] #Rekursiivisesti kasattu alipuu heapify(arr, n, suurin) #Toiminto poistaa juuren Keon def deleteRoot(arr): globaali n # Hae viimeinen elementti lastElement = arr[n - 1] # Korvaa juuri viimeisellä elementillä arr[0] = lastElement # Pienennä keon kokoa 1:llä n = n - 1 # pinota juurisolmu heapify(arr, n, 0) # Aputoiminto n-koon taulukon tulostamiseen def printArray(arr, n): for i in range(n): print(arr[i],end=' ') print() # Ohjainkoodi jos __name__ == '__main__': # Max-Heapin taulukkoesitys # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot( arr) printArray(arr, n) # Tämän koodin on antanut Rajat Kumar.>>>5 4 3 2> Aika monimutkaisuus : O(log n) missä n on keon elementtien lukumäärä
Aputila: Päällä)3.Peek-toiminto Max-keap-tietorakenteessa:
Päästäksesi maksimielementtiin (eli kasan juureen), palautetaan juurisolmun arvo. Kurkistamisen aikamonimutkaisuus maksimikeossa on O(1).
Max-Heapin huippuelementti
Peek-operaation käyttöönotto Max-Heapissa:
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
"primin algoritmi"
// 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);>>>Python 3
import>heapq># Create a max heap with some elements using a list>max_heap>=>[>1>,>2>,>3>,>4>,>5>,>6>,>7>,>8>,>9>]>heapq.heapify(max_heap)># Get the peak element (i.e., the largest element)>peak_element>=>heapq.nlargest(>1>, max_heap)[>0>]># Print the peak element>print>(>'Peak element:'>, peak_element)>>>LähtöPeak element: 9>Aika monimutkaisuus :
- Maksimikasossa, joka on toteutettu käyttämällä anjoukkotai lista, huippuelementtiä voidaan käyttää vakioajassa, O(1), koska se sijaitsee aina kasan juuressa.
- Maksimikasossa, joka on toteutettu käyttämällä abinäärinen puu, huippuelementtiin pääsee käsiksi myös O(1)-ajassa, koska se sijaitsee aina puun juuressa.
Aputila: Päällä)
4.Max-keap-tietorakenteessa kasanmuodostustoiminto:
Kasko-operaatiolla voidaan luoda maksimikeko lajittelemattomasta taulukosta. Tämä tehdään aloittamalla viimeisestä ei-lehtisolmusta ja suorittamalla toistuvasti kupla alas -toiminto, kunnes kaikki solmut täyttävät kasan ominaisuuden. Max-keon keon aikamonimutkaisuus on O(n).
Heapify-toiminnot Max-Heapissa
5.Hakutoiminto Max-keap-tietorakenteessa:
Jos haluat etsiä elementtiä maksimikeosta, lineaarinen haku voidaan suorittaa kasaa edustavan taulukon yli. Lineaarisen haun aikamonimutkaisuus on kuitenkin O(n), mikä ei ole tehokasta. Siksi haku ei ole yleisesti käytetty operaatio maksimikeossa.
Tässä on esimerkkikoodi, joka näyttää, kuinka voit etsiä elementtiä maksimikeosta käyttämällä 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
merkkijonon arvo
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>>lämpötila =>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>viimeinen) {>>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.'>);>}>>>Python 3
import>heapq>max_heap>=>[>10>,>8>,>7>,>6>,>5>,>3>,>2>,>1>]># example max heap>heapq._heapify_max(max_heap)>element>=>6># element to search for>found>=>False># Copy the max heap to a temporary list and search for the element>temp>=>list>(max_heap)>while>temp:>>if>heapq._heappop_max(temp)>=>=>element:>>found>=>True>>break>if>found:>>print>(>'Element found in the max heap.'>)>else>:>>print>(>'Element not found in the max heap.'>)>>>LähtöElement found in the max heap.>Aika monimutkaisuus : O(n), missä n on kasan koko.
Aputila : Päällä),Max-Heap-tietorakenteen sovellukset:
- Keon lajittelualgoritmi: Keon datarakenne on perusta kekolajittelualgoritmille, joka on tehokas lajittelualgoritmi, jonka pahimman tapauksen aikakompleksisuus on O(n log n). Kekolajittelualgoritmia käytetään erilaisissa sovelluksissa, mukaan lukien tietokannan indeksointi ja numeerinen analyysi.
- Muistin hallinta: Kasatietorakennetta käytetään muistinhallintajärjestelmissä muistin varaamiseen ja purkamiseen dynaamisesti. Keon avulla tallennetaan muistilohkot ja kasatietorakenteen avulla muistilohkoja hallitaan tehokkaasti ja allokoidaan ohjelmille tarpeen mukaan.
- Graafialgoritmit: Keon tietorakennetta käytetään erilaisissa graafialgoritmeissa, mukaan lukien Dijkstran algoritmi, Primin algoritmi ja Kruskalin algoritmi. Nämä algoritmit vaativat tehokkaan prioriteettijono-toteutuksen, joka voidaan saavuttaa kasatietorakenteen avulla.
- Työaikataulu: Keon tietorakennetta käytetään työn ajoitusalgoritmeissa, joissa tehtävät ajoitetaan niiden prioriteetin tai määräajan perusteella. Keon tietorakenne mahdollistaa tehokkaan pääsyn tärkeimpiin tehtäviin, mikä tekee siitä hyödyllisen tietorakenteen työn ajoitussovelluksille.
Max-Heap-tietorakenteen edut:
- Säilytä maksimiarvo tehokkaasti: Max kaso mahdollistaa jatkuvan pääsyn kasan maksimielementtiin, mikä tekee siitä hyödyllisen sovelluksissa, joissa maksimielementti on löydettävä nopeasti.
- Tehokkaat lisäys- ja poistotoiminnot: Max-keon lisäys- ja poistotoimintojen aikamonimutkaisuus on O(log n), mikä tekee niistä tehokkaita suurille elementtikokoelmille.
- Prioriteettijonot: Max-kekoa voidaan käyttää prioriteettijonon toteuttamiseen, mikä on hyödyllistä monissa sovelluksissa, kuten työn ajoituksessa, tehtävien priorisoinnissa ja tapahtumapohjaisessa simulaatiossa.
- Lajittelu: Max-kekolla voidaan toteuttaa kasalajittelu, joka on tehokas lajittelualgoritmi, jonka pahimman tapauksen aikamonimutkaisuus on O(n log n).
- Tilatehokkuus: Max-keko voidaan toteuttaa taulukkona, joka vaatii vähemmän muistia verrattuna muihin tietorakenteisiin, kuten binäärihakupuuhun tai linkitettyyn listaan.
Suurin keon tietorakenne on hyödyllinen ja tehokas työkalu elementtikokoelmien ylläpitoon ja käsittelyyn, varsinkin kun maksimielementtiin on päästävä nopeasti tai kun elementtejä on lajiteltava tai priorisoitava.
