Compare a list priority queue to a heap priority queue in C#

[binary tree]My book Essential Algorithms: A Practical Approach to Computer Algorithms describes lots of other interesting data structures and algorithms, many just as interesting but less complicated than this one. For more information about queues, priority queues, trees and other algorithmic topics, give it a look.



[priority queue]
The example Make a generic priority queue class in C# explains how to build a list-based priority queue. It can enqueue and dequeue items in O(N) time. (Actually depending on how smart the lists are at resizing, the queue can probably enqueue items in less than O(N) time.)

The example Make an efficient priority queue class in C#, Part 2 explains how to build a heap-based priority queue that can enqueue and dequeue objects in O(log N) time.

This post compares the two kinds of queues to see which is faster under different circumstances.

When you click the Go button, the program executes the following code.

// Run the tests.
private void btnGo_Click(object sender, EventArgs e)
{
    lblHeapQueue.Text = "";
    lblListQueue.Text = "";
    Cursor = Cursors.WaitCursor;
    Refresh();

    // Get the input parameters.
    int num_items = int.Parse(txtNumItems.Text);
    int num_trials = int.Parse(txtNumTrials.Text);
    int max_priority = int.Parse(txtMaxPriority.Text) + 1;

    // Make some random values.
    string[] values = new string[num_items];
    int[] priorities = new int[num_items];
    Random rand = new Random();
    for (int i = 0; i < num_items; i++)
    {
        priorities[i] = rand.Next(0, max_priority);
        values[i] = priorities[i].ToString();
    }

    string value;
    int priority;
    Stopwatch watch = new Stopwatch();

    // Test the heap queue.
    watch.Start();
    HeapQueue<string> heap_queue =
        new HeapQueue<string>();
    for (int trial = 0; trial < num_trials; trial++)
    {
        // Save the values.
        for (int i = 0; i < num_items; i++)
            heap_queue.Enqueue(values[i], priorities[i]);
        // Retrieve the values.
        for (int i = 0; i < num_items; i++)
            heap_queue.Dequeue(out value, out priority);
    }
    watch.Stop();
    lblHeapQueue.Text =
        watch.Elapsed.TotalSeconds.ToString("0.00") +
        " seconds";
    lblHeapQueue.Refresh();

    // Test the list queue.
    watch.Reset();
    watch.Start();
    PriorityQueue<string> list_queue =
        new PriorityQueue<string>();
    for (int trial = 0; trial < num_trials; trial++)
    {
        // Save the values.
        for (int i = 0; i < num_items; i++)
            list_queue.Enqueue(values[i], priorities[i]);
        // Retrieve the values.
        for (int i = 0; i < num_items; i++)
            list_queue.Dequeue(out value, out priority);
    }
    watch.Stop();
    lblListQueue.Text =
        watch.Elapsed.TotalSeconds.ToString("0.00") +
        " seconds";
    lblListQueue.Refresh();

    Cursor = Cursors.Default;
}

After some preliminaries, the code creates some random test items.

Next the prorgam creates a heap-based priority queue. For the desired number of trials, the program adds all of the test items to the queue and then removes the items from the queue. When it finishes, the program displays the elapsed time.

The program then repeats the trials with a list-based priority queue.

[priority queue]
The picture at the top of this post shows the results of adding and removing 1,000 items from the queues 1,000 times. You can see that the heap-based priority queue is much faster, taking only about 1/5th as long as the list-based priority queue.



[priority queue]
However, the relative speeds of the queues depends on the number of items that you add and remove. The heap-based priority queue is more complicated than the list-based version, so its overhead dominates if you only add and remove a few items. Figure 1 shows that when you add and remove only 10 items, the heap-based priority queue takes around 2.7 times as long as the list-based queue.



[priority queue]
In contrast, when you add and remove more items, the overhead become insignificant compared to the asymptotic runtime (the O(N) versus O(log N) times). As Figure 2 shows, when you add and remove 10,000 items to the queue, the list-based priority queue takes more than 45 times as long as the heap-based queue.

The break even point in my tests was around 125 items.

The moral is that you should think about how you will use a particular algorithm or data structure before you decide which one to use. In this example, the list-based priority queue is faster if you will only add a small number of items to it.

Download the example program and look at the code for more details. And be sure to look at my book Essential Algorithms: A Practical Approach to Computer Algorithms for more information about other interesting and useful algorithms.


Download Example   Follow me on Twitter   RSS feed   Donate




About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms, classes, generic, mathematics, OOP and tagged , , , , , , , , , , , , . Bookmark the permalink.

One Response to Compare a list priority queue to a heap priority queue in C#

  1. Maxy says:

    That’s great, thanks and I will you more nicely jobs.

Leave a Reply

Your email address will not be published. Required fields are marked *