EN Max-Heap er definert som en type Heap-datastrukturen er en type binært tre som ofte brukes i informatikk til forskjellige formål, inkludert sortering, søk og organisering av data.
Introduksjon til Max-Heap Data Structure
Formål og brukstilfeller av Max-Heap:
- Prioritetskø: En av de primære bruksområdene for heap-datastrukturen er å implementere prioriterte køer.
- haugsortering: Heap-datastrukturen brukes også i sorteringsalgoritmer.
- Minnehåndtering: Heap-datastrukturen brukes også i minnehåndtering. Når et program trenger å tildele minne dynamisk, bruker det haugdatastrukturen for å holde styr på tilgjengelig minne.
- Dijkstras korteste vei-algoritme bruker en heap-datastruktur for å holde styr på toppunktene med kortest vei fra kildepunktet.
Max-Heap-datastruktur på forskjellige språk:
1. Max-Heap i C++
En maks haug kan implementeres ved å bruke priority_queue beholder fra Standard malbibliotek (STL) . De priority_queue container er en type containeradapter som gir en måte å lagre elementer i en kølignende datastruktur der hvert element har en prioritet knyttet til seg.
Synt ax: priority_queuemaxH;>2. Max-Heap i Java
I Java kan en maksimal haug implementeres ved å bruke Prioritetskø klasse fra java.util-pakken . PriorityQueue-klassen er en prioritetskø som gir en måte å lagre elementer i en kølignende datastruktur der hvert element har en prioritet knyttet til seg.
Syntax : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());>3. Max-Heap i Python
I Python kan en maksimal haug implementeres ved å bruke heapq modul, som gir funksjoner for implementering av heaps. Spesielt gir heapq-modulen en måte å lage og manipulere heap-datastrukturer på.
Synt ax: heap = [] heapify(heap)>4. Max-Heap i C#
I C# kan en maks haug implementeres ved å bruke PriorityQueue-klassen fra System.Collections.Generisk navneområde . PriorityQueue-klassen er en prioritetskø som gir en måte å lagre elementer i en kølignende datastruktur der hvert element har en prioritet knyttet til seg.
Syntax: var maxHeap = new PriorityQueue((a, b) =>b - a);>5. Max-Heap i JavaScript
En maks haug er et binært tre der hver node har en verdi større enn eller lik dens barn. I JavaScript kan du implementere en maksimal haug ved å bruke en matrise, der det første elementet representerer rotnoden, og barna til en node ved indeksen Jeg ligger på indekser 2i+1 og 2i+2.
Syntax: const miaxHeap = new MaxHeap();>Forskjellen mellom Max og Min Heap
Min haug Max Heap 1. I en Min-heap må nøkkelen som er tilstede ved rotnoden være mindre enn eller lik blant nøklene som er tilstede på alle dens barn. I en Max-Heap må nøkkelen som er tilstede ved rotnoden være større enn eller lik blant nøklene som er tilstede på alle dens barn. 2. I en Min-Heap er minimum nøkkelelementet tilstede ved roten. I en Max-Heap er det maksimale nøkkelelementet tilstede ved roten. 3. En Min-heap bruker den stigende prioritet. En Max-Heap bruker synkende prioritet. 4. I konstruksjonen av en Min-Heap har det minste elementet prioritet. Ved bygging av en Max-Heap har det største elementet prioritet. 5. I en Min-heap er det minste elementet det første som blir tatt ut av haugen. I en Max-Heap er det største elementet det første som blir spratt fra haugen. Intern implementering av Max-Heap-datastruktur:
EN Min haug er vanligvis representert som en matrise .
- Rotelementet vil være kl Arr[0] .
- For hvilken som helst ith-node Arr[i].
- venstre barn lagres i indeks 2i+1
- Høyre barn lagres i indeks 2i+2
- Foreldre lagres i indeksgulvet ((i-1)/2)
Den interne implementeringen av Max-Heap krever 3 hovedtrinn:
- Innsetting : For å sette inn et nytt element i heapen, legges det til på slutten av matrisen og bobles deretter opp til det tilfredsstiller heap-egenskapen.
- Sletting : For å slette maksimumselementet (roten av heapen), byttes det siste elementet i matrisen med roten, og den nye roten bobles ned til den tilfredsstiller heap-egenskapen.
- Heapify : En heapify-operasjon kan brukes til å lage en maksimal heap fra en usortert matrise.
Operasjoner på Max-heap-datastrukturen og deres implementering:
Her er noen vanlige operasjoner som kan utføres på en Heap Data Structure-datastruktur,
1. Innsetting i Max-Heap Data Structure :
Elementer kan settes inn i haugen etter en lignende tilnærming som diskutert ovenfor for sletting. Tanken er å:
- Øk først haugstørrelsen med 1, slik at den kan lagre det nye elementet.
- Sett inn det nye elementet på slutten av heapen.
- Dette nylig innsatte elementet kan forvrenge egenskapene til Heap for foreldrene. Så, for å beholde egenskapene til Heap, heapify dette nylig innsatte elementet etter en nedenfra og opp-tilnærming.
Illustrasjon:
Anta at haugen er en maks-haug som:
Innsetting i Max heap
Implementering av innsettingsoperasjon i Max-Heap:
C++
motstridende søk
// 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[foreldre]) {>>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[foreldre]) {>>>// 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[foreldre]) {>>// 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[foreldre]) {>>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[foreldre]:>>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....>'''>>>Produksjon15 5 10 2 4 3>Tidskompleksitet: O(log(n)) ( hvor n er antall elementer i haugen )
Hjelpeplass: På)2. Sletting i Max-Heap Data Structure :
Å slette et element på en hvilken som helst mellomposisjon i haugen kan være kostbart, så vi kan ganske enkelt erstatte elementet som skal slettes med det siste elementet og slette det siste elementet i haugen.
- Erstatt roten eller elementet som skal slettes med det siste elementet.
- Slett det siste elementet fra heapen.
- Siden det siste elementet nå er plassert på posisjonen til rotnoden. Så det kan hende den ikke følger haugeiendommen. Derfor, heapify den siste noden plassert ved posisjonen til roten.
Illustrasjon :
Anta at haugen er en maks-haug som:
Maks haugdatastruktur
Elementet som skal slettes er root, dvs. 10.
Prosess :
Det siste elementet er 4.
Trinn 1: Erstatt det siste elementet med root, og slett det.
Max Heap
Steg 2 : Heapify rot.
Siste haug:
Max Heap
Implementering av sletteoperasjon 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 fet 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øyre barn er større enn størst så langt if (r og arr[r]> arr[størst]): størst = r # Hvis største ikke er rot if (størst != i) : arr[i],arr[størst]=arr[størst],arr[i] #Rekursivt heapify det berørte undertreet heapify(arr, n, størst) #Funksjon for å slette roten fra Heap def deleteRoot(arr): global n # Hent det siste elementet lastElement = arr[n - 1] # Erstatt rot med siste element arr[0] = lastElement # Reduser størrelsen på haugen med 1 n = n - 1 # heapify rotnoden heapify(arr, n, 0) # En verktøyfunksjon for å skrive ut array av størrelse n def printArray(arr, n): for i in range(n): print(arr[i],end=' ') print() # Driver Code if __name__ == '__main__': # Matriserepresentasjon av Max-Heap # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot( arr) printArray(arr, n) # Denne koden er bidratt av Rajat Kumar.>>>Produksjon5 4 3 2>Tidskompleksitet : O(log n) hvor n er antall elementer i haugen
Hjelpeplass: På)3.Peek-operasjon på Max-heap-datastruktur:
For å få tilgang til det maksimale elementet (dvs. roten til haugen), returneres verdien til rotnoden. Tidskompleksiteten til kikk i en maks haug er O(1).
Peak Element Of Max- Heap
Implementering av Peek-operasjon 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);>>}>}>transformer streng til int>>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)>>>ProduksjonPeak element: 9>Tidskompleksitet :
- I en maks haug implementert ved hjelp av enarrayeller en liste, kan toppelementet nås i konstant tid, O(1), da det alltid er plassert ved roten av haugen.
- I en maks haug implementert ved hjelp av enbinært tre, kan toppelementet også nås i O(1)-tid, da det alltid er plassert ved roten av treet.
Hjelpeplass: På)
4.Heapify-operasjon på Max-heap Data Structure:
En heapify-operasjon kan brukes til å lage en maksimal heap fra en usortert matrise. Dette gjøres ved å starte ved den siste noden uten blader og gjentatte ganger utføre boble ned-operasjonen til alle noder tilfredsstiller heap-egenskapen. Tidskompleksiteten til heapify i en maks haug er O(n).
Heapify-operasjoner i Max-Heap
hvor finner jeg nettleserinnstillingene mine5.Søkeoperasjon på Max-heap Data Structure:
For å søke etter et element i den maksimale haugen, kan et lineært søk utføres over matrisen som representerer haugen. Imidlertid er tidskompleksiteten til et lineært søk O(n), noe som ikke er effektivt. Derfor er søk ikke en vanlig operasjon i en maks haug.
Her er en eksempelkode som viser hvordan du søker etter et element i en maksimal haug ved å bruke std::finn() :
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>siste) {>>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.'>)>>>ProduksjonElement found in the max heap.>Tidskompleksitet : O(n), der n er størrelsen på haugen.
Auxiliary Space : O(n),Anvendelser av Max-Heap Data Structure:
- Heapsort-algoritme: Heap-datastrukturen er grunnlaget for heapsort-algoritmen, som er en effektiv sorteringsalgoritme med en worst-case tidskompleksitet på O(n log n). Heapsort-algoritmen brukes i ulike applikasjoner, inkludert databaseindeksering og numerisk analyse.
- Minnehåndtering: Heap-datastrukturen brukes i minnestyringssystemer for å tildele og deallokere minne dynamisk. Heapen brukes til å lagre minneblokkene, og haugdatastrukturen brukes til å effektivt administrere minneblokkene og allokere dem til programmer etter behov.
- Grafalgoritmer: Heap-datastrukturen brukes i ulike grafalgoritmer, inkludert Dijkstras algoritme, Prims algoritme og Kruskals algoritme. Disse algoritmene krever effektiv prioritetskøimplementering, som kan oppnås ved å bruke heapdatastrukturen.
- Jobbplanlegging: Heap-datastrukturen brukes i jobbplanleggingsalgoritmer, der oppgaver planlegges basert på deres prioritet eller tidsfrist. Heap-datastrukturen gir effektiv tilgang til den høyest prioriterte oppgaven, noe som gjør den til en nyttig datastruktur for jobbplanleggingsapplikasjoner.
Fordeler med Max-Heap Data Structure:
- Oppretthold maksimalverdien effektivt: En maks haug gir konstant tilgang til det maksimale elementet i haugen, noe som gjør det nyttig i applikasjoner der det maksimale elementet må finnes raskt.
- Effektive innsettings- og slettingsoperasjoner: Insert- og delete-operasjonene i en maks-heap har en tidskompleksitet på O(log n), noe som gjør dem effektive for store samlinger av elementer.
- Prioriterte køer: En maksimal haug kan brukes til å implementere en prioritert kø, som er nyttig i mange applikasjoner som jobbplanlegging, oppgaveprioritering og hendelsesdrevet simulering.
- Sortering: En maks heap kan brukes til å implementere heapsort, som er en effektiv sorteringsalgoritme som har en worst-case tidskompleksitet på O(n log n).
- Plasseffektivitet: En maksimal heap kan implementeres som en matrise, som krever mindre minne sammenlignet med andre datastrukturer som et binært søketre eller en koblet liste.
Max heap-datastruktur er et nyttig og effektivt verktøy for å vedlikeholde og manipulere samlinger av elementer, spesielt når det maksimale elementet må nås raskt eller når elementer må sorteres eller prioriteres.
