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].