[WikiDyd] [TitleIndex] [WordIndex

C# : Kopiec i kolejka priorytetowa oparta na kopcu

Kopiec:

   1 using System;
   2 
   3 namespace aisd
   4 {
   5     public class Heap<T> where T : IComparable<T>
   6     {
   7         private T[] h;
   8         private int nEntries;
   9         public Heap()
  10             : this(100)
  11         {
  12         }
  13         public Heap(int size)
  14         {
  15             h = new T[size];
  16             nEntries = 0;
  17         }
  18         public void Put(T e)
  19         {
  20             if (nEntries == h.Length)
  21                 resize();
  22             h[nEntries++] = e;
  23             heapUp();
  24         }
  25         public T Get()
  26         {
  27             if (nEntries == 0)
  28                 return default(T);
  29             else
  30             {
  31                 T tmp = h[0];
  32                 h[0] = h[--nEntries];
  33                 heapDown();
  34                 return tmp;
  35             }
  36         }
  37         public bool IsEmpty()
  38         {
  39             return nEntries == 0;
  40         }
  41         public void Clear()
  42         {
  43             nEntries = 0;
  44         }
  45         override public string ToString()
  46         {
  47             string tmp = "[";
  48             for (int i = 0; i < nEntries; i++)
  49                 tmp += " " + h[i];
  50             return tmp + " ]";
  51         }
  52         public string ToStringDebug()
  53         {
  54             string tmp = "[";
  55             for (int i = 0; i < nEntries; i++)
  56                 tmp += " " + h[i] + "[" + i + ":" + (i - 1) / 2 + "]";
  57             return tmp + " ]";
  58         }
  59         private void swap(int i, int j)
  60         {
  61             T tmp = h[i];
  62             h[i] = h[j];
  63             h[j] = tmp;
  64         }
  65         private void resize()
  66         {
  67             T[] nh = new T[h.Length * 2];
  68             for (int i = 0; i < nEntries; i++)
  69                 nh[i] = h[i];
  70             h = nh;
  71         }
  72         private void heapUp()
  73         {
  74             int i = nEntries - 1;
  75             int p;
  76             while ((p = (i - 1) / 2) >= 0)
  77             {
  78                 if (h[p].CompareTo(h[i]) >= 0)
  79                     return;
  80                 swap(i, p);
  81                 i = p;
  82             }
  83         }
  84         private void heapDown()
  85         {
  86             int i = 0;
  87             int c = 2 * i + 1;
  88             while (c < nEntries)
  89             {
  90                 if (c + 1 < nEntries && h[c + 1].CompareTo(h[c]) > 0)
  91                     c++;
  92                 if (h[i].CompareTo(h[c]) >= 0)
  93                     return;
  94                 swap(i, c);
  95                 i = c;
  96                 c = 2 * i + 1;
  97             }
  98         }
  99     }
 100 }

Kolejka priorytetowa - abstrakcyjny typ danych

   1 using System;
   2 using System.Collections.Generic;
   3 using System.Text;
   4 
   5 namespace aisd
   6 {
   7     public interface IPriorityQueue<T> where T : IComparable<T>
   8     {
   9         bool IsEmpty();
  10         void Push(T entry);
  11         T Pop();
  12     }
  13 }

Implementacja IPriorityQueue za pomoc─ů kopca:

   1 using System;
   2 using System.Collections.Generic;
   3 using System.Text;
   4 
   5 namespace aisd
   6 {
   7     public class PriorityQueue<T> : IPriorityQueue<T> where T : IComparable<T>
   8     {
   9         public PriorityQueue() {
  10             h = new Heap<T>();
  11         }
  12 
  13         #region IPriorityQueue<T> Members
  14 
  15         public bool IsEmpty()
  16         {
  17             return h.IsEmpty();
  18         }
  19 
  20         public void Push(T entry)
  21         {
  22             h.Put(entry);
  23         }
  24 
  25         public T Pop()
  26         {
  27             return h.Get();
  28         }
  29 
  30         #endregion
  31 
  32         private Heap<T> h;
  33     }
  34 }

2015-09-23 06:32