Generic Heap and prioritized queues in C#

One of the systems I'm writing required a heap data structure so I've implemented it as a generic as its quite useful for guaranteed sort times and for prioritized queues.

which can be used:

string data = "an out of order string";


var heap = new Heap<char>();
foreach (char c in data)
  heap.Push(c);

// in order becomes
while (heap.Count != 0)
  Console.WriteLine(heap.Pop());

// or in reverse order, using a custom order

Comparison<char> comparison = delegate(char first, char second)
{
  return second.CompareTo(first);
};

var heap2 = new Heap<char>(comparison);
foreach (char c in data)
  heap2.Push(c);
while (heap2.Count != 0)
  Console.WriteLine(heap2.Pop());

implemented as:

using System;
using System.Collections.Generic;
using System.Text;

namespace Heaps
{

/// <summary>
/// heap data stucture, guaranteed O(nlog n), acts as a priority queue
/// </summary>
/// <typeparam name="T">data to hold in heap tree</typeparam>
class Heap<TValue> where TValue : IComparable
{
  // functions return if item not found
  public const int NOTFOUND = -1;
  // root offset
  const int ROOT = 0;
  // forward, backward step direction
  const int FORWARD = 1;
  const int BACKWARD = -FORWARD;
  // storage of values
  List<TValue> values = null;
  // allow parameterisation of ordering and (min/max heap)
  Comparison<TValue> comparison = null;

  /// <summary>
  /// creates a new heap, with ordering
  /// defined by T : IComparable
  /// </summary>
  public Heap()
  {
    values = new List<TValue>();
  }

  /// <summary>
  /// creates a new heap, with ordering
  /// defined by Comparison<T>
  /// </summary>
  /// <param name="comparison"></param>
  public Heap(Comparison<TValue> comparison): this()
  {
    this.comparison = comparison;
  }

  /// <summary>
  /// return the value at offset position in the tree (pre-order traversal)
  /// </summary>
  /// <param name="position">offset in tree</param>
  /// <returns></returns>
  public TValue this[int position]
  {
    get
    {
      return values[position];
    }
  }

  /// <summary>
  /// number of values in tree
  /// </summary>
  public int Count
  {
    get
    {
      return Length();
    }
  }

  /// <summary>
  /// returns the offset of the parent
  /// </summary>
  /// <param name="position">the value position to find parent of</param>
  /// <returns>offset of parent in tree</returns>
  public int ParentOf(int position)
  {
    int result = NOTFOUND;
    if (position > 0)
      result = ((position+1) / 2) - 1;

    return result;
  }

  /// <summary>
  /// return the offset of the left child
  /// </summary>
  /// <param name="position">the value offset position to find the left child of</param>
  /// <returns>offset of left child in tree</returns>
  public int Left(int position)
  {
    int result = NOTFOUND;

    result = (position * 2) + 1;

    result = EnsureNotBeyond(result);

    return result;
  }

  /// <summary>
  /// return the offset of the right child
  /// </summary>
  /// <param name="position">the value offset position to find the right child of</param>
  /// <returns>offset of right child in tree</returns>
  public int Right(int position)
  {
    // right node is 1 more than the left
    int result = Left(position);

    if (result != NOTFOUND)
      result++; // one position beyond left

    result = EnsureNotBeyond(result);

    return result;
  }

  /// <summary>
  /// returns the root value
  /// </summary>
  public TValue Root
  {
    get
    {
      if (Length() == 0)
        throw new InvalidOperationException("No items in heap");

      return values[ROOT];
    }
  }

  /// <summary>
  /// returns the value with highest priority
  /// </summary>
  /// <returns>the value</returns>
  public TValue Pop()
  {
    TValue result = Root;

    int lastItem = EnsureNotBeyond(Length() - 1);

    if (Length() > 1)
      values[ROOT] = values[lastItem];

    values.RemoveAt(lastItem);

    MaintainHeapProperty(FORWARD);

    return result;
  }

  /// <summary>
  /// add the value to the tree
  /// </summary>
  /// <param name="value">value to add</param>
  public void Push(TValue value)
  {
    values.Add(value);

    MaintainHeapProperty(BACKWARD);
  }

  /// <summary>
  /// number of nodes
  /// </summary>
  /// <returns>length</returns>
  private int Length()
  {
    return values.Count;
  }

  /// <summary>
  /// ensures a  position is not beyond the tree storage
  /// </summary>
  /// <param name="position">offset</param>
  /// <returns>offset, or NOTFOUND if out of bounds</returns>
  private int EnsureNotBeyond(int position)
  {
    if (position >= Length())
      position = NOTFOUND;

    return position;
  }

  /// <summary>
  /// adjusts tree to ensure heap property maintained after a push or pop
  /// </summary>
  /// <param name="direction">FORWARD for push, BACKWARD if pop</param>
  private void MaintainHeapProperty(int direction)
  {
    int start = (direction == FORWARD) ? ROOT : Length();
    int end = (direction == FORWARD) ? Length() : NOTFOUND;

    for (int pos = start; pos != end; pos += direction)
    {
      int left = Left(pos);
      int right = Right(pos);

      // ensure this value is greater than chidren
      if (left != NOTFOUND && Compare(pos, left) < 0)
        Swap(pos, left);
      if (right != NOTFOUND && Compare(pos, right) < 0)
        Swap(pos, right);
    }
  }

  /// <summary>
  /// return integer indicating order
  /// </summary>
  /// <param name="first">offset of first</param>
  /// <param name="second">offset of second</param>
  /// <returns>.lt. zero=first,second;zero=first==second;.gt. zero=second,first</returns>
  private int Compare(int first, int second)
  {
    int result = 0;

    // if comparison delegate provided us it to compare
    if (comparison != null)
      result = comparison(values[first], values[second]);
    else // default TValue compare
      result = values[first].CompareTo(values[second]);

    return result;
  }

  /// <summary>
  /// swaps two offsets
  /// </summary>
  /// <param name="first">first offset</param>
  /// <param name="second">second offset</param>
  private void Swap(int first, int second)
  {
    TValue temp = values[first];
    values[first] = values[second];
    values[second] = temp;
  }

  public override string ToString()
  {
    StringBuilder sb = new StringBuilder();

    sb.Append("[");
    foreach (TValue value in values)
      sb.Append(value.ToString());
    sb.Append("]");

    return sb.ToString();
  }
}

}