Priority Queues with C#: Listing 4.

Removing an item from a priority queue.

public T Dequeue()
{
  // Assumes pq isn't empty
  int li = data.Count - 1;
  T frontItem = data[0];
  data[0] = data[li];
  data.RemoveAt(li);

  --li;
  int pi = 0;
  while (true)
  {
    int ci = pi * 2 + 1;
    if (ci  > li) break;
    int rc = ci + 1;
    if (rc  <= li && data[rc].CompareTo(data[ci])  < 0)
      ci = rc;
    if (data[pi].CompareTo(data[ci])  <= 0) break;
    T tmp = data[pi]; data[pi] = data[ci]; data[ci] = tmp;
    pi = ci;
  }
  return frontItem;
}

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.