Högar är utmärkta datastrukturer för att effektivt hantera och manipulera data när du behöver upprepade gånger hitta det minsta eller maximala elementet. I Java ger klassen "PriorityQueue" en hög implementering (min-heap som standard). Så här kan du effektivt använda högar för att hantera och manipulera stora datasätt:
1. Förstå grunderna
* Heap Egendom: En hög upprätthåller en specifik ordning. I en min-heap är modernodens nyckel alltid mindre än eller lika med sina barns nycklar. I maxime-heap är modernodens nyckel alltid större än eller lika med sina barns nycklar.
* `priorityqueue` i Java: "PriorityQueue` implementerar en min-heap som standard. Du kan anpassa den för att vara en max-heap med en anpassad "komparator".
* Tidskomplexitet:
* `Lägg till (element)`:o (log n) i genomsnitt (där n är antalet element i högen)
* `ta bort ()` (tar bort roten, min eller max):o (log n)
* `peek ()` (returnerar roten):o (1)
* `innehåller (element)`:o (n) i värsta fall. Högar är * inte * effektiva för att söka efter godtyckliga element.
* Bygga en hög från en matris:o (n)
2. Kärntekniker och användningsfall
* Hitta de minsta/största elementen: Detta är en klassisk högapplikation.
* k minsta:
1. Skapa en max-heap av storlek `k` från de första` k` elementen i ditt datasätt.
2. Iterera genom de återstående elementen. Om ett element är mindre än roten till max-heap, ta bort roten och sätt in det nya elementet.
3. Efter bearbetning av alla element kommer Max-heap att innehålla de "k" minsta elementen.
* K Största:
1. Skapa en min-heap av storlek `K` från de första` K`-elementen i ditt datasätt.
2. Iterera genom de återstående elementen. Om ett element är större än roten till min-heap, ta bort roten och sätt in det nya elementet.
3. Efter bearbetning av alla element kommer min-heap att innehålla de "K" största elementen.
`` `Java
import java.util.priorityqueue;
import java.util.comParator;
import java.util.list;
import java.util.arrayList;
public class Heapexamples {
offentlig statisk lista findKlLargest (int [] nums, int k) {
PriorityQueue minheap =new PriorityQueue <> (); // min-heap som standard
för (int num:nums) {
if (minheap.size ()
minheap.add (num);
} annars om (num> minheap.peek ()) {
minheap.poll (); // ta bort den minsta
minheap.add (num); // Lägg till det nya, större elementet
}
}
// Konvertera högen till en lista (valfritt, för specifik beställning)
Lista KLargest =new ArrayList <> (minheap);
klargest.sort (Comparator.reverseOrder ()); // sortera fallande för största till minsta
returnera Klargest;
}
offentlig statisk lista findksmallest (int [] nums, int k) {
PriorityQueue maxHeap =new PriorityQueue <> (Comparator.reverseOrder ()); // max-heap
för (int num:nums) {
if (maxHeap.size ()
maxheap.add (num);
} annars om (num
maxHeap.poll (); // ta bort den största
maxheap.add (num); // lägg till det nya, mindre elementet
}
}
// Konvertera högen till en lista (valfritt, för specifik beställning)
Lista ksmallest =ny ArrayList <> (MaxHeap);
ksmallest.sort (comparator.naturalorder ()); // sortera stigande för minsta till största
return Ksmallest;
}
public static void main (String [] args) {
int [] data ={5, 2, 9, 1, 5, 6};
int k =3;
Lista största =findKLargest (data, k);
System.out.println ("K största:" + största); // Utgång:K Största:[9, 6, 5]
Listan minsta =findksmallest (data, k);
System.out.println ("K minsta:" + minsta); // utgång:k minsta:[1, 2, 5]
}
}
`` `
* sammanslagning k sorterade listor:
1. Skapa en min-heap för att lagra det första elementet från varje lista. Varje element i högen ska lagra värdet * och * indexet för listan den kom från.
2. Ta upp minsta elementet upprepade gånger. Detta är nästa element i den sammanslagna sorterade listan.
3. Om listan från vilken det borttagna elementet kom har fler element, lägg till nästa element från den listan till högen.
4. Fortsätt tills högen är tom.
`` `Java
import java.util.priorityqueue;
import java.util.list;
import java.util.arrayList;
public class MergesortedLists {
Privat statisk klassnod implementerar jämförbar {
int värde;
int ListIndex;
int elementIndex;
public node (int värde, int listIndex, int elementIndex) {
this.value =värde;
this.listindex =ListIndex;
this.elementIndex =elementIndex;
}
@Åsidosätta
public int Compareto (Node Other) {
returnera heltal.
}
}
Offentlig statisk lista MergeksortedLists (lista > listor) {
List MergedList =new ArrayList <> ();
PriorityQueue minheap =new PriorityQueue <> ();
// Lägg till det första elementet från varje lista till högen
för (int i =0; i
if (! list.get (i) .isEmpty ()) {
minheap.add (ny nod (listor.get (i) .get (0), i, 0));
}
}
medan (! minheap.isEmpty ()) {
Nodström =minheap.poll ();
MergedList.Add (Current.Value);
int listIndex =current.listindex;
int elementIndex =current.elementIndex;
// lägg till nästa element från samma lista om det finns
if (elementIndex + 1
minheap.add (ny nod (listor.get (ListIndex) .get (elementIndex + 1), ListIndex, ElementIndex + 1));
}
}
Return MergedList;
}
public static void main (String [] args) {
Lista > listor =ny ArrayList <> ();
listor.add (list.of (1, 4, 7));
listor.add (list.of (2, 5, 8));
listor.add (list.of (3, 6, 9));
Lista sammanslagd =MergeksortedLists (listor);
System.out.println ("Merged List:" + Merged); // utgång:sammanslagd lista:[1, 2, 3, 4, 5, 6, 7, 8, 9]
}
}
`` `
* Prioritetskönsapplikationer:
* Uppgiftsplanering: Prioritera uppgifter baserade på brådskande och utföra dem i ordning.
* grafalgoritmer (dijkstra, a*): Förvara noder som ska besökas baserat på deras uppskattade avstånd från källan.
* Eventsimulering: Processhändelser i kronologisk ordning.
3. Viktiga överväganden för stora data
* Minneshantering: Om ditt datasätt är * extremt * stort och inte passar i minnet, överväg:
* Extern sortering (sammanslagningssortering med högar): Dela upp uppgifterna i mindre bitar som passar i minnet, sortera varje bit (med högar eller andra metoder) och slå sedan samman de sorterade bitarna med en hög. Detta innebär att läsa och skriva data till disken.
* Streamingalgoritmer: Algoritmer utformade för att bearbeta data i ett enda pass, vilket minimerar minnesanvändningen. Även om en ren hög kanske inte är lämplig för strömning i alla fall, kan du använda tekniker som reservoarprovtagning i samband med högar.
* Anpassad komparator: För komplexa objekt, implementera en "komparator" som definierar hur dina objekt ska jämföras i högen.
* sopor samling: Stora högar kan sätta press på skräpsamlaren. Tänk på att skapa objekt och bortskaffa för att undvika flaskhalsar för prestanda.
* Profilering: Använd profilverktyg för att identifiera prestationshotspots i din kod. Detta kan hjälpa dig att avgöra om högoperationer är flaskhalsen och om du behöver optimera dem ytterligare.
* primitiva typer (när det är möjligt): Om du arbetar med primitiva typer (t.ex. `int`,` dubbel`), kan du överväga att använda en `int []` eller `dubbel []` som den underliggande lagringen för din hög, snarare än `heltal eller` dubbel` objekt. Detta kan minska minneskostnaden och förbättra prestandan. Du skulle sedan implementera Heap -logiken själv (med hjälp av arrayindex). Detta är endast nödvändigt i extremt prestationskänsliga scenarier.
* Fördelningen: Om du känner till den ungefärliga maximala storleken på din hög i förväg, förbehåller dig "priorityqueue" med den kapaciteten. Detta kan förhindra att storleken på operationer kan vara kostsamma.
Exempel:Prioritering av loggposter
Föreställ dig att du bearbetar en stor loggfil och måste extrahera de mest kritiska loggposter baserat på en svårighetsgrad.
`` `Java
import java.util.priorityqueue;
import java.util.comParator;
import java.util.list;
import java.util.arrayList;
klass logentry {
Strängmeddelande;
int svårighetsgrad;
public logentry (strängmeddelande, int svårighetsgrad) {
this.message =meddelande;
this.severity =svårighetsgrad;
}
@Åsidosätta
public String toString () {
returnera "logentry {" +
"Meddelande ='" + meddelande +' \ '' +
", svårighetsgrad =" + svårighetsgrad +
'}';
}
}
public class Loganalyzer {
offentlig statisk lista findmostkritisk (lista loggar, int n) {
PriorityQueue minheap =new PriorityQueue <> (Comparator.comParingInt (Logentry ::GetSeverity));
för (logentry log:loggar) {
if (minheap.size ()
minheap.add (log);
} annars om (log.getSeverity ()> minheap.peek (). getSeverity ()) {
minheap.poll ();
minheap.add (log);
}
}
Lista Criticallogs =ny ArrayList <> (minheap);
criticallogs.sort (comparator.comParingInt (logentry ::getSeverity) .reversed ());
Return Criticallogs;
}
public static void main (String [] args) {
Lista loggar =ny ArrayList <> ();
Logs.Add (ny logentry ("Lågprioritetsfel", 1));
Logs.Add (ny logentry ("Medium Priority Warning", 5));
Logs.Add (ny logentry ("Critical Error - System Crash", 10));
Logs.Add (ny logentry ("En annan händelse med låg prioritet", 2));
Logs.Add (ny logentry ("Högprioritetsnätverksproblem", 8));
Logs.Add (ny logentry ("Medium Priority Database Problem", 6));
int n =3;
Lista Critical =FindestCritical (loggar, n);
System.out.println ("Mest kritiska loggar:" + kritiska);
// Output:De flesta kritiska loggar:[Logentry {Message ='Critical Error - System Crash', svårighetsgrad =10}, logentry {Message ='Högprioritetsnätverksproblem', svårighetsgrad =8}, logentry {meddelande ='Medium prioriterad databasproblem', svårighetsgrad =6}]
}
}
`` `
Sammanfattningsvis:
Högar är kraftfulla för att hitta extrema värden (min/max) och prioritera element i ett datasätt. När du hanterar stora mängder data, tänk på minnesanvändning, överväg externa sorteringstekniker om det behövs och profilera din kod för att identifiera och adressera prestanda flaskhalsar. Klassen "PriorityQueue" i Java är en bekväm utgångspunkt, men du kan behöva anpassa den eller implementera din egen Heap -logik för specifika användningsfall och minnesbegränsningar.
