C# Heapsort

February 15, 2008 – 8:01 am

This is a simple implementation of the Heapsort algorithm in C#. It is a max-heap implementation, meaning that it builds the heap from the bottom up by sifting down the maximum element; this is opposed to the min-heap implementation that builds the heap top-down by sifting upward. Also, this method is a member of the Sorting class that I will present later, and the generic class T is defined in this context as any class that implements IComparable.

   1:  public void Heapsort (T[] array, int start, int end)

   2:  {

   3:    // to begin, place the array in max-heap order

   4:   

   5:    // get the index in array of the last parent node

   6:    int left = start + ((end - start) >> 1);

   7:    int right = end;

   8:    int offset = start;

   9:   

  10:    //while (left >= 0)

  11:    while (left >= start)

  12:    {

  13:      // sift down the node at index left to the proper place so that all

  14:      //   nodes below the left index are in heap order

  15:      //SiftDown(array, left, array.Length - 1);

  16:      SiftDown(array, offset, left, end);

  17:      left -= 1;

  18:    }

  19:   

  20:    // all nodes should now be in max-heap order

  21:   

  22:    while (right > start)

  23:    {

  24:      // swap the maximum value of the heap with the last element of the

  25:      //   heap

  26:      Swap(array, right, start);

  27:   

  28:      // decrease the size of the heap by one so that the previous max

  29:      //   value will stay in its proper placement

  30:      right -= 1;

  31:   

  32:      // put the heap back in max-heap order

  33:      SiftDown(array, offset, start, right);

  34:    }

  35:  }

  36:   

  37:  private void SiftDown (T[] array, int offset, int start, int end)

  38:  {

  39:    int root = start;

  40:    int child;

  41:   

  42:    // keep going while the root has at least one child

  43:    while (((root - offset) * 2 + 1) <= (end - offset))

  44:    {

  45:      // get the left child

  46:      child = ((root - offset) * 2 + 1) + offset;

  47:   

  48:      // if the child has a sibling and the child’s value is less than its

  49:      //   siblings

  50:      if (child < end && array[child].CompareTo(array[child + 1]) < 0)

  51:      {

  52:        // point to the right child instead

  53:        child += 1;

  54:      }

  55:      if (array[root].CompareTo(array[child]) < 0)

  56:      {

  57:        // out of max-heap order

  58:        Swap(array, root, child);

  59:   

  60:        // repeat to continue sifting down the child

  61:        root = child;

  62:      }

  63:      else

  64:      {

  65:        // all sifted

  66:        break;

  67:      }

  68:    }

  69:  }

  70:   

  71:  private void Swap (T[] array, int i, int k)

  72:  {

  73:    T swap = array[i];

  74:    array[i] = array[k];

  75:    array[k] = swap;

  76:  }