A max-hög är ett komplett binärt träd där värdet i varje intern nod är större än eller lika med värdena i den nodens barn. Att mappa elementen i en hög till en array är trivialt: om en nod lagras ett index k, så lagras dess vänstra underordnade vid index 2k + 1 och dess högra underordnade vid index 2k + 2.
java bubbel sortering
Illustration: Max Heap
Hur representeras Max Heap?
A-Max Heap är ett komplett binärt träd. A-Max-hög representeras vanligtvis som en array. Rotelementet kommer att vara vid Arr[0]. Tabellen nedan visar index för andra noder för ith nod, dvs Arr[i]:
Arr[(i-1)/2] Returnerar den överordnade noden.
Arr[(2*i)+1] Returnerar den vänstra underordnade noden.
Arr[(2*i)+2] Returnerar den högra underordnade noden.
Operationer på Max Heap är som följer:
- getMax(): Det returnerar rotelementet i Max Heap. Tidskomplexiteten för denna operation är O(1) .
- extraheraMax(): Tar bort det maximala elementet från MaxHeap . Tidskomplexiteten för denna operation är O(Logg n) eftersom denna operation behöver underhålla heap-egenskapen genom att anropa heapify() metod efter att ha tagit bort roten.
- Föra in(): Att sätta in en ny nyckel tar O(Logg n) tid. Vi lägger till en ny nyckel i slutet av trädet. Om den nya nyckeln är mindre än sin förälder behöver vi inte göra någonting. Annars måste vi korsa upp för att fixa den kränkta högegendomen.
Notera: I implementeringen nedan gör vi indexering från index 1 för att förenkla implementeringen.
Metoder:
medelvärde vs genomsnitt
Det finns två metoder för att uppnå målet enligt listan:
- Grundläggande tillvägagångssätt genom att skapa maxHeapify() metod
- Använder sig av Collections.reverseOrder() metod via biblioteksfunktioner
Metod 1: Grundläggande tillvägagångssätt genom att skapa maxHeapify() metod
Vi kommer att skapa en metod som antar att de vänstra och högra underträden redan är upphopade, vi behöver bara fixa roten.
Exempel
Java
java heltal till sträng
// Java program to implement Max Heap> // Main class> public> class> MaxHeap {> >private> int>[] Heap;> >private> int> size;> >private> int> maxsize;> >// Constructor to initialize an> >// empty max heap with given maximum> >// capacity> >public> MaxHeap(>int> maxsize)> >{> >// This keyword refers to current instance itself> >this>.maxsize = maxsize;> >this>.size =>0>;> >Heap =>new> int>[>this>.maxsize];> >}> >// Method 1> >// Returning position of parent> >private> int> parent(>int> pos) {>return> (pos ->1>) />2>; }> >// Method 2> >// Returning left children> >private> int> leftChild(>int> pos) {>return> (>2> * pos) +>1>; }> >// Method 3> >// Returning right children> >private> int> rightChild(>int> pos)> >{> >return> (>2> * pos) +>2>;> >}> >// Method 4> >// Returning true if given node is leaf> >private> boolean> isLeaf(>int> pos)> >{> >if> (pos>(storlek />2>) && pos <= size) {> >return> true>;> >}> >return> false>;> >}> >// Method 5> >// Swapping nodes> >private> void> swap(>int> fpos,>int> spos)> >{> >int> tmp;> >tmp = Heap[fpos];> >Heap[fpos] = Heap[spos];> >Heap[spos] = tmp;> >}> >// Method 6> >// Recursive function to max heapify given subtree> >private> void> maxHeapify(>int> pos)> >{> >if> (isLeaf(pos))> >return>;> >if> (Heap[pos] || Heap[pos] if (Heap[leftChild(pos)]>Heap[rightChild(pos)]) { swap(pos, leftChild(pos)); maxHeapify(leftChild(pos)); } annat { swap(pos, rightChild(pos)); maxHeapify(rightChild(pos)); } } } // Metod 7 // Infogar ett nytt element till max heap public void insert(int element) { Heap[size] = element; // Traverse upp och fixa kränkt egenskap int ström = storlek; while (Hög[aktuell]> Hög[förälder(aktuell)]) { swap(aktuell, förälder(aktuell)); ström = förälder(ström); } storlek++; } // Metod 8 // För att visa heap public void print() { for (int i = 0; i 2; i++) { System.out.print('Parent Node : ' + Heap[i]); if (leftChild(i) // om barnet är utanför gränsen // av arrayen System.out.print(' Vänster Child Node: ' + Heap[leftChild(i)]); if (rightChild(i) ) // det högra underordnade indexet får inte // vara utanför indexet för arrayen System.out.print(' Right Child Node: ' + Heap[rightChild(i)]); ; // för ny rad } } // Metod 9 // Ta bort ett element från max heap public int extractMax() { int popped = Heap[0] = maxHeapify(0) ; return popped; } // Metod 10 // main driver method public static void main(String[] arg) { // Visa meddelande för bättre läsbarhet System.out.println('MaxHeap är '); = new MaxHeap(15); // Infoga noder maxHeap.insert(3); maxHeap.insert(19); maxHeap.insert(22); värde i heap System.out.println('Maxvärdet är ' + maxHeap.extractMax()); } }> |
>
android versioner
>Produktion
The Max Heap is Parent Node : 84 Left Child Node: 22 Right Child Node: 19 Parent Node : 22 Left Child Node: 17 Right Child Node: 10 Parent Node : 19 Left Child Node: 5 Right Child Node: 6 Parent Node : 17 Left Child Node: 3 Right Child Node: 9 The max val is 84>
Metod 2: Använder metoden Collections.reverseOrder() via biblioteksfunktioner
Vi använder klassen PriorityQueue för att implementera Heaps i Java. Som standard implementeras Min Heap av denna klass. För att implementera Max Heap använder vi metoden Collections.reverseOrder().
Exempel
Java
// Java program to demonstrate working> // of PriorityQueue as a Max Heap> // Using Collections.reverseOrder() method> // Importing all utility classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Creating empty priority queue> >PriorityQueue pQueue> >=>new> PriorityQueue(> >Collections.reverseOrder());> >// Adding items to our priority queue> >// using add() method> >pQueue.add(>10>);> >pQueue.add(>30>);> >pQueue.add(>20>);> >pQueue.add(>400>);> >// Printing the most priority element> >System.out.println(>'Head value using peek function:'> >+ pQueue.peek());> >// Printing all elements> >System.out.println(>'The queue elements:'>);> >Iterator itr = pQueue.iterator();> >while> (itr.hasNext())> >System.out.println(itr.next());> >// Removing the top priority element (or head) and> >// printing the modified pQueue using poll()> >pQueue.poll();> >System.out.println(>'After removing an element '> >+>'with poll function:'>);> >Iterator itr2 = pQueue.iterator();> >while> (itr2.hasNext())> >System.out.println(itr2.next());> >// Removing 30 using remove() method> >pQueue.remove(>30>);> >System.out.println(>'after removing 30 with'> >+>' remove function:'>);> >Iterator itr3 = pQueue.iterator();> >while> (itr3.hasNext())> >System.out.println(itr3.next());> >// Check if an element is present using contains()> >boolean> b = pQueue.contains(>20>);> >System.out.println(>'Priority queue contains 20 '> >+>'or not?: '> + b);> >// Getting objects from the queue using toArray()> >// in an array and print the array> >Object[] arr = pQueue.toArray();> >System.out.println(>'Value in array: '>);> >for> (>int> i =>0>; i System.out.println('Value: ' + arr[i].toString()); } }> |
>
konvertera strängdatum
>Produktion
Head value using peek function:400 The queue elements: 400 30 20 10 After removing an element with poll function: 30 10 20 after removing 30 with remove function: 20 10 Priority queue contains 20 or not?: true Value in array: Value: 20 Value: 10>