Arborele binar
În Java, există multe tipuri diferite de structuri de date. Heap-ul se bazează pe o structură arborescentă numită arbore binar . Un arbore binar este format din noduri, fiecare dintre acestea putând avea maximum 2 noduri copil:

Max Heap
Max heap (sau maxheap) este un arbore binar complet . Important este că nodul părinte TREBUIE să aibă o valoare mai mare sau egală cu cea a nodurilor secundare stânga și dreapta. Dacă acest lucru nu este respectat, nu aveți o grămadă maximă. Min heap, pe de altă parte, este opusul cu rădăcina ca cea mai mică valoare cu noduri succesive care cresc în valoare; fiecare nod copil are o valoare mai mare sau egală cu părintele său. Este, de asemenea, un arbore binar complet. Un exemplu de heap maxim este:
Clasa PriorityQueue
Mulțile în Java pot fi implementate folosind clasa PriorityQueue . PriorityQueue sunt folosite pentru a găsi elementul cel mai sau cel mai puțin important dintr-o colecție. Clasa PriorityQueue poate fi găsită în java.util.package . PriorityQueues trebuie să fie formate din obiecte care sunt comparabile, astfel încât să fie plasate într-o anumită ordine în coadă. PriorityQueue poate avea un comparator astfel încât să se facă o comparație între obiecte și coada formată conform acestei comparații. Un exemplu este:
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main
{
public static void main(String[] args) {
// Create PriorityQueue with comparator for ascending order of array length
PriorityQueue intQueue = new PriorityQueue((a,b) -> a - b);
Integer [] array1 = {1, 2, 4, 6, 8, 9};
Integer [] array2 = {3, 6, 9};
Integer [] array3 = {2, 4, 8, 16, 32, 64, 128};
Integer [] array4 = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55};
Integer [] array5 = {4};
//Add the array lengths to intQueue
intQueue.add(array1.length);
intQueue.add(array2.length);
intQueue.add(array3.length);
intQueue.add(array4.length);
intQueue.add(array5.length);
//Write out contents of intQueue as stored
while (intQueue.size() != 0) {
System.out.println(intQueue.remove());
}
}
}
Oferă rezultate:
1 3 6 7 11
În acest exemplu, dimensiunea implicită a intQueue este 11, deci nu a fost specificată (de obicei primul argument înaintea comparatorului) și comparatorul a fost dat ca:
(a,b) -> a - b
Aceasta va face o comparație între elementele din intQueue și le va sorta în lungimi de matrice în ordine crescătoare.
Implementarea PriorityQueue pentru a crea un heap maxim
Clasa PriorityQueue este implicit la min heap fără un comparator. Heap min este opusul heap max și, prin urmare, rădăcina este cea mai mică valoare, iar nodurile secundare succesive sunt mai mari sau egale cu rădăcina și nodurile parentale ulterioare. Din acest motiv, pentru heap maxim, este necesar să folosiți reverseOrder() din cadrul Java’s Collections ca comparator. Acest lucru ne va asigura că obținem un heap maxim și nu un heap minim. Această clasă are metode utile, cum ar fi add() , contains() , remove() , poll() și peek() .Metodă | Descriere | Complexitatea timpului |
---|---|---|
adauga (J) | Adaugă elementul J la capătul arborelui | O(LogN) |
elimina (J) | Eliminați valoarea J din arbore | PE) |
sondaj() | Îndepărtează elementul maxim al arborelui | O(LogN) |
arunca o privire() | Returnează elementul rădăcină în partea de sus a arborelui | O(1) |
conține (J) | Returnează adevărat dacă J este în coadă, fals dacă nu | PE) |

mport java.util.Collections;
import java.util.PriorityQueue;
public class MaxHeap {
public static void writeQueue(PriorityQueue<Integer> priorityQueue)
{
// Write out elements in queue, priorityQueue, and remove them using poll()
while(priorityQueue.size() != 0)
{
System.out.println(priorityQueue.poll());
}
}
public static void writeMaxHeap(PriorityQueue<Integer> priorityQueue)
{
// Write out elements in queue as a max heap - root, left child, right child, etc
for (Integer element : priorityQueue) {
System.out.println(element);
}
}
public static void main(String args[])
{
// Array of numbers to create a max heap array from
int[] theArray = {5, 3, 13, 10, 99, 19, 6, 51, 9};
// theQueue is created
PriorityQueue<Integer> theQueue =
new PriorityQueue<Integer>(Collections.reverseOrder());
// Elements are added to theQueue
for (int i = 0 ; i <theArray.length; ++i)
{
theQueue.add(theArray[i]);
}
// The head or root element (priority element) is printed out
System.out.println("The root value is : " + theQueue.peek());
// Find size of theQueue. Use method size()
Integer s = theQueue.size();
System.out.println("Size of theQueue? " + s);
// All elements of theQueue are printed in terms of parent,
// left child, right child
System.out.println("theQueue written using for loop:");
writeMaxHeap(theQueue);
// Does theQueue contain 10? Use method contains()
boolean b = theQueue.contains(10);
System.out.println("Does theQueue contain 10? " + b);
// Erasing value 10 from array using remove()
theQueue.remove(10);
// All elements of theQueue are printed out and removed.
// Each one is the maximum value left in the queue.
// At the end theQueue will be empty
System.out.println("theQueue written out using poll():");
writeQueue(theQueue);
// Find size of theQueue. Use method size()
s = theQueue.size();
System.out.println("Size of theQueue? " + s);
}
}
Ieșire:
99 Dimensiunea cozii? 9 theQueue scris folosind bucla for 99 51 19 13 10 5 6 3 9 Coada conține 10? true theQueue scris folosind poll() 99 51 19 13 9 6 5 3 Dimensiunea cozii? 0
Max Heapify
Algoritmul Max Heapify este utilizat pentru a se asigura că un arbore binar este un heap maxim. Dacă ne aflăm la un nod, n, iar nodurile sale secundare, stânga și dreapta sunt, de asemenea, grămezi maxime în sine, atunci grozav, avem un heap maxim. Dacă acest lucru nu este cazul în întregul copac, atunci nu avem o grămadă maximă. Algoritmul Max Heapify este folosit pentru a sorta arborele astfel încât să adere la principiile maxheap. Max Heapify funcționează pe un singur nod. Dacă cerința este ca matricea să fie o matrice maxheap, atunci toți sub-arborele trebuie convertiți în maxheap înainte de rădăcină, unul câte unul. Algoritmul trebuie utilizat pe fiecare nod. Acest lucru se va face pe N/2 noduri (frunzele vor respecta cerințele maxime de heap). Complexitatea de timp a heap-ului este O(NlogN), iar pentru un nod la înălțimea X, complexitatea de timp este O(X). Următorul cod arată cum să maximizați un copac (o matrice).
public class MaxHeapify
{
public static Integer[] maxHeapify(Integer[ ] array, Integer i)
{
// Create left-child and right-child for the node in question
Integer leftChild = 2 * i + 1;
Integer rightChild = 2 * i + 2;
// Assign maxVal to parent node, i
Integer maxVal = i;
// Set maxVal to greater of the two: node or left-child
if( leftChild < array.length && array[leftChild] > array[maxVal] )
maxVal = leftChild;
// Set maxVal to greater of the two: maxVal or right-child
if( rightChild < array.length && array[rightChild] > array[maxVal] )
maxVal = rightChild;
// Check if maxVal is not equal to parent node, then set parent node to
// maxVal, swap values and then do a maxheapify on maxVal
// which is now the previous parent node
if( maxVal != i )
{
Integer value = array[i];
array[i] = array[maxVal];
array[maxVal] = value;
array = maxHeapify(array, maxVal);
}
return array;
}
public static Integer[] maxHeapCreate(Integer array[])
{
// Call maxHeapify to arrange array in a max heap
Integer [] theNewArr = array;
for( Integer i = array.length/2; i >= 0; i-- )
theNewArr = maxHeapify(array, i);
return theNewArr;
}
public static void main(String[] args)
{
// Create array to be maxheapified, theArray,
// and array, newArray, to write results into, by calling maxheapCreate
// newArray will now be a maxheap
Integer[] theArray = {5, 3, 13, 10, 99, 19, 6, 51, 9};
Integer[ ] newArray = maxHeapCreate(theArray);
// Print out contents of newArray
System.out.println("newArray:");
for(int i = 0; i < newArray.length; ++i)
{
System.out.println(newArray[i]);
}
// Print out labelled contents of newArray
System.out.println(" root : " + newArray[0]);
for (int i = 0; i <= newArray.length/2 - 1; i++) {
System.out.print(" parent node : " + newArray[i] + " left child : " +
newArray[(2*i)+1] + " right child :" + newArray[(2*i)+2]);
System.out.println();
}
}
}
Oferă rezultate:
newArray:99 51 19 10 3 13 65 9 rădăcină : 99 nod părinte : 99 copil stâng : 51 copil drept :19 nod părinte : 51 copil stâng : 10 copil drept :3 nod părinte : 19 copil stâng : 13 copil drept :6 nodul părinte : 10 copil stâng : 5 dreapta copil :999999999 nodul părinte : 99 copil stâng : 51 copil drept :19 nodul părinte : 51 copil stâng : 10 copil drept :3 nodul părinte : 19 copil stâng : 13 copil drept :6 nodul părinte : 10 copil stâng : 5 copil drept :999 nodul părinte : 99 copil stâng : 51 copil drept :19 nodul părinte : 51 copil stâng : 10 copil drept :3 nodul părinte : 19 copil stâng : 13 copil drept :6 nodul părinte : 10 copil stâng : 5 copil drept :96 nod părinte : 10 copil stâng : 5 copil drept :96 nod părinte : 10 copil stâng : 5 copil drept :9
În acest cod, Array este creat și umplut cu numere. Este creată o a doua matrice, newArray , și de data aceasta va conține rezultatul metodei, maxheapCreate , matricea maxim heap. Metoda maxHeapCreate este apelată din main , iar aici este creată o nouă matrice, theNewArr , care este completată cu rezultatele maxHeapify . Acest lucru se face prin bucla peste jumătate din dimensiunea matricei de intrare. Pentru fiecare trecere a buclei, metoda maxHeapify este apelată începând cu elementul din mijlocul matricei și terminând cu primul. Pentru fiecare apel de maxHeapify, sunt găsite copilul stâng și copilul drept al nodului părinte, i, și se fac verificări pentru a găsi care este cel mai mare dintre cele trei, definindu-l ca maxVal . Dacă maxVal nu este egal cu nodul părinte, atunci se face o schimbare, astfel încât nodul părinte și maxVal să fie schimbate și apoi maxHeapify este apelat din nou de data aceasta pe maxVal și se efectuează aceiași pași ca înainte. În cele din urmă, heap-ul maxim va fi creat și nu vor mai fi iterații de efectuat. Matricea actualizată, array , este acum returnată la main ca newArray și apoi fiecare element consecutiv este imprimat pe consolă. newArrayeste acum o grămadă maximă. Rețineți că, la fel ca în exemplul anterior, folosind PriorityQueue, numerele sunt scrise: rădăcină, copilul din dreapta al rădăcinii ca părinte, copilul din stânga al rădăcinii ca părinte, copilul din dreapta al primului copil din dreapta ca părinte, copilul din stânga al primului stanga-copil ca parinte, dreapta-copil al primului stanga-copil ca parinte, stanga-copil al primului drept-copil ca parinte etc. Sunt intr-o ordine putin diferita de cele cand se foloseste PriorityQueue deoarece comparatia se face intre elemente consecutive în timp ce în exemplul maxheapify, nodul este comparat cu următoarele două elemente succesive din matrice și schimbat pentru cea mai mare valoare. Pe scurt, sunt utilizați doi algoritmi diferiți. Ambele creează un heap maxim.
GO TO FULL VERSION