Menú

Què és una estructura de dades Heap a Java

what is heap data structure java

Proveu El Nostre Instrument Per Eliminar Problemes

Aquest tutorial explica què és l'estructura de dades de Java Heap i conceptes relacionats com ara Min Heap, Max Heap, Heap Sort, Stack vs Heap amb exemples:

Un munt és una estructura de dades especial a Java. Un munt és una estructura de dades basada en arbre i es pot classificar com un arbre binari complet. Tots els nodes del munt estan ordenats en un ordre específic.

=> Visiteu aquí per veure la sèrie de formació de Java per a tothom

Estructura de dades de Heap

Què aprendreu:

Estructura de dades de pila a Java

A l'estructura de dades de l'emmagatzematge dinàmic, el node arrel es compara amb els seus fills i es disposa segons l'ordre. Per tant, si a és un node arrel i b és el seu fill, la propietat, clau (a)> = clau (b) generarà un munt màxim.

La relació anterior entre l'arrel i el node fill es diu 'Propietat Heap'.

Depenent de l'ordre dels nodes pare-fill, el munt és generalment de dos tipus:

# 1) Max-Heap :En un Max-Heap, la clau del node arrel és la més gran de totes les claus del munt. S'ha d'assegurar que la mateixa propietat sigui certa per a tots els subarbres del munt recursivament.

El diagrama següent mostra un Sample Max Heap. Tingueu en compte que el node arrel és més gran que els seus fills.

Exemple màxim de pila

# 2) Min-Heap :En el cas d'un Min-Heap, la clau de node arrel és la més petita o mínima entre totes les altres claus presents a l'emmagatzematge dinàmic. Com a l’emmagatzematge màxim, aquesta propietat hauria de ser recursiva per a la resta de subarbres de l’emmagatzematge.

Un exemple, d'un arbre Min-Heap, es mostra a continuació. Com podem veure, la clau arrel és la més petita de totes les altres claus del munt.

Arbre Min-Heap

Es pot utilitzar una estructura de dades de pila a les àrees següents:

  • Els munts s’utilitzen principalment per implementar cues de prioritat.
  • Especialment min-heap es pot utilitzar per determinar els camins més curts entre els vèrtexs d'un gràfic.

Com ja s'ha esmentat, l'estructura de dades de l'emmagatzematge dinàmic és un arbre binari complet que satisfà la propietat d'emmagatzematge dinàmic per a l'arrel i els fills. Aquest munt també es diu com a munt binari .

Munt binari

Un munt binari compleix les propietats següents:

  • Un munt binari és un arbre binari complet. En un arbre binari complet, tots els nivells excepte l'últim nivell estan completament omplerts. A l’últim nivell, les tecles queden el més esquerra possible.
  • Satisfà la propietat del munt. El muntatge binari pot ser màxim o mínim depenent de la propietat del munt que satisfaci.

Un munt binari normalment es representa com una matriu. Com que és un arbre binari complet, es pot representar fàcilment com una matriu. Així, en una representació de matriu de pila binària, l'element arrel serà A (0) on A és la matriu utilitzada per representar la pila binària.

Per tant, en general per a qualsevol itha la representació de matriu d’emmagatzematge dinàmic binari, A (i), podem representar els índexs d’altres nodes com es mostra a continuació.

A ((i-1) / 2)Representa el node pare
L’accés és més ràpid.Més lent que la pila.
A ((2 * i) +1)Representa el node fill esquerre
A ((2 * i) +2)Representa el node secundari adequat

Penseu en el següent munt binari:

munt binari

La representació en matriu del munt binari mínim anterior és la següent:

representació de matriu - Min Binary Heap

Com es mostra més amunt, el munt es travessa segons el fitxer ordre de nivell és a dir, els elements es recorren d’esquerra a dreta a cada nivell. Quan s’esgoten els elements d’un nivell, passem al següent nivell.

A continuació, implementarem el muntatge binari a Java.

El programa següent mostra el muntatge binari a Java.

import java.util.*; class BinaryHeap { private static final int d= 2; private int() heap; private int heapSize; //BinaryHeap constructor with default size public BinaryHeap(int capacity){ heapSize = 0; heap = new int( capacity+1); Arrays.fill(heap, -1); } //is heap empty? public boolean isEmpty(){ return heapSize==0; } //is heap full? public boolean isFull(){ return heapSize == heap.length; } //return parent private int parent(int i){ return (i-1)/d; } //return kth child private int kthChild(int i,int k){ return d*i +k; } //insert new element into the heap public void insert(int x){ if(isFull()) throw new NoSuchElementException('Heap is full, No space to insert new element'); heap(heapSize++) = x; heapifyUp(heapSize-1); } //delete an element from the heap at given position public int delete(int x){ if(isEmpty()) throw new NoSuchElementException('Heap is empty, No element to delete'); int key = heap(x); heap(x) = heap(heapSize -1); heapSize--; heapifyDown(x); return key; } //maintain heap property during insertion private void heapifyUp(int i) { int temp = heap(i); while(i>0 && temp > heap(parent(i))){ heap(i) = heap(parent(i)); i = parent(i); } heap(i) = temp; } //maintain heap property during deletion private void heapifyDown(int i){ int child; int temp = heap(i); while(kthChild(i, 1) heap(rightChild)?leftChild:rightChild; } //print the heap public void printHeap() { System.out.print('nHeap = '); for (int i = 0; i

Sortida:

nHeap = 7 4 6 1 3 2 5

Heap mínim a Java

Un min-heap a Java és un arbre binari complet. A min-heap, el node arrel és més petit que tots els altres nodes del heap. En general, el valor clau de cada node intern és menor o igual que els seus nodes fills.

Pel que fa a la representació de matriu de min-heap, si un node s’emmagatzema a la posició ‘i’, el node fill esquerre s’emmagatzema a la posició 2i + 1 i el node fill dret a la posició 2i + 2. La posició (i-1) / 2 retorna el node pare.

A continuació es detallen les diverses operacions admeses per min-heap.

# 1) Insereix (): Inicialment, s’afegeix una nova clau al final de l’arbre. Si la clau és més gran que el seu node pare, es mantindrà la propietat de l'emmagatzematge dinàmic. En cas contrari, hem de recórrer la clau cap amunt per complir la propietat de l'emmagatzematge dinàmic. L'operació d'inserció a l'emmagatzematge dinàmic mínim requereix temps O (registre n).

# 2) extractMin (): Aquesta operació elimina l'element mínim del munt. Tingueu en compte que la propietat de l'emmagatzematge dinàmic s'ha de mantenir després d'eliminar l'element arrel (element mínim) de l'emmagatzematge dinàmic. Tota aquesta operació pren O (Logn).

# 3) getMin (): getMin () retorna l'arrel del munt que també és l'element mínim. Aquesta operació es fa en temps O (1).

A continuació es mostra un arbre d'exemple per a un Min-heap.

Exemple de Min-heap

El diagrama anterior mostra un arbre min-heap. Veiem que l’arrel de l’arbre és l’element mínim de l’arbre. Com que l'arrel es troba a la ubicació 0, el seu fill esquerre es troba a 2 * 0 + 1 = 1 i el fill dret a 2 * 0 + 2 = 2.

Algorisme de Heap mínim

A continuació es mostra l'algorisme per construir un min-heap.

procedure build_minheap Array Arr: of size N => array of elements { repeat for (i = N/2 ; i >= 1 ; i--) call procedure min_heapify (A, i); } procedure min_heapify (var A( ) , var i, var N) { var left = 2*i; var right = 2*i+1; var smallest; if(left <= N and A(left) < A( i ) ) smallest = left; else smallest = i; if(right <= N and A(right) < A(smallest) ) smallest = right; if(smallest != i) { swap A( i ) and A( smallest )); call min_heapify (A, smallest,N); } }

Implementació Min Heap a Java

Podem implementar el min-heap mitjançant matrius o cues de prioritat. La implementació de min-heap mitjançant cues de prioritat és la implementació predeterminada, ja que una cua de prioritat s’implementa com a min-heap.

El següent programa Java implementa el min-heap mitjançant Arrays. Aquí fem servir la representació de matriu per a l'emmagatzematge dinàmic i, a continuació, apliquem la funció heapify per mantenir la propietat de l'emmagatzematge dinàmic de cada element afegit a l'emmagatzematge dinàmic. Finalment, mostrem el munt.

class Min_Heap { private int() HeapArray; private int size; private int maxsize; private static final int FRONT = 1; //constructor to initialize the HeapArray public Min_Heap(int maxsize) { this.maxsize = maxsize; this.size = 0; HeapArray = new int(this.maxsize + 1); HeapArray(0) = Integer.MIN_VALUE; } // returns parent position for the node private int parent(int pos) { return pos / 2; } // returns the position of left child private int leftChild(int pos) { return (2 * pos); } // returns the position of right child private int rightChild(int pos) { return (2 * pos) + 1; } // checks if the node is a leaf node private boolean isLeaf(int pos) { if (pos >= (size / 2) && pos HeapArray(leftChild(pos)) || HeapArray(pos) > HeapArray(rightChild(pos))) { // swap with left child and then heapify the left child if (HeapArray(leftChild(pos)) = maxsize) { return; } HeapArray(++size) = element; int current = size; while (HeapArray(current) = 1; pos--) { minHeapify(pos); } } // remove and return the heap elment public int remove() { int popped = HeapArray(FRONT); HeapArray(FRONT) = HeapArray(size--); minHeapify(FRONT); return popped; } } class Main{ public static void main(String() arg) { //construct a min heap from given data System.out.println('The Min Heap is '); Min_Heap minHeap = new Min_Heap(7); minHeap.insert(12); minHeap.insert(15); minHeap.insert(30); minHeap.insert(40); minHeap.insert(50); minHeap.insert(90); minHeap.insert(45); minHeap.minHeap(); //display the min heap contents minHeap.display(); //display root node of the min heap System.out.println('The Min val(root node):' + minHeap.remove()); } }

Sortida:

Implementació Min Heap a Java

Heap màxim a Java

Un munt màxim és també un arbre binari complet. En un munt màxim, el node arrel és superior o igual als nodes fills. En general, el valor de qualsevol node intern en un munt màxim és superior o igual als seus nodes fills.

Tot i que l’emmagatzematge dinàmic màxim s’assigna a una matriu, si algun node s’emmagatzema a la posició ‘i’, el fill esquerre es troba emmagatzemat a 2i +1 i el fill dret a 2i + 2.

El Max-heap típic es mostrarà com es mostra a continuació:

Heap màxim a Java

Al diagrama anterior, veiem que el node arrel és el més gran de la pila i que els seus nodes fills tenen valors més petits que el node arrel.

De manera similar al min-heap, el heap màxim també es pot representar com una matriu.

Per tant, si A és una matriu que representa l'emmagatzematge màxim, A (0) és el node arrel. De la mateixa manera, si A (i) és qualsevol node del munt màxim, els següents són els altres nodes adjacents que es poden representar mitjançant una matriu.

  • A ((i-1) / 2) representa el node pare d'A (i).
  • A ((2i +1)) representa el node fill esquerre d'A (i).
  • A (2i + 2) retorna el node secundari dret d'A (i).

A continuació es detallen les operacions que es poden realitzar a la pila màxima.

# 1) Insereix: L'operació d'inserció insereix un valor nou a l'arbre d'emmagatzematge màxim. S'insereix al final de l'arbre. Si la nova clau (valor) és més petita que el seu node pare, es mantindrà la propietat de l'emmagatzematge dinàmic. En cas contrari, l’arbre s’ha de muntar per mantenir la propietat del munt.

convertir YouTube a mp3 durant més de 30 minuts

La complexitat temporal de l'operació d'inserció és O (registre n).

# 2) ExtractMax: L'operació ExtractMax elimina l'element màxim (arrel) del munt màxim. L'operació també amuntega el munt màxim per mantenir la propietat del munt. La complexitat temporal d'aquesta operació és O (log n).

# 3) getMax: L'operació getMax retorna el node arrel del munt màxim amb la complexitat temporal d'O (1).

El programa Java següent implementa l'emmagatzematge dinàmic màxim. Utilitzem ArrayList aquí per representar els elements de pila màxima.

import java.util.ArrayList; class Heap { void heapify(ArrayList hT, int i) { int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) { int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); } } void insert(ArrayList hT, int newNum) { int size = hT.size(); if (size == 0) { hT.add(newNum); } else { hT.add(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } void deleteNode(ArrayList hT, int num) { int size = hT.size(); int i; for (i = 0; i = 0; j--) { heapify(hT, j); } } void printArray(ArrayList array, int size) { for (Integer i : array) { System.out.print(i + ' '); } System.out.println(); } } class Main{ public static void main(String args()) { ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println('Max-Heap array: '); h.printArray(array, size); h.deleteNode(array, 4); System.out.println('After deleting an element: '); h.printArray(array, size); } }

Sortida:

SORTIDA: màxim Heap a Java

Empilament mínim de cua de prioritat a Java

L'estructura de dades de la cua prioritària a Java es pot utilitzar directament per representar el min-heap. Per defecte, la cua de prioritat implementa min-heap.

El programa següent mostra el min-heap a Java mitjançant la cua de prioritat.

import java.util.*; class Main { public static void main(String args()) { // Create priority queue object PriorityQueue pQueue_heap = new PriorityQueue(); // Add elements to the pQueue_heap using add() pQueue_heap.add(100); pQueue_heap.add(30); pQueue_heap.add(20); pQueue_heap.add(40); // Print the head (root node of min heap) using peek method System.out.println('Head (root node of min heap):' + pQueue_heap.peek()); // Print min heap represented using PriorityQueue System.out.println(' Min heap as a PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // remove head (root of min heap) using poll method pQueue_heap.poll(); System.out.println(' Min heap after removing root node:'); //print the min heap again Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } }

Sortida:

SORTIDA - Prioritari de cua mínima a Java

Prioritari de la cua Heap màxim a Java

Per representar l’emmagatzematge màxim a Java mitjançant la cua de prioritat, hem d’utilitzar Collections.reverseOrder per invertir l’emmagatzematge mínim. La cua de prioritat representa directament un min-heap a Java.

Hem implementat Max Heap mitjançant una cua de prioritat al programa següent.

import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue //with Collections.reverseOrder to represent max heap PriorityQueue pQueue_heap = new PriorityQueue(Collections.reverseOrder()); // Add items to the pQueue using add() pQueue_heap.add(10); pQueue_heap.add(90); pQueue_heap.add(20); pQueue_heap.add(40); // Printing all elements of max heap System.out.println('The max heap represented as PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // Print the highest priority element (root of max heap) System.out.println(' Head value (root node of max heap):' + pQueue_heap.peek()); // remove head (root node of max heap) with poll method pQueue_heap.poll(); //print the max heap again System.out.println(' Max heap after removing root: '); Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } }

Sortida:

Cua de prioritat màxima de Heap

Ordena en pila a Java

L’ordenació en pila és una tècnica de classificació de comparació similar a la de selecció, en la qual seleccionem un element màxim de la matriu per a cada iteració. L'ordenació en pila fa ús de l'estructura de dades de l'emmagatzematge dinàmic i ordena els elements creant una pila mínima o màxima dels elements de la matriu que s'ordenaran.

Ja hem comentat que, a la pila mínima i màxima, el node arrel conté l'element mínim i màxim respectivament de la matriu. En l'ordenació de pila, l'element arrel del pila (mínim o màxim) s'elimina i es mou a la matriu ordenada. La pila restant es acumula per mantenir la propietat de pila.

Per tant, hem de realitzar dos passos de manera recursiva per ordenar la matriu donada mitjançant una classificació en pila.

  • Construïu un munt a partir de la matriu donada.
  • Traieu repetidament l'element arrel del munt i moveu-lo a la matriu ordenada. Amuntegeu el munt restant.

La complexitat temporal del tipus Heap és O (n log n) en tots els casos. La complexitat de l’espai és O (1).

Algorisme d'ordenació en pila a Java

A continuació es detallen els algoritmes d’ordenació de pila per ordenar la matriu donada en ordre ascendent i descendent.

# 1) Algorisme d'ordenació en pila per ordenar en ordre ascendent:

  • Creeu un munt màxim per ordenar la matriu donada.
  • Suprimiu l'arrel (valor màxim a la matriu d'entrada) i moveu-la a la matriu ordenada. Col·loqueu l'últim element a la matriu a l'arrel.
  • Heapify la nova arrel del heap.
  • Repetiu els passos 1 i 2 fins que tota la matriu estigui ordenada.

# 2) Algorisme d'ordenació en pila per ordenar en ordre descendent:

  • Construeix un Heap mínim per a la matriu donada.
  • Traieu l'arrel (valor mínim a la matriu) i canvieu-la amb l'últim element de la matriu.
  • Heapify la nova arrel del heap.
  • Repetiu els passos 1 i 2 fins que tota la matriu estigui ordenada.

Implementació d'ordenació en pila a Java

El programa Java següent utilitza una classificació per muntatge per ordenar una matriu en ordre ascendent. Per a això, primer construïm un munt màxim i, a continuació, intercanviem recursivament i amuntegem l'element arrel tal com s'especifica a l'algorisme anterior.

import java.util.*; class HeapSort{ public void heap_sort(int heap_Array()) { int heap_len = heap_Array.length; // construct max heap for (int i = heap_len / 2 - 1; i >= 0; i--) { heapify(heap_Array, heap_len, i); } // Heap sort for (int i = heap_len - 1; i >= 0; i--) { int temp = heap_Array(0); heap_Array(0) = heap_Array(i); heap_Array(i) = temp; // Heapify root element heapify(heap_Array, i, 0); } } void heapify(int heap_Array(), int n, int i) { // find largest value int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left heap_Array(largest)) largest = left; if (right heap_Array(largest)) largest = right; // recursively heapify and swap if root is not the largest if (largest != i) { int swap = heap_Array(i); heap_Array(i) = heap_Array(largest); heap_Array(largest) = swap; heapify(heap_Array, n, largest); } } } class Main{ public static void main(String args()) { //define input array and print it int heap_Array() = {6,2,9,4,10,15,1,13}; System.out.println('Input Array:' + Arrays.toString(heap_Array)); //call HeapSort method for given array HeapSort hs = new HeapSort(); hs.heap_sort(heap_Array); //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(heap_Array)); } }

Sortida:

sortida - Implementació de la classificació en pila a Java

La complexitat temporal global de la tècnica d’ordenació en pila és O (nlogn). La complexitat temporal de la tècnica heapify és O (logn). Tot i que la complexitat temporal de la construcció del munt és O (n).

Stack Vs Heap a Java

Ara tabulem algunes de les diferències entre una estructura de dades de pila i un munt.

PilaMunt
Una pila és una estructura de dades lineal.Un munt és una estructura de dades jeràrquica.
Segueix la comanda LIFO (Last In, First Out).La travessia està en ordre de nivell.
S'utilitza principalment per a l'assignació de memòria estàtica.S’utilitza per a l’assignació de memòria dinàmica.
La memòria s’assigna de manera contigua.La memòria s’assigna en ubicacions aleatòries.
La mida de la pila és limitada segons el sistema operatiu.El sistema operatiu no aplica cap límit de mida de l'emmagatzematge dinàmic.
Stack només té accés a variables locals.Heap té assignades variables globals.
L’assignació / desassignació de memòria és automàtica.El programador ha de fer l'assignació / desassignació manualment.
La pila es pot implementar utilitzant Arrays, Linked List, ArrayList, etc. o qualsevol altra estructura de dades lineal.Heap s’implementa mitjançant matrius o arbres.
Cost de manteniment si és inferior.Més costós de mantenir.
Pot provocar una manca de memòria, ja que la memòria és limitada.No hi ha escassetat de memòria, però pot patir una fragmentació de la memòria.

Preguntes freqüents

P # 1) La pila és més ràpida que Heap?

Resposta: Una pila és més ràpida que la pila, ja que l'accés és lineal a la pila en comparació amb la pila.

P # 2) Per a què serveix un Heap?

Resposta: L’emmagatzematge dinàmic s’utilitza principalment en algoritmes que troben el camí mínim o el més curt entre dos punts, com l’algorisme de Dijkstra, per ordenar mitjançant un ordre d’emmagatzematge dinàmic, per a implementacions de cues prioritàries (min-muntatge), etc.

P # 3) Què és un Heap? Quins són els seus tipus?

Resposta: Un munt és una estructura de dades jeràrquica basada en arbres. Un munt és un arbre binari complet. Els munts són de dos tipus, és a dir, heap màxim en què el node arrel és el més gran de tots els nodes; Muntatge mínim en què el node arrel és el més petit o mínim de totes les claus.

Q # 4) Quins avantatges té Heap sobre una pila?

Resposta: L'avantatge principal de l'emmagatzematge dinàmic sobre la pila està en l'emmagatzematge dinàmic, la memòria s'assigna dinàmicament i, per tant, no hi ha límit quant a la quantitat de memòria que es pot utilitzar. En segon lloc, només es poden assignar variables locals a la pila, mentre que també podem assignar variables globals al munt.

P # 5) Heap pot tenir duplicats?

Resposta: Sí, no hi ha restriccions per tenir nodes amb claus duplicades a l'emmagatzematge dinàmic, ja que aquest és un arbre binari complet i no compleix les propietats de l'arbre de cerca binari.

Conclusió

En aquest tutorial, hem parlat dels tipus d'emmagatzematge d'emmagatzematge i d'emmagatzematge d'emmagatzematge amb tipus d'emmagatzematge. També hem vist la implementació detallada dels seus tipus a Java.

=> Consulteu la guia de formació Java perfecta aquí.

Lectura recomanada

^