EN Max-Heap er defineret som en type Heap-datastrukturen er en type binært træ, der almindeligvis bruges i datalogi til forskellige formål, herunder sortering, søgning og organisering af data.
Introduktion til Max-Heap Data Structure
Formål og anvendelsestilfælde af Max-Heap:
- Prioritetskø: En af de primære anvendelser af heap-datastrukturen er til implementering af prioritetskøer.
- Dyngesortering: Dyngedatastrukturen bruges også til sorteringsalgoritmer.
- Hukommelseshåndtering: Heap-datastrukturen bruges også til hukommelseshåndtering. Når et program skal allokere hukommelse dynamisk, bruger det heap-datastrukturen til at holde styr på den tilgængelige hukommelse.
- Dijkstras korteste vejs algoritme bruger en heap-datastruktur til at holde styr på toppunkterne med den korteste vej fra kildens toppunkt.
Max-Heap-datastruktur på forskellige sprog:
1. Max-Heap i C++
En max heap kan implementeres ved hjælp af priority_queue beholder fra Standard skabelonbibliotek (STL) . Det priority_queue container er en type containeradapter, der giver en måde at gemme elementer i en kølignende datastruktur, hvor hvert element har en prioritet knyttet til sig.
Synt ax: priority_queuemaxH;>2. Max-Heap i Java
I Java kan en max heap implementeres ved hjælp af Prioritetskø klasse fra java.util-pakken . PriorityQueue-klassen er en prioritetskø, der giver en måde at gemme elementer i en kølignende datastruktur, hvor hvert element har en prioritet tilknyttet.
Syntax : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());>3. Max-Heap i Python
I Python kan en max heap implementeres ved hjælp af heapq modul, som giver funktioner til implementering af heaps. Specifikt giver heapq-modulet en måde at skabe og manipulere heap-datastrukturer på.
Synt ax: heap = [] heapify(heap)>4. Max-Heap i C#
I C# kan en max heap implementeres ved hjælp af PriorityQueue-klassen fra System.Collections.Generisk navneområde . PriorityQueue-klassen er en prioritetskø, der giver en måde at gemme elementer i en kølignende datastruktur, hvor hvert element har en prioritet tilknyttet.
Syntax: var maxHeap = new PriorityQueue((a, b) =>b - a);>5. Max-Heap i JavaScript
En max heap er et binært træ, hvor hver node har en værdi større end eller lig med dens børn. I JavaScript kan du implementere en max heap ved hjælp af et array, hvor det første element repræsenterer rodnoden og børnene af en knude ved indeks jeg er placeret ved indekser 2i+1 og 2i+2.
Syntax: const miaxHeap = new MaxHeap();>Forskellen mellem Max og Min Heap
Min bunke Max Heap 1. I en Min-Heap skal nøglen, der er til stede ved rodnoden, være mindre end eller lig med blandt nøglerne, der er til stede ved alle dens børn. I en Max-Heap skal nøglen, der er til stede ved rodnoden, være større end eller lig med blandt nøglerne, der er til stede ved alle dens børn. 2. I en Min-Heap er minimumsnøgleelementet til stede ved roden. I en Max-Heap er det maksimale nøgleelement til stede ved roden. 3. En Min-Heap bruger den stigende prioritet. En Max-Heap bruger den faldende prioritet. 4. I konstruktionen af en Min-Heap har det mindste element prioritet. Ved konstruktionen af en Max-Heap har det største element prioritet. 5. I en Min-Heap er det mindste element det første, der bliver poppet fra dyngen. I en Max-Heap er det største element det første, der bliver poppet fra dyngen. Intern implementering af Max-Heap-datastruktur:
EN Min heap er typisk repræsenteret som en matrix .
- Rodelementet vil være kl Arr[0] .
- For enhver it-node Arr[i].
- venstre barn gemmes ved indeks 2i+1
- Højre barn gemmes ved indeks 2i+2
- Forælder er gemt på indeksgulvet ((i-1)/2)
Den interne implementering af Max-Heap kræver 3 store trin:
- Indskud : For at indsætte et nyt element i heapen tilføjes det til slutningen af arrayet og bobles derefter op, indtil det opfylder heapegenskaben.
- Sletning : For at slette det maksimale element (roden af heapen), byttes det sidste element i arrayet med roden, og den nye rod bobles ned, indtil den opfylder heap-egenskaben.
- Heapify : En heapify-operation kan bruges til at oprette en maks. heap fra et usorteret array.
Operationer på Max-heap datastruktur og deres implementering:
Her er nogle almindelige handlinger, der kan udføres på en Heap Data Structure-datastruktur,
1. Indsættelse i Max-Heap Data Structure :
Elementer kan indsættes i heapen efter en lignende fremgangsmåde som diskuteret ovenfor til sletning. Ideen er at:
- Øg først bunken med 1, så den kan opbevare det nye element.
- Indsæt det nye element i slutningen af heapen.
- Dette nyligt indsatte element kan forvrænge Heaps egenskaber for dets forældre. Så for at bevare egenskaberne for Heap, skal du ophobe dette nyligt indsatte element efter en bottom-up-tilgang.
Illustration:
Antag, at Heapen er en Max-Heap som:
Indsættelse i Max heap
Implementering af indsættelsesoperation i Max-Heap:
C++
modstridende søgning
// 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[forælder]) {>>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[forælder]) {>>>// 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[forælder]) {>>// 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[forælder]) {>>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[forælder]:>>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....>'''>>>Produktion15 5 10 2 4 3>Tidskompleksitet: O(log(n)) ( hvor n er antallet af elementer i bunken )
Hjælpeplads: På)2. Sletning i Max-Heap Data Structure :
Det kan være dyrt at slette et element på en hvilken som helst mellemposition i heapen, så vi kan blot erstatte det element, der skal slettes, med det sidste element og slette det sidste element i heapen.
- Erstat roden eller elementet, der skal slettes, med det sidste element.
- Slet det sidste element fra heapen.
- Da det sidste element nu er placeret ved positionen af rodknuden. Så den følger muligvis ikke bunkeejendommen. Derfor skal du ophobe den sidste node placeret ved rodens position.
Illustration :
Antag, at Heapen er en Max-Heap som:
Max Heap-datastruktur
Elementet, der skal slettes, er root, dvs. 10.
Behandle :
Det sidste element er 4.
Trin 1: Erstat det sidste element med root, og slet det.
Max Heap
Trin 2 : Ophob rod.
Sidste bunke:
Max Heap
Implementering af sletningsoperation i 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#
css fed tekst
// 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[størst]): størst = l #Hvis højre barn er større end største hidtil if (r og arr[r]> arr[størst]): størst = r # Hvis størst ikke er root if (størst != i) : arr[i],arr[størst]=arr[størst],arr[i] #Rekursivt heapify det berørte undertræ heapify(arr, n, størst) #Funktion til at slette roden fra Heap def deleteRoot(arr): globalt n # Hent det sidste element lastElement = arr[n - 1] # Erstat rod med sidste element arr[0] = lastElement # Reducer størrelsen af heap med 1 n = n - 1 # heapify rodknuden heapify(arr, n, 0) # En hjælpefunktion til at udskrive array af størrelse n def printArray(arr, n): for i i område(n): print(arr[i],end=' ') print() # Driverkode hvis __navn__ == '__main__': # Array-repræsentation af Max-Heap # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot( arr) printArray(arr, n) # Denne kode er bidraget af Rajat Kumar.>>>Produktion5 4 3 2>Tidskompleksitet : O(log n) hvor n er antallet af elementer i heapen
Hjælpeplads: På)3.Kig operation på Max-heap datastruktur:
For at få adgang til det maksimale element (dvs. roden af heapen), returneres værdien af rodnoden. Tidskompleksiteten af kig i en max bunke er O(1).
Peak Element Of Max- Heap
Implementering af Peek-operation i 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);>>}>}>forekomst af i java>>C#
using>System;>using>System.Collections.Generic;>public>class>GFG {>>public>static>void>Main() {>>// Create a min heap with some elements using a PriorityQueue>>var>maxHeap =>new>PriorityQueue<>int>>();>>maxHeap.Enqueue(9);>>maxHeap.Enqueue(8);>>maxHeap.Enqueue(7);>>maxHeap.Enqueue(6);>>maxHeap.Enqueue(5);>>maxHeap.Enqueue(4);>>maxHeap.Enqueue(3);>>maxHeap.Enqueue(2);>>maxHeap.Enqueue(1);>>// Get the peak element (i.e., the smallest element)>>int>peakElement = maxHeap.Peek();>>// Print the peak element>>Console.WriteLine(>'Peak element: '>+ peakElement);>>}>}>// Define a PriorityQueue class that uses a max heap>class>PriorityQueue>where>T : IComparable {>>private>List heap;>>public>PriorityQueue() {>>this>.heap =>new>List();>>}>>public>int>Count {>>get>{>return>this>.heap.Count; }>>}>>public>void>Enqueue(T item) {>>this>.heap.Add(item);>>this>.BubbleUp(>this>.heap.Count - 1);>>}>>public>T Dequeue() {>>T item =>this>.heap[0];>>int>lastIndex =>this>.heap.Count - 1;>>this>.heap[0] =>this>.heap[lastIndex];>>this>.heap.RemoveAt(lastIndex);>>this>.BubbleDown(0);>>return>item;>>}>>public>T Peek() {>>return>this>.heap[0];>>}>>private>void>BubbleUp(>int>index) {>>while>(index>0) {>>int>parentIndex = (index - 1) / 2;>>if>(>this>.heap[parentIndex].CompareTo(>this>.heap[index])>= 0) {>>break>;>>}>>Swap(parentIndex, index);>>index = parentIndex;>>}>>}>>private>void>BubbleDown(>int>index) {>>while>(index <>this>.heap.Count) {>>int>leftChildIndex = index * 2 + 1;>>int>rightChildIndex = index * 2 + 2;>>int>largestChildIndex = index;>>if>(leftChildIndex <>this>.heap.Count &&>this>.heap[leftChildIndex].CompareTo(>this>.heap[largestChildIndex])>0) {>>largestChildIndex = leftChildIndex;>>}>>if>(rightChildIndex <>this>.heap.Count &&>this>.heap[rightChildIndex].CompareTo(>this>.heap[largestChildIndex])>0) {>>largestChildIndex = rightChildIndex;>>}>>if>(largestChildIndex == index) {>>break>;>>}>>Swap(largestChildIndex, index);>>index = largestChildIndex;>>}>>}>>private>void>Swap(>int>i,>int>j) {>>T temp =>this>.heap[i];>>this>.heap[i] =>this>.heap[j];>>this>.heap[j] = temp;>>}>}>>>Javascript
// Define a MaxHeap class that uses an array>class MaxHeap {>>constructor() {>>this>.heap = [];>>}>>push(item) {>>this>.heap.push(item);>>this>.bubbleUp(>this>.heap.length - 1);>>}>>pop() {>>let item =>this>.heap[0];>>let lastIndex =>this>.heap.length - 1;>>this>.heap[0] =>this>.heap[lastIndex];>>this>.heap.pop();>>this>.bubbleDown(0);>>return>item;>>}>>peak() {>>return>this>.heap[0];>>}>>bubbleUp(index) {>>while>(index>0) {>>let parentIndex = Math.floor((index - 1) / 2);>>if>(>this>.heap[parentIndex]>=>this>.heap[index]) {>>break>;>>}>>this>.swap(parentIndex, index);>>index = parentIndex;>>}>>}>>bubbleDown(index) {>>while>(index <>this>.heap.length) {>>let leftChildIndex = index * 2 + 1;>>let rightChildIndex = index * 2 + 2;>>let largestChildIndex = index;>>if>(leftChildIndex <>this>.heap.length &&>this>.heap[leftChildIndex]>>this>.heap[largestChildIndex]) {>>largestChildIndex = leftChildIndex;>>}>>if>(rightChildIndex <>this>.heap.length &&>this>.heap[rightChildIndex]>>this>.heap[largestChildIndex]) {>>largestChildIndex = rightChildIndex;>>}>>if>(largestChildIndex === index) {>>break>;>>}>>this>.swap(largestChildIndex, index);>>index = largestChildIndex;>>}>>}>>swap(i, j) {>>let temp =>this>.heap[i];>>this>.heap[i] =>this>.heap[j];>>this>.heap[j] = temp;>>}>}>// Create a max heap with some elements using an array>let maxHeap =>new>MaxHeap();>maxHeap.push(9);>maxHeap.push(8);>maxHeap.push(7);>maxHeap.push(6);>maxHeap.push(5);>maxHeap.push(4);>maxHeap.push(3);>maxHeap.push(2);>maxHeap.push(1);>// Get the peak element (i.e., the largest element)>let peakElement = maxHeap.peak();>// Print the peak element>console.log(>'Peak element: '>+ peakElement);>>>Python3
import>heapq># Create a max heap with some elements using a list>max_heap>=>[>1>,>2>,>3>,>4>,>5>,>6>,>7>,>8>,>9>]>heapq.heapify(max_heap)># Get the peak element (i.e., the largest element)>peak_element>=>heapq.nlargest(>1>, max_heap)[>0>]># Print the peak element>print>(>'Peak element:'>, peak_element)>>>ProduktionPeak element: 9>Tidskompleksitet :
- I en max bunke implementeret ved hjælp af enarrayeller en liste, kan peak-elementet tilgås i konstant tid, O(1), da det altid er placeret ved roden af heapen.
- I en max bunke implementeret ved hjælp af enbinært træ, kan peak-elementet også tilgås i O(1) tid, da det altid er placeret ved roden af træet.
Hjælpeplads: På)
4.Heapify-operation på Max-heap-datastruktur:
En heapify-operation kan bruges til at skabe en max heap fra et usorteret array. Dette gøres ved at starte ved den sidste ikke-bladsknude og gentagne gange udføre boble ned-operationen, indtil alle noder opfylder heap-egenskaben. Tidskompleksiteten af heapify i en max heap er O(n).
Heapify-operationer i Max-Heap
hvor finder jeg mine browserindstillinger5.Søgeoperation på Max-heap Data Structure:
For at søge efter et element i den maksimale heap, kan der udføres en lineær søgning over det array, der repræsenterer heapen. Imidlertid er tidskompleksiteten af en lineær søgning O(n), hvilket ikke er effektivt. Derfor er søgning ikke en almindeligt brugt operation i en maks. bunke.
Her er en eksempelkode, der viser, hvordan man søger efter et element i en maks. bunke ved hjælp af std::find() :
C++
#include>#include // for std::priority_queue>using>namespace>std;>int>main() {>>std::priority_queue<>int>>max_heap;>>// example max heap>>>max_heap.push(10);>>max_heap.push(9);>>max_heap.push(8);>>max_heap.push(6);>>max_heap.push(4);>>int>element = 6;>// element to search for>>bool>found =>false>;>>// Copy the max heap to a temporary queue and search for the element>>std::priority_queue<>int>>temp = max_heap;>>while>(!temp.empty()) {>>if>(temp.top() == element) {>>found =>true>;>>break>;>>}>>temp.pop();>>}>>if>(found) {>>std::cout <<>'Element found in the max heap.'><< std::endl;>>}>else>{>>std::cout <<>'Element not found in the max heap.'><< std::endl;>>}>>return>0;>}>>>Java
import>java.util.PriorityQueue;>public>class>GFG {>>public>static>void>main(String[] args) {>>PriorityQueue maxHeap =>new>PriorityQueue((a, b) ->b - a);>>maxHeap.add(>3>);>// insert elements into the priority queue>>maxHeap.offer(>1>);>>maxHeap.offer(>4>);>>maxHeap.offer(>1>);>>maxHeap.offer(>6>);>>int>element =>6>;>// element to search for>>boolean>found =>false>;>>// Copy the max heap to a temporary queue and search for the element>>PriorityQueue temp =>new>PriorityQueue(maxHeap);>>while>(!temp.isEmpty()) {>>if>(temp.poll() == element) {>>found =>true>;>>break>;>>}>>}>>if>(found) {>>System.out.println(>'Element found in the max heap.'>);>>}>else>{>>System.out.println(>'Element not found in the max heap.'>);>>}>>}>}>>>C#
using>System;>using>System.Collections.Generic;>class>Program {>>static>void>Main(>string>[] args) {>>// Create a max heap with some elements using a PriorityQueue>>PriorityQueue<>int>>maxHeap =>new>PriorityQueue<>int>>();>>maxHeap.Enqueue(10);>>maxHeap.Enqueue(9);>>maxHeap.Enqueue(8);>>maxHeap.Enqueue(6);>>maxHeap.Enqueue(4);>>int>element = 6;>// element to search for>>bool>found =>false>;>>// Copy the max heap to a temporary queue and search for the element>>PriorityQueue<>int>>temp =>new>PriorityQueue<>int>>(maxHeap);>>while>(temp.Count>0) {>>if>(temp.Peek() == element) {>>found =>true>;>>break>;>>}>>temp.Dequeue();>>}>>if>(found) {>>Console.WriteLine(>'Element found in the max heap.'>);>>}>else>{>>Console.WriteLine(>'Element not found in the max heap.'>);>>}>>}>}>// PriorityQueue class>class>PriorityQueue>where>T : IComparable {>>private>List heap =>new>List();>>public>void>Enqueue(T item) {>>heap.Add(item);>>int>child = heap.Count - 1;>>while>(child>0) {>>int>parent = (child - 1) / 2;>>if>(heap[child].CompareTo(heap[parent])>0) {>>T tmp = heap[child];>>heap[child] = heap[parent];>>heap[parent] = tmp;>>child = parent;>>}>else>{>>break>;>>}>>}>>}>>public>T Dequeue() {>>int>last = heap.Count - 1;>>T frontItem = heap[0];>>heap[0] = heap[last];>>heap.RemoveAt(last);>>last--;>>int>parent = 0;>>while>(>true>) {>>int>leftChild = parent * 2 + 1;>>if>(leftChild>sidste) {>>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.'>)>>>ProduktionElement found in the max heap.>Tidskompleksitet : O(n), hvor n er bunkens størrelse.
Hjælpeplads : På),Anvendelser af Max-Heap Data Structure:
- Heapsort-algoritme: Heap-datastrukturen er grundlaget for heapsort-algoritmen, som er en effektiv sorteringsalgoritme med en worst-case tidskompleksitet på O(n log n). Heapsort-algoritmen bruges i forskellige applikationer, herunder databaseindeksering og numerisk analyse.
- Hukommelseshåndtering: Heap-datastrukturen bruges i hukommelsesstyringssystemer til at allokere og deallokere hukommelse dynamisk. Heapen bruges til at gemme hukommelsesblokkene, og heapdatastrukturen bruges til effektivt at styre hukommelsesblokkene og allokere dem til programmer efter behov.
- Grafalgoritmer: Dyngedatastrukturen bruges i forskellige grafalgoritmer, herunder Dijkstras algoritme, Prims algoritme og Kruskals algoritme. Disse algoritmer kræver effektiv prioritetskøimplementering, hvilket kan opnås ved hjælp af heap-datastrukturen.
- Jobplanlægning: Heap-datastrukturen bruges i jobplanlægningsalgoritmer, hvor opgaver er planlagt baseret på deres prioritet eller deadline. Heap-datastrukturen giver effektiv adgang til opgaven med højest prioritet, hvilket gør den til en nyttig datastruktur til jobplanlægningsapplikationer.
Fordele ved Max-Heap Data Structure:
- Oprethold den maksimale værdi effektivt: En max heap giver konstant adgang til det maksimale element i heapen, hvilket gør det nyttigt i applikationer, hvor det maksimale element skal findes hurtigt.
- Effektive indsætnings- og sletningshandlinger: Indsæt- og sletningsoperationerne i en max-heap har en tidskompleksitet på O(log n), hvilket gør dem effektive til store samlinger af elementer.
- Prioriterede køer: En max heap kan bruges til at implementere en prioritetskø, hvilket er nyttigt i mange applikationer såsom jobplanlægning, opgaveprioritering og hændelsesdrevet simulering.
- Sortering: En max heap kan bruges til at implementere heapsort, som er en effektiv sorteringsalgoritme, der har en worst-case tidskompleksitet på O(n log n).
- Pladseffektivitet: En max heap kan implementeres som et array, hvilket kræver mindre hukommelse sammenlignet med andre datastrukturer såsom et binært søgetræ eller en linket liste.
Max heap datastruktur er et nyttigt og effektivt værktøj til at vedligeholde og manipulere samlinger af elementer, især når det maksimale element skal tilgås hurtigt, eller når elementer skal sorteres eller prioriteres.
