Implementering av en matrisbaserad hög i Java innebär att använda en matris för att representera högstrukturen. Vi använder ett min-heap som ett exempel (det minsta elementet vid roten), men principerna är desamma för en max-heap.
Här är en Java-implementering av en min-heap, inklusive metoder för införande, extraktion av minsta element och heapify-operationer:
`` `Java
offentlig klass minheap {
privat int [] hög;
privat int -storlek;
privat int kapacitet;
public minheap (int -kapacitet) {
this.capacity =kapacitet;
this.heap =ny int [kapacitet + 1]; // Index 0 används inte
this.size =0;
}
public boolean isEmpty () {
returstorlek ==0;
}
public boolean isfull () {
returstorlek ==kapacitet;
}
privat int förälder (int i) {
return i / 2;
}
privat int vänster (int i) {
return 2 * i;
}
privat int rätt (int i) {
return 2 * i + 1;
}
privat tomrumsswap (int i, int j) {
int temp =heap [i];
heap [i] =heap [j];
hög [j] =temp;
}
public void Insert (int key) {
if (isfull ()) {
Kasta ny illegalstateException ("Heap är full");
}
storlek ++;
hög [storlek] =nyckel;
int i =storlek;
medan (i> 1 &&heap [förälder (i)]> heap [i]) {// min-heap egendom
Swap (i, förälder (i));
i =förälder (i);
}
}
public int ExtractMin () {
if (isEmpty ()) {
Kasta ny illegalStateException ("Heap är tom");
}
int root =heap [1];
hög [1] =hög [storlek];
storlek--;
heapify (1);
returnera roten;
}
privat tomrum heapify (int i) {
int minsta =i;
int l =vänster (i);
int r =höger (i);
if (l <=size &&heap [l]
minsta =l;
}
if (r <=size &&heap [r]
minsta =r;
}
if (minsta! =i) {
Swap (i, minsta);
Heapify (minsta);
}
}
public void PrintTheap () {
för (int i =1; i <=storlek; i ++) {
System.out.print (heap [i] + "");
}
System.out.println ();
}
public static void main (String [] args) {
MINHEAP MINHEAP =new 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 ("Extract Min:" + minheap.extractMin ());
System.out.println ("Efter extrahering av min:");
minheap.printheap ();
}
}
`` `
Den här koden innehåller:
* konstruktör: Initialiserar höguppsättningen med en given kapacitet. Observera att index 0 inte används.
* `isEmpty ()` och `isfull ()`: Kontrollera högstillståndet.
* `förälder ()`, `vänster ()`, `höger ()`: Helper fungerar för att få index för förälder- och barnnoder.
* `swap ()`: Byt två element i matrisen.
* `insert ()`: Sätter in ett nytt element i högen och underhåller min-heap-egenskapen.
* `ExtractMin ()`: Tar bort och returnerar det minsta elementet (rot) och underhåller den min-heap-egenskapen med `heapify ()`.
* `heapify ()`: Återställer egenskapen Min-Heap efter att ett element har tagits bort eller infogas. Det jämför ett element med sina barn och byts om det behövs.
* `PrintTheap ()`: En hjälpfunktion för demonstration.
Kom ihåg att hantera potentiella undantag, till exempel att försöka extrahera från en tom hög eller infoga i en fullständig. Detta exempel använder heltalsvärden; Du kan enkelt anpassa den till andra datatyper genom att använda en generisk typparameter. För större högar kan du överväga att använda en mer sofistikerad storleksstrategi för att undvika begränsning av fast kapacitet.
