Max Heap în Java
A max-heap este un arbore binar complet în care valoarea din fiecare nod intern este mai mare sau egală cu valorile din copiii acelui nod. Maparea elementelor unui heap într-o matrice este trivială: dacă un nod este stocat cu un index k, atunci copilul său din stânga este stocat la indexul 2k + 1 și cel din dreapta la indexul 2k + 2.
Ilustrare: Max Heap
Cum este reprezentat Max Heap?
A-Max Heap este un arbore binar complet. Heap-ul A-Max este de obicei reprezentat ca o matrice. Elementul rădăcină va fi la Arr[0]. Tabelul de mai jos prezintă indecșii altor noduri pentru ith nod, adică Arr[i]:
Arr[(i-1)/2] Returnează nodul părinte.
Arr[(2*i)+1] Returnează nodul copil stâng.
Arr[(2*i)+2] Returnează nodul secundar corect.
Operațiunile pe Max Heap sunt după cum urmează:
- getMax(): Returnează elementul rădăcină din Max Heap. Complexitatea de timp a acestei operațiuni este O(1) .
- extractMax(): Elimină elementul maxim din MaxHeap . Complexitatea de timp a acestei operațiuni este O(Log n) deoarece această operație trebuie să mențină proprietatea heap prin apelarea metoda heapify(). după îndepărtarea rădăcinii.
- introduce(): Introducerea unei noi chei ia O(Log n) timp. Adăugăm o cheie nouă la capătul arborelui. Dacă noua cheie este mai mică decât cea părinte, atunci nu trebuie să facem nimic. În caz contrar, trebuie să traversăm în sus pentru a remedia proprietatea heap încălcată.
Notă: În implementarea de mai jos, facem indexare din indexul 1 pentru a simplifica implementarea.
Metode:
Există 2 metode prin care putem atinge obiectivul enumerat:
- Abordare de bază prin creare maxHeapify() metodă
- Folosind Collections.reverseOrder() metoda prin funcții de bibliotecă
Metoda 1: Abordare de bază prin creare maxHeapify() metodă
Vom crea o metodă presupunând că subarborele din stânga și din dreapta sunt deja îngrămădite, trebuie doar să reparăm rădăcina.
Exemplu
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>(dimensiune /> 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(poz)]) { swap(poz, leftChild(poz)); maxHeapify(leftChild(poz)); } else { swap(poz, dreaptaCopil(poz)); maxHeapify(rightChild(poz)); } } } // Metoda 7 // Inserează un nou element în heap maxim public void insert(int element) { Heap[size] = element; // Traversează în sus și remediază proprietatea încălcată int curent = dimensiune; while (Heap[curent]> Heap[parent(current)]) { swap(current, parent(current)); curent = părinte(curent); } dimensiune++; } // Metoda 8 // Pentru a afișa heap public void print() { for (int i = 0; i 2; i++) { System.out.print('Parent Node: ' + Heap[i]); if (leftChild(i) // dacă copilul este în afara limitei // ale matricei System.out.print(' Left Child Node: ' + Heap[leftChild(i)]); if (rightChild(i) ) // indexul secundar nu trebuie // să fie în afara indexului matricei System.out.print(' Right Child Node: ' + Heap[rightChild(i)]); ; // pentru linia nouă } } // Metoda 9 // Eliminați un element din heap maxim public int extractMax() { int popped = Heap[0] = Heap[--size]; ; return a apărut } // Metoda 10 // metoda driverului principal public static void main(String[] arg) { // Afișează mesajul pentru o mai bună lizibilitate System.out.println('MaxHeap este '); = new MaxHeap(15); maxHeap.insert(19); maxHeap.insert(22); maxHeap.insert(9); valoare în heap System.out.println('Valoarea maximă este ' + maxHeap.extractMax()); } }>>> |
>
// 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()); } }>
Ieșire
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
