[WikiDyd] [TitleIndex] [WordIndex

Kopiec i sortowanie przez kopcowanie C#

Krótki przykładzik w C# pokazujący implementację kopca.

Klasa Heap - zawiera implementację generycznego kopca i statyczną metodę sortującą tablice.

   1 using System;
   2 
   3 namespace Heap
   4 {
   5     public delegate int T_COMPARATOR<T>(T o1, T o2);
   6 
   7     /// <summary>
   8     /// Tested class: a heap of T.
   9     /// </summary>
  10     /// <param name="n">The n.</param>
  11     class Heap<T>
  12     {
  13         private T[] v;
  14         private int n;
  15         public int Length = 0;
  16 
  17         private T_COMPARATOR<T> comparator;
  18 
  19         /// <summary>
  20         /// Initializes a new instance of the <see cref="Heap"/> class.
  21         /// </summary>
  22         /// <param name="n">The length of the Heap.</param>
  23         public Heap(int size, T_COMPARATOR<T> comparator)
  24         {
  25             v = new T[size];
  26             Length = v.Length;
  27             n = 0;
  28             this.comparator = comparator;
  29         }
  30 
  31         /// <summary>
  32         /// Adds new value to the heap.
  33         /// </summary>
  34         /// <param name="value">The new value.</param>
  35         public void add(T value)
  36         {
  37             v[n++] = value;
  38             putUp();
  39         }
  40 
  41         /// <summary>
  42         /// Gets the tpmost value.
  43         /// </summary>
  44         public T get()
  45         {
  46             T retVal = v[0];
  47             v[0] = v[--n];
  48             getDown();
  49             return retVal;
  50         }
  51 
  52         /// <summary>
  53         /// Prints this to Console.
  54         /// </summary>
  55         public void outToConsole()
  56         {
  57             System.Console.Write("[ ");
  58             for (int i = 0; i < n; i++)
  59                 System.Console.Write("{0} ", v[i]);
  60             System.Console.WriteLine("]");
  61         }
  62 
  63         public bool notEmpty()
  64         {
  65             return n > 0;
  66         }
  67 
  68         /// <summary>
  69         /// Moves last element up the heap until all
  70         /// relations are ok
  71         /// </summary>
  72         private void putUp()
  73         {
  74             int c = n - 1;
  75             int p = (c - 1) / 2;
  76             while (c > 0 && comparator(v[p], v[c]) < 0)
  77             {
  78                 T tmp = v[p];
  79                 v[p] = v[c];
  80                 v[c] = tmp;
  81                 c = p;
  82                 p = (c - 1) / 2;
  83             }
  84         }
  85 
  86         private void getDown()
  87         {
  88             int p = 0;
  89             int c = 2 * p + 1;
  90             while (c < n)
  91             {
  92                 if (c + 1 < n && comparator(v[c], v[c + 1]) < 0)
  93                     c++;
  94                 if (comparator(v[p], v[c]) > 0)
  95                     return;
  96                 else
  97                 {
  98                     T tmp = v[p];
  99                     v[p] = v[c];
 100                     v[c] = tmp;
 101                     p = c;
 102                     c = 2 * p + 1;
 103                 }
 104             }
 105         }
 106 
 107         public static void heapSort(T[] t, T_COMPARATOR<T> comparator)
 108         {
 109             int n = t.Length;
 110 
 111             for (int i = 1; i < n; i++)
 112             {
 113                 int c = i;
 114                 int p = (c - 1) / 2;
 115                 while (c > 0 && comparator(t[p], t[c]) < 0)
 116                 {
 117                     T tmp = t[p];
 118                     t[p] = t[c];
 119                     t[c] = tmp;
 120                     c = p;
 121                     p = (c - 1) / 2;
 122                 }
 123             }
 124             for (int i = n - 1; i > 0; i--)
 125             {
 126                 T tmp = t[0];
 127                 t[0] = t[i];
 128                 t[i] = tmp;
 129                 int p = 0;
 130                 int c = 2 * p + 1;
 131                 while (c < i)
 132                 {
 133                     if (c + 1 < i && comparator(t[c], t[c + 1]) < 0)
 134                         c++;
 135                     if (comparator(t[p], t[c]) < 0)
 136                     {
 137                         T swp = t[p];
 138                         t[p] = t[c];
 139                         t[c] = swp;
 140                         p = c;
 141                         c = 2 * p + 1;
 142                     }
 143                     else
 144                         break;
 145                 }
 146             }
 147 
 148         }
 149 
 150     }
 151 }

Program demo-testujący.

   1 using System;
   2 using System.Collections.Generic;
   3 using System.Text;
   4 
   5 namespace Heap
   6 {
   7     class Program
   8     {
   9         public static int cmp(double d1, double d2)
  10         {
  11             if (d1 > d2)
  12                 return 1;
  13             else if (d1 == d2)
  14                 return 0;
  15             else
  16                 return -1;
  17         }
  18 
  19         public static void Main(string[] args)
  20         {
  21             Heap<double> h = new Heap<double>(10, new T_COMPARATOR<double>(cmp));
  22             for (int i = 0; i < args.Length; i++)
  23                 h.add(Double.Parse(args[i]));
  24             h.outToConsole();
  25             while (h.notEmpty())
  26                 System.Console.WriteLine("{0}", h.get());
  27 
  28             double[] t = new double[10];
  29             Random rg = new Random();
  30             for (int i = 0; i < t.Length; i++)
  31                 t[i] = rg.Next(0,10);
  32 
  33             Heap<double>.heapSort(t, new T_COMPARATOR<double>(cmp));
  34 
  35             System.Console.Write("Sorted vector: [ ");
  36             for (int i = 0; i < t.Length; i++)
  37                 System.Console.Write("{0} ", t[i]);
  38             System.Console.WriteLine("]");
  39         }
  40     }
  41 }

2015-09-23 06:32