A skew heap er en abstrakt datastruktur . Selv om Java ikke sørger for et binært tre klasse, kan den skjeve haug sees på som et selvorganiserende binært søketre . Java Skew Heap klassen implementerer Sammenlignbare grensesnittet så lister over SkewHeap gjenstander kan sorteres enkelt. Instruksjoner
en

Skriv skjelettet av SkewHeap klassen . Variabler av interesse er verdien ( nodens verdi) og venstre og høyre ( venstre og høyre barn ) . TMP og innrykk statiske variabler brukes til midlertidig plass i flettingen og skrive ut metoder. Konstruktøren initialiserer verdi og etterlater venstre og høyre som null " " public class SkewHeap implementerer Sammenlignbare { int verdi ; . SkewHeap venstre, høyre , statisk LinkedList tmp ; static int innrykk = 0; offentlig SkewHeap ( int val ) { value = val ; } } " "
2

Bruk compareTo metode som en måte å oppfylle Sammenlignbare grensesnitt og tillate lister over SkewHeap objekter som skal sorteres . CompareTo metoden skal returnere et negativt tall , null eller positivt tall , avhengig av hvordan de to objektene skal sorteres . Oppnå dette ved å utføre en subtraksjon på de to noder verdier slik at noder med mindre verdier er sortert før noder av større verdi " " public int compareTo ( SkewHeap h ) {return verdi - h.value ; } " . "

3

Komponer chop metoden, en viktig metode som brukes av flettingen . Når en fletting er utført , er begge hauger hakket hverandre ned høyre side . . Hogge metoden utfører det hogge og legger de resterende subheaps til tmp list " " public void chop ( ) { SkewHeap r = høyre , høyre = null; if ( r = null ! ) R.chop (); tmp.addLast ( dette) ; } " "
4

Lag flettingen metoden. Innsatsen og removeHead metoder både bruk fusjonere for å utføre sin oppgave . Flettingen metoden vil hogge begge masser som skal flettes , som lagrer alle de subheaps i tmp .
5

Oppnå sortere tmp lenket liste og kombinere subheaps ved å fjerne de siste to hauger fra listen. Legg en som høyre barn av den andre, bytte høyre og venstre barn og legge haugen tilbake til slutten av listen . På denne måten blir hakket subheaps sammen igjen til en enkelt balansert haug. Venstre noder er alltid garantert å være mindre enn de riktige noder , og underordnede noder har en større verdi enn foreldre noder " " offentlig SkewHeap merge ( SkewHeap h) { //Hakk nodene ned rett vei tmp = new LinkedList ( ) . ; hogge (); h.chop (); //Sorter nodene Collections.sort ( tmp ), //Flett subheaps while ( tmp.size ( ) > 1 ) { SkewHeap a = tmp.removeLast (); SkewHeap b = tmp.removeLast (); b.right = b.left ; b.left = a; tmp.addLast ( b ) ;} retur tmp.getFirst (); } " "
6

Skriv removeHead metoden. Dette vil fjerne hodet node og flette venstre og høyre barn hauger " " offentlig SkewHeap removeHead ( ) { if ( venstre == null && høyre == null ) return null; . Else if ( venstre == null ) return rett , ellers if ( høyre == null ) return venstre ; else return left.merge (til høyre ); } " "
7

Formuler print-metoden. Denne metoden er viktig for debugging , som debuggers ikke ofte har fasilitetene til å vise nestede datastrukturer som dette skew haug. Det er rekursiv og innrykk riktig " " public void print ( ) { for ( int i = 0; . Jeg System.out.println (verdi ) ; innrykk + +; if ( venstre = null ) { for ( int i = 0; ! Jeg System . out.println ( " left.print (); } if ( høyre = null) { for ( int i = 0 ; i System.out.println ( " - > "); right.print (); } innrykk - - ; } " "