Priority Queues with C#: Listing 5.

Checking the state of the priority queue.

public bool IsConsistent()
{
  if (data.Count == 0) return true;
  int li = data.Count - 1; // last index
  for (int pi = 0; pi  < data.Count; ++pi) // each parent index
  {
    int lci = 2 * pi + 1; // left child index
    int rci = 2 * pi + 2; // right child index
    if (lci  <= li && data[pi].CompareTo(data[lci])  > 0) return false;
    if (rci  <= li && data[pi].CompareTo(data[rci])  > 0) return false;
  }
  return true; // Passed all checks
}

About the Author

Dr. James McCaffrey works for Microsoft Research in Redmond, WA. James has worked on several key Microsoft products such as Internet Explorer and Bing. James can be reached at jamccaff@microsoft.com.