En skævhed bunke er en abstrakt datastruktur. Selvom Java ikke giver mulighed for et binært træ klasse, kan skew heap være tænkt som et selvorganiserende binær søgning træ. Java Skew Heap klasse implementerer de sammenlignelige grænseflade, således lister over SkewHeap objekter kan sorteres nemt. Instruktioner
1

Skriv skelettet af den SkewHeap klasse. De variable af interesse er værdi ( node værdi ), og venstre og højre ( venstre og højre børn). De TMP og led statiske variabler anvendes til midlertidig plads i fletningen og udskrive metoder. Konstruktøren initialiserer værdi og efterlader venstre og højre som null "" public class SkewHeap implementerer Sammenlignelige { int værdi . SkewHeap venstre, højre , statisk LinketListe tmp , statisk int led = 0; offentlig SkewHeap ( int val ) { value = val ;} } ""
2

Brug compareTo metoden som en måde at opfylde de sammenlignelige grænseflade og tillade lister over SkewHeap objekter, der skal sorteres. Den compareTo Metoden skal returnere et negativt tal , nul eller positivt tal , afhængigt af hvordan de to objekter skal sorteres . Opnå dette ved at udføre en subtraktion på de to knudepunkter 'værdier , således at noder med mindre værdier sorteres før knudepunkter i større værdi "" offentlig int compareTo ( SkewHeap h) {return værdi - h.value ;} " . "

3

Komponer chop metoden , en vigtig metode anvendt af fletningen . Når en sammenfletning er udført , er begge dynger hakkede hinanden ned i højre side . . Chop metoden udfører denne chop og tilføjer de resterende subheaps til tmp listen "" public void chop () { SkewHeap r = højre , højre = null , hvis (r = null !) R.chop (); tmp.addLast ( dette) ;} ""
4

Opret sammenfletningen metoden. Indsatsen og removeHead metoder både brugen fusionere for at udføre deres opgaver. Sammenfletningsværktøjet metode vil hugge begge dynger at blive slået sammen, som gemmer alle de subheaps i tmp .
5.

Udføre sortere tmp linkede liste , og kombinere de subheaps ved at fjerne de sidste to dynger på listen. Tilsæt en som højre barn af den anden , bytte om på højre og venstre børn og tilsæt den bunke tilbage til slutningen af ​​listen . På denne måde bliver hakkede subheaps samles i en enkelt afbalanceret bunke . Venstre noder er altid garanteret at være mindre end de rigtige noder, og barn noder har en større værdi end forælder knuder " " offentlig SkewHeap merge ( SkewHeap h ) {//Hak noder ned den rigtige vej tmp = new LinkedList (). ; hugge (); h.chop () //Sort knudepunkterne Collections.sort ( tmp ) //Kombiner subheaps while ( tmp.size ( )> 1 ) { SkewHeap a = tmp.removeLast (); SkewHeap b = tmp.removeLast (); b.right = b.left , b.left = a; tmp.addLast ( b );} tilbagevenden tmp.getFirst ( );} ""
6

Skriv den removeHead metode . Dette vil fjerne hovedet node og flette venstre og højre barn dynger " " offentlig SkewHeap removeHead () { if ( venstre == null && højre == null ) return null ; . Else if ( venstre == null ) return ret , ellers hvis (højre == null ) return til venstre; ellers retur left.merge (til højre) ;} ""
7

Formulér print-metoden . Denne metode er vigtig for debugging, da debuggers ofte ikke har faciliteterne til at se indlejrede datastrukturer som denne skævhed bunke. Det er rekursive og led korrekt "" public void print ( ) { for (int i = 0; . Jeg System.out.println ( værdi) led + +; if ( venstre = null) { for (int i = 0; ! I System . out.println ( " left.print (); } if (højre = null) { for (int i = 0; i System.out.println ( " -> ") right.print ( );} led - - ;} ""