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, Wash. He has worked on several Microsoft products including Azure and Bing. James can be reached at [email protected].

comments powered by Disqus

Featured

Subscribe on YouTube