A Max-Heap je opredeljena kot vrsta Podatkovna struktura kopice je vrsta binarnega drevesa, ki se običajno uporablja v računalništvu za različne namene, vključno z razvrščanjem, iskanjem in organiziranjem podatkov.

Uvod v strukturo podatkov Max-Heap

Namen in primeri uporabe Max-Heap:

• Prednostna čakalna vrsta: Ena od primarnih uporab podatkovne strukture kopice je za izvajanje prednostnih čakalnih vrst.
• Razvrstitev kopice: Podatkovna struktura kopice se uporablja tudi v algoritmih za razvrščanje.
• Upravljanje pomnilnika: Podatkovna struktura kopice se uporablja tudi pri upravljanju pomnilnika. Ko mora program dinamično dodeliti pomnilnik, uporablja podatkovno strukturo kopice, da sledi razpoložljivemu pomnilniku.
• Dijkstrajev algoritem najkrajše poti uporablja podatkovno strukturo kopice, da sledi točkam z najkrajšo potjo od izvorne točke.

Struktura podatkov Max-Heap v različnih jezikih:

1. Max-Heap v C++

Največji kup je mogoče implementirati z uporabo prednostna_čakalna vrsta posoda iz Standardna knjižnica predlog (STL) . The prednostna_čakalna vrsta kontejner je vrsta vsebniškega adapterja, ki omogoča shranjevanje elementov v čakalni vrsti podobni podatkovni strukturi, v kateri ima vsak element prednost, povezano z njim.

  Synt  ax: priority_queuemaxH;>

2. Max-Heap v Javi

V Javi je največjo kopico mogoče implementirati z uporabo PriorityQueue razred od paket java.util . Razred PriorityQueue je prednostna čakalna vrsta, ki zagotavlja način za shranjevanje elementov v čakalni vrsti podobni podatkovni strukturi, v kateri ima vsak element z njim povezano prioriteto.

  Syntax  : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());>

3. Max-Heap v Pythonu

V Pythonu je mogoče maksimalno kopico implementirati z uporabo heapq modul, ki nudi funkcije za izvajanje kopic. Natančneje, modul heapq ponuja način za ustvarjanje in upravljanje podatkovnih struktur kopice.

  Synt  ax: heap = []  heapify(heap)>

4. Max-Heap v C#

V C# je največjo kopico mogoče implementirati z uporabo razreda PriorityQueue iz System.Collections.Generic imenski prostor . Razred PriorityQueue je prednostna čakalna vrsta, ki zagotavlja način za shranjevanje elementov v čakalni vrsti podobni podatkovni strukturi, v kateri ima vsak element z njim povezano prioriteto.

  Syntax:   var maxHeap = new PriorityQueue((a, b) =>b - a);>

5. Max-Heap v JavaScriptu

Največja kopica je binarno drevo, kjer ima vsako vozlišče vrednost, ki je večja ali enaka svojim otrokom. V JavaScriptu lahko implementirate največji kup z uporabo matrike, kjer prvi element predstavlja korensko vozlišče, otroci vozlišča pa indeks jaz se nahajajo na indeksih 2i+1 in 2i+2.

Syntax: const miaxHeap = new MaxHeap();>

Razlika med Max in Min Heap

	Najmanjša kopica	Max Heap
1.	V Min-Heap mora biti ključ, ki je prisoten v korenskem vozlišču, manjši ali enak med ključi, ki so prisotni pri vseh njegovih podrejenih elementih.	V Max-Heap mora biti ključ, ki je prisoten v korenskem vozlišču, večji ali enak med ključi, ki so prisotni pri vseh njegovih podrejenih.
2.	V Min-Heap minimalni ključni element, ki je prisoten v korenu.	V Max-Heap največji ključni element, ki je prisoten v korenu.
3.	Min-Heap uporablja naraščajočo prioriteto.	Max-Heap uporablja padajočo prioriteto.
4.	Pri konstrukciji Min-Heap ima prednost najmanjši element.	Pri konstrukciji Max-Heap ima prednost največji element.
5.	V Min-Heap-u je najmanjši element prvi, ki se odstrani iz kupa.	V največji kopici je največji element prvi, ki se odstrani iz kopice.

Notranja izvedba podatkovne strukture Max-Heap:

A Najmanjša kopica je običajno predstavljena kot niz .

• Korenski element bo pri Prihod[0] .
• Za katero koli ith vozlišče Arr[i].
  • levi otrok je shranjen pri indeksu 2i+1
  • Desni otrok je shranjen pri indeksu 2i+2
  • Nadrejeni je shranjen na dnu indeksa ((i-1)/2)

Notranja implementacija Max-Heap zahteva 3 glavne korake:

1. Vstavljanje : Če želite v kopico vstaviti nov element, se ta doda na konec matrike in se nato dvigne v mehurček, dokler ne zadosti lastnosti kopice.
2. Izbris : Če želite izbrisati največji element (koren kopice), se zadnji element v matriki zamenja s korenom, novi koren pa se prikaže navzdol, dokler ne zadosti lastnosti kopice.
3. Heapify : Operacijo heapify je mogoče uporabiti za ustvarjanje največjega kupa iz nerazvrščene matrike.

Operacije na strukturi podatkov Max-heap in njihova implementacija:

Tukaj je nekaj običajnih operacij, ki jih je mogoče izvesti na podatkovni strukturi Heap Data Structure,

1. Vstavljanje v strukturo podatkov Max-Heap :

Elemente je mogoče vstaviti v kopico po podobnem pristopu, kot je opisano zgoraj za brisanje. Ideja je:

• Najprej povečajte velikost kopice za 1, da lahko shrani nov element.
• Vstavite nov element na konec kopice.
• Ta na novo vstavljen element lahko popači lastnosti Heap za njegove starše. Torej, da bi ohranili lastnosti kopice, heapificirajte ta na novo vstavljeni element po pristopu od spodaj navzgor.

Ilustracija:

Recimo, da je kopica največja kopica kot:

Vstavljanje v največji kup

Izvedba operacije vstavljanja v Max-Heap:

C++

znak v int v Javi

// C++ program to insert new element to Heap> #include> using> namespace> std;> #define MAX 1000 // Max size of Heap> // Function to heapify ith node in a Heap> // of size n following a Bottom-up approach> void> heapify(>int> arr[],>int> n,>int> i)> {> >// Find parent> >int> parent = (i - 1) / 2;> >if> (arr[parent]>0) {> >// For Max-Heap> >// If current node is greater than its parent> >// Swap both of them and call heapify again> >// for the parent> >if> (arr[i]>arr[parent]) {> >swap(arr[i], arr[parent]);> >// Recursively heapify the parent node> >heapify(arr, n, parent);> >}> >}> }> // Function to insert a new node to the Heap> void> insertNode(>int> arr[],>int>& n,>int> Key)> {> >// Increase the size of Heap by 1> >n = n + 1;> >// Insert the element at end of Heap> >arr[n - 1] = Key;> >// Heapify the new node following a> >// Bottom-up approach> >heapify(arr, n, n - 1);> }> // A utility function to print array of size n> void> printArray(>int> arr[],>int> n)> {> >for> (>int> i = 0; i cout << arr[i] << ' '; cout << ' '; } // Driver Code int main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[MAX] = { 10, 5, 3, 2, 4 }; int n = 5; int key = 15; insertNode(arr, n, key); printArray(arr, n); // Final Heap will be: // 15 // / // 5 10 // / / // 2 4 3 return 0; }>

>

>

Java

// Java program for implementing insertion in Heaps> public> class> insertionHeap {> >// Function to heapify ith node in a Heap> >// of size n following a Bottom-up approach> >static> void> heapify(>int>[] arr,>int> n,>int> i)> >{> >// Find parent> >int> parent = (i ->1>) />2>;> > >if> (arr[parent]>>0>) {> >// For Max-Heap> >// If current node is greater than its parent> >// Swap both of them and call heapify again> >// for the parent> >if> (arr[i]>arr[parent]) {> > >// swap arr[i] and arr[parent]> >int> temp = arr[i];> >arr[i] = arr[parent];> >arr[parent] = temp;> > >// Recursively heapify the parent node> >heapify(arr, n, parent);> >}> >}> >}> >// Function to insert a new node to the heap.> >static> int> insertNode(>int>[] arr,>int> n,>int> Key)> >{> >// Increase the size of Heap by 1> >n = n +>1>;> > >// Insert the element at end of Heap> >arr[n ->1>] = Key;> > >// Heapify the new node following a> >// Bottom-up approach> >heapify(arr, n, n ->1>);> > >// return new size of Heap> >return> n;> >}> >/* A utility function to print array of size n */> >static> void> printArray(>int>[] arr,>int> n)> >{> >for> (>int> i =>0>; i System.out.println(arr[i] + ' '); System.out.println(); } // Driver Code public static void main(String args[]) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 // maximum size of the array int MAX = 1000; int[] arr = new int[MAX]; // initializing some values arr[0] = 10; arr[1] = 5; arr[2] = 3; arr[3] = 2; arr[4] = 4; // Current size of the array int n = 5; // the element to be inserted int Key = 15; // The function inserts the new element to the heap and // returns the new size of the array n = insertNode(arr, n, Key); printArray(arr, n); // Final Heap will be: // 15 // / // 5 10 // / / // 2 4 3 } } // The code is contributed by Gautam goel>

>

>

C#

// C# program for implementing insertion in Heaps> using> System;> public> class> insertionHeap {> >// Function to heapify ith node in a Heap of size n following a Bottom-up approach> >static> void> heapify(>int>[] arr,>int> n,>int> i) {> >// Find parent> >int> parent = (i - 1) / 2;> >if> (arr[parent]>0) {> >// For Max-Heap> >// If current node is greater than its parent> >// Swap both of them and call heapify again> >// for the parent> >if> (arr[i]>arr[nadrejeni]) {> >// swap arr[i] and arr[parent]> >int> temp = arr[i];> >arr[i] = arr[parent];> >arr[parent] = temp;> >// Recursively heapify the parent node> >heapify(arr, n, parent);> >}> >}> >}> >// Function to insert a new node to the heap.> >static> int> insertNode(>int>[] arr,>int> n,>int> Key) {> >// Increase the size of Heap by 1> >n = n + 1;> >// Insert the element at end of Heap> >arr[n - 1] = Key;> >// Heapify the new node following a> >// Bottom-up approach> >heapify(arr, n, n - 1);> >// return new size of Heap> >return> n;> >}> >/* A utility function to print array of size n */> >static> void> printArray(>int>[] arr,>int> n) {> >for> (>int> i = 0; i Console.WriteLine(arr[i] + ' '); Console.WriteLine(''); } public static void Main(string[] args) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 // maximum size of the array int MAX = 1000; int[] arr = new int[MAX]; // initializing some values arr[0] = 10; arr[1] = 5; arr[2] = 3; arr[3] = 2; arr[4] = 4; // Current size of the array int n = 5; // the element to be inserted int Key = 15; // The function inserts the new element to the heap and // returns the new size of the array n = insertNode(arr, n, Key); printArray(arr, n); // Final Heap will be: // 15 // / // 5 10 // / / // 2 4 3 } } // This code is contributed by ajaymakvana.>

>

>

Javascript

// Javascript program for implement insertion in Heaps> // To heapify a subtree rooted with node i which is> // an index in arr[].Nn is size of heap> let MAX = 1000;> // Function to heapify ith node in a Heap of size n following a Bottom-up approach> function> heapify(arr, n, i)> {> >// Find parent> >let parent = Math.floor((i-1)/2);> >if> (arr[parent]>= 0) {> >// For Max-Heap> >// If current node is greater than its parent> >// Swap both of them and call heapify again> >// for the parent> >if> (arr[i]>arr[parent]) {> >let temp = arr[i];> >arr[i] = arr[parent];> >arr[parent] = temp;> >// Recursively heapify the parent node> >heapify(arr, n, parent);> >}> >}> }> // Function to insert a new node to the Heap> function> insertNode(arr, n, Key)> {> >// Increase the size of Heap by 1> >n = n + 1;> >// Insert the element at end of Heap> >arr[n - 1] = Key;> >// Heapify the new node following a> >// Bottom-up approach> >heapify(arr, n, n - 1);> > >return> n;> }> /* A utility function to print array of size N */> function> printArray(arr, n)> {> >for> (let i = 0; i console.log(arr[i] + ' '); console.log(''); } let arr = [ 10, 5, 3, 2, 4 ]; let n = arr.length; let key = 15; n = insertNode(arr, n, key); printArray(arr, n); // This code is contributed by ajaymakvana>

>

>

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[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....> '''>

>

>

Izhod

15 5 10 2 4 3>

Časovna kompleksnost: O(log(n)) ( kjer je n št elementov v kupu )
Pomožni prostor: O(n)

2. Izbris v strukturi podatkov Max-Heap :

Brisanje elementa na kateri koli vmesni poziciji v kopici je lahko drago, zato lahko preprosto zamenjamo element, ki ga želimo izbrisati, z zadnjim elementom in izbrišemo zadnji element kopice.

• Zamenjajte koren ali element, ki ga želite izbrisati, z zadnjim elementom.
• Izbrišite zadnji element iz kopice.
• Ker je zadnji element zdaj postavljen na položaj korenskega vozlišča. Torej morda ne sledi lastnosti kopice. Zato kopičite zadnje vozlišče na mestu korena.

Ilustracija :

Recimo, da je kopica največja kopica kot:

Največja podatkovna struktura kopice

Element, ki ga želite izbrisati, je root, tj. 10.

Proces :

Zadnji element je 4.

Korak 1: Zadnji element zamenjajte s root in ga izbrišite.

Max Heap

2. korak : Heapify root.

Končna kopica:

Max Heap

Izvedba operacije brisanja 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>

>

>

Javascript

gimp brisanje ozadja

> >// 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[največji]): največji = l #Če je desni podrejeni večji od največjega do sedaj if (r in arr[r]> arr[največji]): največji = r # Če največji ni koren if (največji != i) : arr[i],arr[largest]=arr[largest],arr[i] #Rekurzivno heapify prizadetega poddrevesa heapify(arr, n, largest) #Funkcija za brisanje korena iz Heap def deleteRoot(arr): global n # Pridobi zadnji element lastElement = arr[n - 1] # Zamenjaj koren z zadnjim elementom arr[0] = lastElement # Zmanjšaj velikost kopice za 1 n = n - 1 # heapify korensko vozlišče heapify(arr, n, 0) # Pomožna funkcija za tiskanje matrike velikosti n def printArray(arr, n): for i in range(n): print(arr[i],end=' ') print() # Koda gonilnika if __name__ == '__main__': # Matrična predstavitev Max-Heap # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot( arr) printArray(arr, n) # To kodo je prispeval Rajat Kumar.>

>

>

Izhod

5 4 3 2>

Časovna zapletenost : O(log n), kjer je n št. elementov v kupu
Pomožni prostor: O(n)

3.Operacija Peek v strukturi podatkov Max-heap:

Za dostop do največjega elementa (tj. korena kopice) se vrne vrednost korenskega vozlišča. Časovna kompleksnost pokukanja v največji kup je O(1).

Najvišji element največjega kupa

Implementacija operacije 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#

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

system.out.println

// 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)>

>

>

Izhod

Peak element: 9>

Časovna zapletenost :

• V največjem kupu, implementiranem z annizali seznam, je do elementa vrha mogoče dostopati v konstantnem času, O(1), saj se vedno nahaja v korenu kopice.
• V največjem kupu, implementiranem z abinarno drevo, je do elementa vrha mogoče dostopati tudi v O(1) času, saj se vedno nahaja v korenu drevesa.

Pomožni prostor: O(n)

4.Operacija Heapify na podatkovni strukturi Max-heap:

Operacijo heapify lahko uporabite za ustvarjanje največje kopice iz nerazvrščene matrike. To naredite tako, da začnete pri zadnjem nelistnem vozlišču in večkrat izvedete operacijo mehurčka navzdol, dokler vsa vozlišča ne izpolnjujejo lastnosti kopice. Časovna kompleksnost heapifyja v največjem kupu je O(n).

Operacije Heapify v Max-Heap

5.Operacija iskanja v strukturi podatkov Max-heap:

Če želite poiskati element v največji kopici, lahko izvedete linearno iskanje po matriki, ki predstavlja kopico. Vendar pa je časovna kompleksnost linearnega iskanja O(n), kar ni učinkovito. Zato iskanje ni pogosto uporabljena operacija v največjem kupu.

Tukaj je primer kode, ki prikazuje, kako z uporabo iskati element v največjem kupu std::najdi() :

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

java branje datoteke csv

import> java.util.PriorityQueue;> public> class> GFG {> >public> static> void> main(String[] args) {> >PriorityQueue maxHeap =>new> PriorityQueue((a, b) ->b - a);> >maxHeap.add(>3>);>// insert elements into the priority queue> >maxHeap.offer(>1>);> >maxHeap.offer(>4>);> >maxHeap.offer(>1>);> >maxHeap.offer(>6>);> >int> element =>6>;>// element to search for> >boolean> found =>false>;> >// Copy the max heap to a temporary queue and search for the element> >PriorityQueue temp =>new> PriorityQueue(maxHeap);> >while> (!temp.isEmpty()) {> >if> (temp.poll() == element) {> >found =>true>;> >break>;> >}> >}> >if> (found) {> >System.out.println(>'Element found in the max heap.'>);> >}>else> {> >System.out.println(>'Element not found in the max heap.'>);> >}> >}> }>

>

>

C#

using> System;> using> System.Collections.Generic;> class> Program {> >static> void> Main(>string>[] args) {> >// Create a max heap with some elements using a PriorityQueue> >PriorityQueue<>int>>maxHeap =>new> PriorityQueue<>int>>();> >maxHeap.Enqueue(10);> >maxHeap.Enqueue(9);> >maxHeap.Enqueue(8);> >maxHeap.Enqueue(6);> >maxHeap.Enqueue(4);> >int> element = 6;>// element to search for> >bool> found =>false>;> >// Copy the max heap to a temporary queue and search for the element> >PriorityQueue<>int>>temp =>new> PriorityQueue<>int>>(maxHeap);> >while> (temp.Count>0) {> >if> (temp.Peek() == element) {> >found =>true>;> >break>;> >}> >temp.Dequeue();> >}> >if> (found) {> >Console.WriteLine(>'Element found in the max heap.'>);> >}>else> {> >Console.WriteLine(>'Element not found in the max heap.'>);> >}> >}> }> // PriorityQueue class> class> PriorityQueue>where> T : IComparable {> >private> List heap =>new> List();> >public> void> Enqueue(T item) {> >heap.Add(item);> >int> child = heap.Count - 1;> >while> (child>0) {> >int> parent = (child - 1) / 2;> >if> (heap[child].CompareTo(heap[parent])>0) {> >T tmp = heap[child];> >heap[child] = heap[parent];> >heap[parent] = tmp;> >child = parent;> >}>else> {> >break>;> >}> >}> >}> >public> T Dequeue() {> >int> last = heap.Count - 1;> >T frontItem = heap[0];> >heap[0] = heap[last];> >heap.RemoveAt(last);> >last--;> >int> parent = 0;> >while> (>true>) {> >int> leftChild = parent * 2 + 1;> >if> (leftChild>zadnji) {> >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.'>)>

>

>

Izhod

Element found in the max heap.>

Časovna zapletenost : O(n), kjer je n velikost kupa.
Pomožni prostor : O(n),

Uporaba podatkovne strukture Max-Heap:

• Heapsort algoritem: Podatkovna struktura kopice je osnova za algoritem heapsort, ki je učinkovit algoritem za razvrščanje s časovno kompleksnostjo v najslabšem primeru O(n log n). Algoritem heapsort se uporablja v različnih aplikacijah, vključno z indeksiranjem baze podatkov in numerično analizo.
• Upravljanje pomnilnika: Podatkovna struktura kopice se uporablja v sistemih za upravljanje pomnilnika za dinamično dodeljevanje in sprostitev pomnilnika. Kopica se uporablja za shranjevanje pomnilniških blokov, podatkovna struktura kopice pa se uporablja za učinkovito upravljanje pomnilniških blokov in njihovo dodeljevanje programom po potrebi.
• Algoritmi grafov: Podatkovna struktura kopice se uporablja v različnih algoritmih grafov, vključno z Dijkstrovim algoritmom, Primovim algoritmom in Kruskalovim algoritmom. Ti algoritmi zahtevajo učinkovito implementacijo prednostne čakalne vrste, kar je mogoče doseči z uporabo podatkovne strukture kopice.
• Razporeditev dela: Podatkovna struktura kopice se uporablja v algoritmih za razporejanje opravil, kjer so opravila razporejena glede na njihovo prioriteto ali rok. Podatkovna struktura kopice omogoča učinkovit dostop do naloge z najvišjo prioriteto, zaradi česar je uporabna podatkovna struktura za aplikacije za razporejanje opravil.

Prednosti podatkovne strukture Max-Heap:

• Učinkovito vzdržujte največjo vrednost: Največja kopica omogoča stalni dostop do največjega elementa v kopici, zaradi česar je uporabna v aplikacijah, kjer je treba hitro najti največji element.
• Učinkovite operacije vstavljanja in brisanja: Operacije vstavljanja in brisanja v največjem kupu imajo časovno kompleksnost O(log n), zaradi česar so učinkovite za velike zbirke elementov.
• Prednostne čakalne vrste: Največji kup se lahko uporabi za implementacijo prednostne čakalne vrste, ki je uporabna v številnih aplikacijah, kot so razporejanje opravil, prednostna naloga opravil in simulacija na podlagi dogodkov.
• Razvrščanje: Največji kup se lahko uporabi za implementacijo heapsort-a, ki je učinkovit algoritem za razvrščanje, ki ima v najslabšem primeru časovno kompleksnost O(n log n).
• Prostorska učinkovitost: Največjo kopico je mogoče implementirati kot matriko, ki zahteva manj pomnilnika v primerjavi z drugimi podatkovnimi strukturami, kot je binarno iskalno drevo ali povezan seznam.

Podatkovna struktura največje kopice je uporabno in učinkovito orodje za vzdrževanje in upravljanje zbirk elementov, zlasti kadar je treba hitro dostopati do največjega elementa ali ko je treba elemente razvrstiti ali jim dati prednost.