Schrijf het skelet van de SkewHeap klasse . De variabelen van belang zijn waarde ( waarde van het knooppunt ) en links en rechts ( links en rechts kinderen ) . De tmp en streepje statische variabelen worden gebruikt voor tijdelijke ruimte in het samenvoegen en afdrukken methoden . De constructor initialiseert waarde en laat links en rechts als van nul " " public class SkewHeap implementeert Vergelijkbaar { int waarde ; . SkewHeap links, rechts ; statische LinkedList tmp ; static int streepje = 0; openbare SkewHeap ( int val) { waarde = val ; } } " " kopen van 2

Gebruik de compareTo methode als een manier om de vergelijkbare interface van vervullen en laten lijsten van SkewHeap objecten te sorteren . De compareTo werkwijze geen negatief getal , nul of positief getal , afhankelijk van hoe de twee objecten worden gesorteerd terugkeren . Bereiken dit door het uitvoeren van een aftrekking op waarden die knooppunten met minder waarden worden gesorteerd voordat knooppunten van grotere waarde van de twee knooppunten ' " " public int compareTo ( SkewHeap h ) { return waarde - h.value ;} " . "

3

Stel de chop -methode , een belangrijke methode die wordt gebruikt door merge . Als het samenvoegen wordt uitgevoerd , worden beide hoopjes gehakt uit elkaar aan de rechterzijde . . De chop methode voert die chop en voegt de resterende subheaps om de tmp lijst " " public void chop ( ) { SkewHeap r = rechts , rechts = null; if ( r = null ! ) R.chop ( ) ; tmp.addLast ( this); } " "
4

Maak de merge -methode . De insert en removeHead methoden gebruiken beide samen te voegen om hun taak te volbrengen . Het samenvoegen methode zal hakken beiden hopen te worden samengevoegd , waarin alle van de subheaps opslaat in tmp .
5

Bereiken sorteren van de tmp gelinkte lijst en het combineren van de subheaps door het verwijderen van de laatste twee hopen uit de lijst . Voeg een als rechterkind van de andere Wissel de rechter en linker kinderen en voeg de hoop naar het einde van de lijst . Op deze wijze worden gesneden subheaps opnieuw samengesteld tot een evenwichtige heap. Linker knooppunten zijn altijd gegarandeerd tot minder dan de juiste knooppunten en onderliggende knooppunten hebben een grotere waarde dan bovenliggende knooppunten " " openbare SkewHeap merge ( SkewHeap h ) { //Hak de knopen onderaan de juiste weg tmp = new LinkedList ( ) . ; chop ( ) ; h.chop ( ) ; //Sorteer de knooppunten Collections.sort ( tmp ) ; //Voeg de subheaps terwijl ( tmp.size ( ) > 1 ) { SkewHeap a = tmp.removeLast ( ) ; SkewHeap b = tmp.removeLast ( ) ; b.right = b.Klik met de linker ; b.Klik met de linker = a ; tmp.addLast ( b ) ; } return tmp.getFirst ( ) ;} " "
6

Schrijf het removeHead methode . Dit zal het hoofd knooppunt verwijderen en samenvoegen van de linker en rechter kind hoopjes " " openbare SkewHeap removeHead ( ) {if (links == null && rechts == null ) return null ; . Else if (links == null ) return rechts; anders if ( rechts == null ) return links; anders return left.merge ( rechts ) ;} " "
7

Formuleer de afdruk methode . Deze methode is van belang voor het debuggen , als debuggers niet vaak hebben de faciliteiten om geneste data structuren te bekijken als deze scheef heap . Het is recursieve en streepjes correct " " public void print () { for ( int i = 0 ; . I System.out.println ( waarde ) ; streepje + + if ( links = null ) { for ( int i = 0 ; ! I System . out.println ( " left.print ( ) ;} if ( rechts = null ) { for ( int i = 0; i System.out.println ( " - > " ) ; right.print ( ) ; } streepje - - ;} " "