Heap / Heapsort

Ich möchte meinen ersten Beitrag über eine alte Datenstruktur namens Heap schreiben. Die bekannteste Anwendung ist sicherlich der Heapsort-Algorithmus, jedoch gibt es noch andere Einsatzgebiete, auf die ich eingehen werde.

Der Heap (engl. für „Haufen“) ist eine abstrakte Datenstruktur, die auf einem binären Baum basiert. Dieser wird in der Regel in einem Array abgebildet, wobei der Zugriff auf die beiden Kinder eines Knotens leicht über den Index berechnet werden kann. Typischerweise fängt der Index mit 0 an, so dass zu einem Index i das linke Kind an der Position 2 * i + 1 und das rechte Kind an der Position 2 * i + 2 liegt.

Mit dieser Art der Speicherung lässt sich auch leicht bestimmen, welche Knoten zu den „Blättern“ gehören, also keine eigenen Kinder haben. Hat ein Heap bspw. 5 Elemente, so ist 0 die Wurzel, 1 und 2 die Kinder der Wurzel und 3 und 4 die Kinder von 1. Insgesamt haben die Elemente 2, 3 und 4 keine Kinder. Dies lässt sich leicht über die Formel (elementCount - 2) / 2 berechnen, wobei elementCount die Anzahl der Element darstellt und die Formel den letzten inneren Knoten (mit mindestens einem Kind) berechnet.

Ein solches Array wird aber erst zu einem Heap, wenn die Heap-Eigenschaft erfüllt ist, dass alle Eltern größer als ihre Kinder sind (auch „Max-Heap“ genannt).

Um diese Heap-Eigenschaft zu implementieren, müssen beim Hinzufügen von Elementen diese einfach an das Ende der bisherigen Heap-Struktur angefügt werden und dann solange mit ihrem Vater verglichen werden, bis dieser größer ist als das neue Element.

Bei einem Heap kann nur das oberste (Wurzel-)Element gelöscht werden. In der einfachen Implementierung eines Heaps rückt dann jeweils das größte Kind-Element nach, bis ein Blatt erreicht wird.

Der Heapsort funktioniert nun einfach so, dass erst aus den zu sortierenden Elementen ein Heap aufgebaut wird. In einem zweiten Schritt („Heapify„) wird nun die Wurzel mit dem letzten Element vertauscht und die Heap-Größe um 1 reduziert. Dann wird der Wurzelwert mit seinen beiden Kindern verglichen und sollte eines größer sein, mit diesem vertauscht. Dies erfolgt solange, bis keines der Kinder mehr größer ist.

Hier zuerst eine Implementierung in Scala, die auf die notwendigsten Operationen beschränkt ist und den Algorithmus gut veranschaulicht:

Heap.scala

trait PriorityQueue[T] {
  def add( element: T )
  def top: Option[T]
  def removeTop(): Option[T]
}

class Heap[T <% Ordered[T]: ClassTag]( val elements: Array[T], var elementCount: Int ) 
    extends PriorityQueue[T] {
  def this( size: Int ) = this( new Array[T]( size ), 0 )
  def this( array: Array[T] ) = this( array, array.length )
  def this() = this( Heap.DEFAULT_SIZE )

  val capacity = elements.length
  def size = elementCount;

  def add( element: T ) {
    if ( elementCount >= capacity ) throw new IllegalStateException( "capacity exhausted" )

    elements( elementCount ) = element
    elementCount += 1
    upHeap( elementCount - 1 )
  }

  def top = if ( elementCount > 0 ) Some( elements( Heap.FIRST_ELEMENT ) ) else None

  def removeTop() = {
    if ( elementCount <= 0 ) None
    else {
      val result = elements( 0 )
      elementCount -= 1
      if ( elementCount > 0 ) {
        elements( Heap.FIRST_ELEMENT ) = elements( elementCount )
        downHeap( Heap.FIRST_ELEMENT )
      }
      Some( result )
    }
  }

  def sort: Array[T] = {
    while ( elementCount > 1 ) elements( elementCount ) = removeTop( ).get
    elements
  }

  protected def leftChildPosition( parentPosition: Int ) = 2 * parentPosition + 1
  protected def rightChildPosition( parentPosition: Int ) = 2 * parentPosition + 2
  protected def leftSiblingPosition( rightSiblingPosition: Int ) = rightSiblingPosition - 1
  protected def rightSiblingPosition( leftSiblingPosition: Int ) = leftSiblingPosition + 1
  protected def parentPosition( childPosition: Int ) = ( childPosition - 1 ) / 2
  protected def hasParent( childPosition: Int ) = childPosition > Heap.FIRST_ELEMENT
  protected def inHeapRange( position: Int ) = ( position < elementCount )
  protected def lastInnerNode = ( elementCount - 2 ) / 2
  protected def isLeaf( position: Int ) = position > lastInnerNode

  private def exchangeValues( firstPosition: Int, secondPosition: Int ) {
    if ( firstPosition != secondPosition ) {
      val temp = elements( firstPosition )
      elements( firstPosition ) = elements( secondPosition )
      elements( secondPosition ) = temp
    }
  }

  protected def downHeap( parentPosition: Int ) {
    def maxValuePosition( firstPosition: Int, secondPosition: Int ) =
      if ( elements( firstPosition ) > elements( secondPosition ) ) firstPosition
      else secondPosition

    val leftChild = leftChildPosition( parentPosition )
    if ( inHeapRange( leftChild ) ) {
      var maxPosition = maxValuePosition( parentPosition, leftChild )
      val rightChild = rightSiblingPosition( leftChild )
      if ( inHeapRange( rightChild ) ) maxPosition = maxValuePosition( maxPosition, rightChild )
      exchangeValues( parentPosition, maxPosition )
      if ( maxPosition != parentPosition ) downHeap( maxPosition )
    }
  }

  @tailrec
  private def upHeap( childPosition: Int ) {
    if ( childPosition > Heap.FIRST_ELEMENT ) {
      val parentPos = parentPosition( childPosition )
      if ( elements( childPosition ) > elements( parentPos ) ) {
        exchangeValues( parentPos, childPosition )
        upHeap( parentPos )
      }
    }
  }

  private def makeHeap {
    for ( i <- lastInnerNode to ( Heap.FIRST_ELEMENT, -1 ) ) downHeap( i )
  }
  makeHeap
}

object Heap {
  val DEFAULT_SIZE = 16
  val FIRST_ELEMENT = 0
}

Eine überarbeitete Fassung des Algorithmus benötigt in der Regel weniger Vergleiche. Diese Variante wird "Bottom-Up-Heap" genannt und im gleichnamigen verwendet. Der Unterschied besteht darin, dass beim Löschen der Wurzel das jeweils größte Kind direkt an die Stelle des Vaters tritt. Erst wenn ein Blatt erreicht wird, wird das einzufügende Element solange im Heap nach oben bewegt, bis an der passenden Stelle angelangt. Da in einem Heap bereits die Hälfte aller Elemente Blätter sind (!), kann in der Regel durch diese Modifikation ein deutlicher Geschwindigkeitszuwachs erzielt werden.

Hier der entsprechende Scala-Code:

BottomUpHeap.scala

class BottomUpHeap[T <% Ordered[T]: ClassTag]( array: Array[T], count: Int )
  extends Heap[T]( array, count ) {
  def this( array: Array[T] ) = this( array, array.length )
  def this( size: Int ) = this( new Array[T]( size ), 0 )
  def this() = this( Heap.DEFAULT_SIZE )

  override protected def downHeap( position: Int ) {
    @tailrec
    def searchLargestChild( position: Int ): Int = {
      if ( isLeaf( position ) )
        position
      else {
        val rightChildPos = rightChildPosition( position )
        val leftChildPos = leftSiblingPosition( rightChildPos )
        if ( inHeapRange( rightChildPos ) ) {
          val largestChildPos =
            if ( elements( leftChildPos ) > elements( rightChildPos ) )
              leftChildPos
            else
              rightChildPos
          searchLargestChild( largestChildPos )
        } else {
          leftChildPos
        }
      }
    }

    @tailrec
    def findInsertionPosition( position: Int, value: T ): Int = {
      if ( !hasParent( position ) || ( elements( position ) >= value ) )
        position
      else
        findInsertionPosition( parentPosition( position ), value )
    }

    @tailrec
    def swapValuesUp( topPos: Int, insertionPos: Int, insertionValue: T ) {
      if ( insertionPos == topPos ) {
        elements( insertionPos ) = insertionValue
      } else {
        val value = elements( insertionPos )
        elements( insertionPos ) = insertionValue
        swapValuesUp( topPos, parentPosition( insertionPos ), value )
      }
    }

    val insertionValue = elements( position )
    val largestChildPos = searchLargestChild( position )
    val insertionPos = findInsertionPosition( largestChildPos, insertionValue )
    swapValuesUp( position, insertionPos, insertionValue )
  }
}