fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace IceAndFire.DataStructures
  5. {
  6.     public class PriorityQueue<T> where T : IComparable<T>
  7.     {
  8.         private readonly List<T> _data;
  9.  
  10.         public PriorityQueue()
  11.         {
  12.             _data = new List<T>();
  13.         }
  14.  
  15.         public void Enqueue(T item)
  16.         {
  17.             _data.Add(item);
  18.             var ci = _data.Count - 1; // child index; start at end
  19.             while (ci > 0)
  20.             {
  21.                 var pi = (ci - 1) / 2; // parent index
  22.                 if (_data[ci].CompareTo(_data[pi]) >= 0)
  23.                     break; // child item is larger than (or equal) parent so we're done
  24.                 var tmp = _data[ci];
  25.                 _data[ci] = _data[pi];
  26.                 _data[pi] = tmp;
  27.                 ci = pi;
  28.             }
  29.         }
  30.  
  31.         public T Dequeue()
  32.         {
  33.             // assumes pq is not empty; up to calling code
  34.             var li = _data.Count - 1; // last index (before removal)
  35.             var frontItem = _data[0]; // fetch the front
  36.             _data[0] = _data[li];
  37.             _data.RemoveAt(li);
  38.  
  39.             --li; // last index (after removal)
  40.             var pi = 0; // parent index. start at front of pq
  41.             while (true)
  42.             {
  43.                 var ci = pi * 2 + 1; // left child index of parent
  44.                 if (ci > li) break; // no children so done
  45.                 var rc = ci + 1; // right child
  46.                 if (rc <= li && _data[rc].CompareTo(_data[ci]) < 0
  47.                 ) // if there is a rc (ci + 1), and it is smaller than left child, use the rc instead
  48.                     ci = rc;
  49.                 if (_data[pi].CompareTo(_data[ci]) <= 0)
  50.                     break; // parent is smaller than (or equal to) smallest child so done
  51.                 var tmp = _data[pi];
  52.                 _data[pi] = _data[ci];
  53.                 _data[ci] = tmp; // swap parent and child
  54.                 pi = ci;
  55.             }
  56.  
  57.             return frontItem;
  58.         }
  59.  
  60.         public T Peek()
  61.         {
  62.             var frontItem = _data[0];
  63.             return frontItem;
  64.         }
  65.  
  66.         public int Count()
  67.         {
  68.             return _data.Count;
  69.         }
  70.  
  71.         public override string ToString()
  72.         {
  73.             var s = "";
  74.             foreach (var t in _data)
  75.                 s += t + " ";
  76.  
  77.             s += "count = " + _data.Count;
  78.             return s;
  79.         }
  80.     } // PriorityQueue
  81. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
error CS5001: Program `prog.exe' does not contain a static `Main' method suitable for an entry point
Compilation failed: 1 error(s), 0 warnings
stdout
copy 
Standard output is empty
https://ideone.com/4hXvBH
language:
C# (gmcs 5.20.1)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!