Max Heap Java
A maksimalus krūvas yra pilnas dvejetainis medis, kuriame kiekvieno vidinio mazgo reikšmė yra didesnė arba lygi to mazgo antrinių verčių reikšmėms. Krūvos elementų atvaizdavimas į masyvą yra trivialus: jei mazgas saugomas indeksu k, tada jo kairysis vaikas saugomas indeksu 2k + 1, o dešinysis - 2k + 2.
Iliustracija: Max Heap
Kaip vaizduojamas Maxas Heapas?
A-Max Heap yra pilnas dvejetainis medis. A-Max krūva paprastai vaizduojama kaip masyvas. Šakninis elementas bus Arr[0]. Žemiau esančioje lentelėje rodomi kitų mazgų indeksai ith mazgas, ty Arr[i]:
Arr[(i-1)/2] Grąžina pirminį mazgą.
Arr[(2*i)+1] Grąžina kairįjį antrinį mazgą.
Arr[(2*i)+2] Grąžina dešinįjį antrinį mazgą.
„Max Heap“ operacijos yra tokios:
- getMax (): Tai grąžina pagrindinį Max Heap elementą. Šios operacijos laiko sudėtingumas yra O(1) .
- ExtractMax(): Pašalina maksimalų elementą iš MaxHeap . Šios operacijos laiko sudėtingumas yra O (Žurnalas n) nes atliekant šią operaciją reikia išlaikyti krūvos savybę skambinant heapify() metodas pašalinus šaknį.
- Įdėti(): Naujo rakto įdėjimas užtrunka O (Žurnalas n) laikas. Medžio gale pridedame naują raktą. Jei naujasis raktas yra mažesnis už pirminį raktą, nieko daryti nereikia. Priešingu atveju turime važiuoti aukštyn, kad pataisytume pažeistą krūvos ypatybę.
Pastaba: Toliau pateiktame įgyvendinime indeksuojame nuo 1 indekso, kad supaprastintume įgyvendinimą.
Metodai:
Yra 2 būdai, kuriais galime pasiekti išvardintą tikslą:
- Pagrindinis požiūris kuriant maxHeapify() metodas
- Naudojant Collections.reverseOrder() metodas per bibliotekos funkcijas
1 būdas: Pagrindinis požiūris kuriant maxHeapify() metodas
Mes sukursime metodą darydami prielaidą, kad kairysis ir dešinysis pomedžiai jau yra sukrauti, mums reikia tik pataisyti šaknį.
Pavyzdys
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>(dydis />> |
>
// 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()); } }>
Išvestis
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
