A maksimālā kaudze ir pilnīgs binārs koks, kurā vērtība katrā iekšējā mezglā ir lielāka vai vienāda ar vērtībām šī mezgla atvasinātajos. Kaudzes elementu kartēšana masīvā ir triviāla: ja mezglam ir saglabāts indekss k, tad tā kreisais bērns tiek saglabāts indeksā 2k + 1 un labais bērns indeksā 2k + 2.
Ilustrācija: Makss kaudze
Kā tiek attēlots Max Heap?
A-Max Heap ir pilnīgs binārais koks. A-Max kaudze parasti tiek attēlota kā masīvs. Saknes elements atradīsies Arr[0]. Zemāk redzamajā tabulā ir parādīti citu mezglu indeksi ith mezgls, t.i., Arr[i]:
Arr[(i-1)/2] Atgriež vecāku mezglu.
Arr[(2*i)+1] Atgriež kreiso pakārtoto mezglu.
Arr[(2*i)+2] Atgriež pareizo pakārtoto mezglu.
Darbības ar Max Heap ir šādas:
- getMax(): Tas atgriež Max Heap saknes elementu. Šīs operācijas laika sarežģītība ir O(1) .
- ekstraktsMax(): Noņem maksimālo elementu no MaxHeap . Šīs operācijas laika sarežģītība ir O(Žurnāls n) jo šai darbībai ir jāsaglabā kaudzes īpašums, zvanot uz heapify() metode pēc saknes noņemšanas.
- ievietot (): Jaunas atslēgas ievietošana prasa O(Žurnāls n) laiks. Mēs pievienojam jaunu atslēgu koka galā. Ja jaunā atslēga ir mazāka par tās vecāku, mums nekas nav jādara. Pretējā gadījumā mums ir jāpārvietojas augšup, lai labotu bojāto kaudzes īpašumu.
Piezīme: Tālāk sniegtajā ieviešanā mēs veicam indeksēšanu no 1. indeksi, lai vienkāršotu ieviešanu.
Metodes:
Ir 2 metodes, kā mēs varam sasniegt norādīto mērķi:
- Pamata pieeja, radot maxHeapify() metodi
- Izmantojot Collections.reverseOrder() metode, izmantojot bibliotēkas funkcijas
1. metode: Pamata pieeja, radot maxHeapify() metodi
Mēs izveidosim metodi, pieņemot, ka kreisais un labais apakškoks jau ir izveidots kaudzītē, mums ir jālabo tikai sakne.
Piemērs
Java
// 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>(izmērs />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)]>Kaudze[labaisBērns(poz)]) { swap(poz, kreisaisBērns(poz)); maxHeapify(leftChild(pos)); } else { swap(pos, rightChild(pos)); maxHeapify(labaisBērns(poz)); } } } // 7. metode // Ievieto jaunu elementu max kaudzes public void insert(int element) { Heap[size] = elements; // Traverse up and fix violated property int current = size; while (Heap[current]> Heap[parent(current)]) { mijmaiņas(pašreizējais, mātes(pašreizējais)); strāva = vecāks(strāva); } izmērs++; } // 8. metode // Lai parādītu kaudzi public void print() { for (int i = 0; i 2; i++) { System.out.print('Parent Node : ' + Heap[i]); if (leftChild(i) // ja bērns ir ārpus masīva System.out.print(' Left Child Node: ' + Heap[leftChild(i)]); if (rightChild(i) ) // pareizais pakārtotais indekss nedrīkst // atrasties ārpus masīva System.out.print(' Right Child Node: ' + Heap[rightChild(i)] indeksa System.out.println() // jaunai rindai } // 9. metode // Noņemt elementu no max kaudzes public int extractMax() { int popped = Heap[0] = Heap[--size]; ; return popped } // 10. metode // galvenā draivera metode public static void main(String[] arg) { // Parādīt ziņojumu labākai lasāmībai System.out.println('MaxHeap ir '); = new MaxHeap(15) // Pielāgotas ievades maxHeap.insert(17); maxHeap.insert(6); maxHeap.insert(9); vērtība kaudzītē System.out.println('Maksimālā vērtība ir ' + maxHeap.extractMax()); } }> |
dateformat.format java
>
>Izvade
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>
2. metode: Metodes Collections.reverseOrder() izmantošana, izmantojot bibliotēkas funkcijas
Mēs izmantojam PriorityQueue klasi, lai ieviestu Heaps Java. Pēc noklusējuma šī klase ir ieviesusi Min Heap. Lai ieviestu Max Heap, mēs izmantojam Collections.reverseOrder() metodi.
Piemērs
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()); } }> |
>
>Izvade
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>