HeapSort

[babuschka]

Hi Leute,

hat einer von euch vielleicht ein paar nützliche tipps wie man am besten einen heap sort programmieren kann?

Danke

 

[Beni]

Haben wir zufälligerweise diese Woche gehabt...
... wo bist du Student? ???:L

Der Heapsort besteht eigentlich aus 4 Methoden:

- Versinken (sink)
- Vertauschen (swap)
- Herstellen des Heaps (heapify)
- Sortieren (sort)


Zuerst wird der Heap hergestellt, indem die Hälfte des Heaps versinkt:

        for( int i = array.length/2; i>= 0; i-- )
            sink( array, i, array.length );

Danach kannst du Sortieren:

        for( int i = array.length-1; i>= 0; i-- ){
            swap( array, 0, i );
            sink( array, 0, i );
        }

Versinken ist das schwierigste: das Element das sinkt mit dem grösseren seiner Childs vertauschen (sofern diese Childs auch tatsächlich grösser sind, als das Element). Und das solange wiederholen, bis das Element zuunterst im Heap-Baum ist, oder beide Childs kleiner sind:

    private void sink( Comparable[] array, int index, int last ){
        while( true ){
            int left = 2*index;
            int right = left+1;
            
            if( left >= last )
                return;
            
            else if( right >= last ){
                boolean leftGreater = 0 < array[ left ].compareTo( array[ index ] );
                
                swap( array, index, left );
                return;
            }
            
            boolean leftGreater = 0 < array[ left ].compareTo( array[ index ] );
            boolean rightGreater = 0 < array[ right ].compareTo( array[ index ] );
            
            
            if( leftGreater && rightGreater ){
                boolean leftGreaterRight = 0 < array[ left ].compareTo( array[ right ] );
                
                if( leftGreaterRight ){
                    swap( array, index, left );
                    index = left;
                }
                else{
                    swap( array, index, right );
                    index = right;
                }
            }
            else if( leftGreater ){
                swap( array, index, left );
                index = left;
            }
            else if( rightGreater ){
                swap( array, index, right );
                index = right;
            }
            else
                break;
        }

Und falls dir das alles nichts sagt -> google :wink:

mfg Beni

 

[babuschka]

Hi Beni,

so wie es ausschaut hat es die TU Berlin auch diese Woche.

Werd mich erst mal durch deinen Tipp durchwurschteln.

Danke

Christian