public class HeapQ<T> where T : IComparable { List<T> items; public HeapQ () { items = new List<T> (); } public bool Empty { get { return items.Count == 0; } } public T First { get { if (items.Count > 1) { return items[0]; } return items[items.Count - 1]; } } public void Push (T item) { items.Add (item); SiftDown (0, items.Count - 1); } public T Pop () { T item; var last = items[items.Count - 1]; items.RemoveAt (items.Count - 1); if (items.Count > 0) { item = items[0]; items[0] = last; SiftUp (0); } else { item = last; } return item; } void SiftDown (int startpos, int pos) { var newitem = items[pos]; while (pos > startpos) { var parentpos = (pos - 1) >> 1; var parent = items[parentpos]; if (parent.CompareTo (newitem) <= 0) break; items[pos] = parent; pos = parentpos; } items[pos] = newitem; } void SiftUp (int pos) { var endpos = items.Count; var startpos = pos; var newitem = items[pos]; var childpos = 2 * pos + 1; while (childpos < endpos) { var rightpos = childpos + 1; if (rightpos < endpos && items[rightpos].CompareTo (items[childpos]) <= 0) childpos = rightpos; items[pos] = items[childpos]; pos = childpos; childpos = 2 * pos + 1; } items[pos] = newitem; SiftDown (startpos, pos); } }
Thursday, August 25, 2011
Heap Queue in C#
A minimal re-implementation of the Python heapq module.
Subscribe to:
Post Comments (Atom)
Popular Posts
-
These are the robots I've been working on for the last 12 months. They each weigh about 11 tonnes and have a 17 meter reach. The control...
-
So, you've created a car prefab using WheelCollider components, and now you can apply a motorTorque to make the whole thing move along. ...
-
The procedural planet package has been updated to version 1.4, and you can see the new demo here . It features better city light control, be...
-
I have just spent an hour trying to track down a weird bug in some Javascript interpolation code. The offending code looks like this: var n ...
-
Dear Lazyweb. Imagine a nice RESTful interface for working with Tags. The URL: /tags/ will return a list of all the tags. The URL: /tags/fo...
-
Why would I ask that question? Python 3 has been available for some time now, yet uptake is slow. There aren't a whole lot of packages i...
-
I've just finished refactoring an awful C# class. I had been delaying the job for a while because I didn't want to do it. Then, whil...
-
I've built sites with Django, TurboGears and Pylons. I've come to prefer Pylons. Why? Pylons gets out of the way, and stays out of t...
-
I've just uploaded Fibra 2 to the cheeseshop. Fibra 2 includes the promised non-blocking plugin, which allows a generator based task to...
-
After my last post, I decided to benchmark the scaling properties of Stackless, Kamaelia, Fibra using the same hackysack algorithm. Left axi...
No comments:
Post a Comment