| Bij het implementeren van een array-gebaseerde heap in Java wordt een array gebruikt om de heap-structuur weer te geven. We gebruiken een min-heap als voorbeeld (het kleinste element in de root), maar de principes zijn hetzelfde voor een max-heap.
Hier is een Java-implementatie van een min-heap, inclusief methoden voor het invoegen, extraheren van het minimumelement en heapify-bewerkingen:
```java
openbare klasse MinHeap {
privé int[] heap;
privé int-grootte;
particuliere int-capaciteit;
openbare MinHeap(int-capaciteit) {
deze.capaciteit =capaciteit;
this.heap =nieuwe int[capaciteit + 1]; // Index 0 wordt niet gebruikt
deze.grootte =0;
}
openbare boolean isEmpty() {
retourgrootte ==0;
}
publieke booleaanse waarde isFull() {
retourgrootte ==capaciteit;
}
privé int ouder(int i) {
retour i / 2;
}
privé int links(int i) {
retour 2 * ik;
}
privé int rechts(int i) {
retour 2 * ik + 1;
}
private void swap(int i, int j) {
int temp =heap[i];
hoop[i] =hoop[j];
hoop[j] =temperatuur;
}
openbare ongeldige invoeging (int-sleutel) {
als (isVol()) {
throw new IllegalStateException("Heap is vol");
}
maat++;
heap[grootte] =sleutel;
int i =grootte;
while (i> 1 &&heap[parent(i)]> heap[i]) {// Min-heap eigenschap
swap(i, ouder(i));
ik =ouder(i);
}
}
openbare int extractMin() {
als (isLeeg()) {
throw new IllegalStateException("Heap is leeg");
}
int root =heap[1];
heap[1] =heap[grootte];
maat--;
ophopen(1);
retourwortel;
}
privé leegte heapify(int i) {
int kleinste =i;
int l =links(i);
int r =rechts(i);
if (l <=grootte &&hoop[l]
kleinste =l;
}
if (r <=grootte &&heap[r]
kleinste =r;
}
als (kleinste!=i) {
swap(i, kleinste);
ophopen(kleinste);
}
}
openbare leegte printHeap() {
voor (int i =1; i <=grootte; i++) {
Systeem.uit.print(heap[i] + " ");
}
Systeem.out.println();
}
public static void main(String[] args) {
MinHeap minHeap =nieuwe MinHeap(10);
minHeap.insert(3);
minHeap.insert(2);
minHeap.insert(15);
minHeap.insert(5);
minHeap.insert(4);
minHeap.insert(45);
System.out.println("MinHeap-array:");
minHeap.printHeap();
System.out.println("Min uitpakken:" + minHeap.extractMin());
System.out.println("Na het uitpakken van min:");
minHeap.printHeap();
}
}
```
Deze code omvat:
* Constructeur: Initialiseert de heap-array met een bepaalde capaciteit. Merk op dat index 0 niet wordt gebruikt.
* `isEmpty()` en `isFull()`: Controleer de staat van de heap.
* `parent()`, `left()`, `right()`: Helperfuncties om de indices van bovenliggende en onderliggende knooppunten op te halen.
* `swap()`: Verwisselt twee elementen in de array.
* `insert()`: Voegt een nieuw element in de heap in, waarbij de eigenschap min-heap behouden blijft.
* `extractMin()`: Verwijdert en retourneert het minimumelement (root), waarbij de eigenschap min-heap behouden blijft met behulp van `heapify()`.
* `heapify()`: Herstelt de eigenschap min-heap nadat een element is verwijderd of ingevoegd. Het vergelijkt recursief een element met zijn kinderen en wisselt indien nodig.
* `printHeap()`: Een helperfunctie voor demonstratie.
Vergeet niet om met mogelijke uitzonderingen om te gaan, zoals proberen uit een lege heap te extraheren of in een volle heap in te voegen. In dit voorbeeld worden gehele waarden gebruikt; u kunt het eenvoudig aanpassen aan andere gegevenstypen door een generieke typeparameter te gebruiken. Voor grotere stapels kunt u overwegen een meer geavanceerde strategie voor het wijzigen van de grootte te gebruiken om de beperking van de vaste capaciteit te vermijden. |
