Implementering av en matrisbaserad hög (min-heap i detta exempel) i Java innebär att använda en enda matris för att representera högstrukturen. Så här kan du göra det, inklusive metoder för införande, borttagning (extraktion av det minsta elementet) och Peek (få det minsta elementet utan att ta bort det):
`` `Java
public class ArrayHeap {
privat int [] hög;
privat int -storlek;
privat int kapacitet;
public arrayHeap (int -kapacitet) {
this.capacity =kapacitet;
this.heap =ny int [kapacitet + 1]; // Index 0 används inte
this.size =0;
}
// Helper -funktion för att få moderindex
privat int förälder (int i) {
return i / 2;
}
// Helper -funktion för att få vänster barnindex
privat int vänster (int i) {
return 2 * i;
}
// Helper -funktion för att få rätt barnindex
privat int rätt (int i) {
return 2 * i + 1;
}
// Helper Function för att Heapify Up efter insättning
privat tomrum heapifyup (int i) {
medan (i> 1 &&heap [förälder (i)]> heap [i]) {
Swap (i, förälder (i));
i =förälder (i);
}
}
// Helper Function för att Heapify Down efter radering
privat tomrum heapifydown (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);
heapifydown (minsta);
}
}
// Hjälperfunktion för att byta två element
privat tomrumsswap (int i, int j) {
int temp =heap [i];
heap [i] =heap [j];
hög [j] =temp;
}
// sätt in ett nytt element i högen
public void Insert (int key) {
if (storlek ==kapacitet) {
Kasta ny illegalstateException ("Heap är full");
}
storlek ++;
hög [storlek] =nyckel;
heapifyup (storlek);
}
// extrahera (och ta bort) det minsta elementet
public int ExtractMin () {
if (size ==0) {
Kasta ny illegalStateException ("Heap är tom");
}
int min =heap [1];
hög [1] =hög [storlek];
storlek--;
heapifydown (1);
return min;
}
// Få minsta element utan att ta bort det
public int Peekmin () {
if (size ==0) {
Kasta ny illegalStateException ("Heap är tom");
}
returnera högen [1];
}
// Kontrollera om högen är tom
public boolean isEmpty () {
returstorlek ==0;
}
public static void main (String [] args) {
ArrayHeap Heap =new ArrayHeap (10);
heap.insert (10);
Heap.Insert (5);
Heap.Insert (15);
Heap.Insert (3);
Heap.Insert (8);
System.out.println ("Minsta element:" + heap.peekmin ()); // utgång:3
System.out.println ("Extraherad minimielement:" + heap.extractMin ()); // utgång:3
System.out.println ("Nytt minimielement:" + heap.peekmin ()); // utgång:5
}
}
`` `
Denna implementering ger grundläggande högverksamhet. Kom ihåg att detta är en *min-heap *; För att göra det till en *max-heap *, måste du vända jämförelselogiken i `heapifyup` och` heapifydown '. För större högar, överväg att använda en mer sofistikerad datastruktur eller bibliotek om prestanda blir kritisk. Du kan också utöka detta för att hantera generiska för mer mångsidiga datatyper. Kom ihåg att hantera potentiella undantag som "illegalStateException" för tomma eller fulla högar.
