C# Priority Queue/Heap

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Prelates, Moderators General

C# Priority Queue/Heap

Postby TomZ » Fri Oct 07, 2011 8:54 pm UTC

I am preparing for a programming context next week and I'm programming in C#.NET. When implementing Dijkstra's Algorithm, it is common to use a priority queue or heap to work out which node to visit next. Unfortunately, C# does not provide these data structures natively. Using non-standard libraries is forbidden and implementing one myself seems a waste of precious time. We are allowed to bring printouts so in theory I could write the code beforehand and copy it, but that's still inefficient.
I thought I had solved my problem when I discovered SortedSet but this is not supported (or disabled on purpose?) by the judging server. Does anyone know of a suitable alternative?


One alternative I've found myself is SortedList but I'm getting an error I don't understand. For instance, when I have
Code: Select all
SortedList<Node, int> queue = new SortedList<Node, int>()

calling queue.Min() results in an error that at least one object must implement IComparable. However, Node implements IComparable and has the public member int CompareTo(object other).
Does anyone know what I'm doing wrong here?
TomZ
 
Posts: 6
Joined: Wed Sep 14, 2011 8:26 pm UTC

Re: C# Priority Queue/Heap

Postby Sc4Freak » Sun Oct 09, 2011 11:03 am UTC

You can use a plain old List. The BinarySearch method does everything you need it to - give it an object, and it'll return the index of that object (performing a binary search through a sorted list). If the object doesn't exist, it'll return the bitwise complement of the index where the object should be inserted. It's not exactly a heap, but it should get plenty close.

calling queue.Min() results in an error that at least one object must implement IComparable. However, Node implements IComparable and has the public member int CompareTo(object other).
Does anyone know what I'm doing wrong here?


Min is an extension method provided by LINQ. It performs a linear search through an IEnumerable sequence, looking for the minimum value. SortedList<TKey, TValue> implements IEnumerable<KeyValuePair<TKey, TValue>>, which means that Min() is trying to find the minimum KeyValuePair<TKey, TValue>. KeyValuePair<TKey, TValue> doesn't implement IComparable, so it throws an exception.
User avatar
Sc4Freak
 
Posts: 673
Joined: Thu Jul 12, 2007 4:50 am UTC
Location: Redmond, Washington

Re: C# Priority Queue/Heap

Postby rpenido » Fri Oct 14, 2011 11:01 am UTC

Can you post the code of Node class ?
You really need to use SortedList ?

The code below uses the List class. If you want to use the CompareTo from the Node class, it will work for you.

Code: Select all
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Node: IComparable<Node>
    {
        public int value;

        public Node(int value)
        {
            this.value = value;
        }

        public int CompareTo(Node other)
        {
            return value.CompareTo(other.value);
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            List<Node> nodeList = new List<Node>();
            nodeList.Add(new Node(5));
            nodeList.Add(new Node(1));
            nodeList.Add(new Node(2));
            nodeList.Add(new Node(3));
            Node minNode = nodeList.Min();
            Console.WriteLine("MinValue: " + minNode.value);
            Console.ReadKey();
        }
    }
rpenido
 
Posts: 12
Joined: Thu Sep 09, 2010 1:58 pm UTC


Return to Coding

Who is online

Users browsing this forum: Exabot [Bot] and 13 guests