SHARE
TWEET

C# Heap Class (Generics)

ChestnutGames Aug 25th, 2015 103 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections;
  3.  
  4. public class Heap<T> where T : IHeapItem<T>
  5. {
  6.         private T[] _items;
  7.         private int _itemCount;
  8.  
  9.         public Heap(int maxSize)
  10.         {
  11.                 _items = new T[maxSize];
  12.         }
  13.  
  14.         public void Add(T item)
  15.         {
  16.                 item.HeapIndex = _itemCount;
  17.                 _items[_itemCount] = item;
  18.                 SortUp(item);
  19.                 _itemCount++;
  20.         }
  21.  
  22.         public T RemoveFirst()
  23.         {
  24.                 T firstItem = _items[0];
  25.                 _itemCount--;
  26.  
  27.                 _items[0] = _items[_itemCount];
  28.                 _items[0].HeapIndex = 0;
  29.  
  30.                 SortDown(_items[0]);
  31.                 return firstItem;
  32.         }
  33.  
  34.         public void UpdateItem(T item)
  35.         {
  36.                 SortUp(item);
  37.         }
  38.  
  39.         public int Count
  40.         {
  41.                 get
  42.                 {
  43.                         return _itemCount;
  44.                 }
  45.         }
  46.  
  47.         public bool Contains(T item)
  48.         {
  49.                 return Equals(_items[item.HeapIndex], item);
  50.         }
  51.  
  52.         void SortDown(T item)
  53.         {
  54.                 while(true)
  55.                 {
  56.                         int childIndexLeft = item.HeapIndex * 2 + 1;
  57.                         int childIndexRight = item.HeapIndex * 2 + 2;
  58.  
  59.                         int swapIndex = 0;
  60.  
  61.                         if(childIndexLeft < _itemCount)
  62.                         {
  63.                                 swapIndex = childIndexLeft;
  64.  
  65.                                 if(childIndexRight < _itemCount)
  66.                                 {
  67.                                         if(_items[childIndexLeft].CompareTo(_items[childIndexRight]) < 0)
  68.                                         {
  69.                                                 swapIndex = childIndexRight;
  70.                                         }
  71.                                 }
  72.  
  73.                                 if(item.CompareTo(_items[swapIndex]) < 0)
  74.                                         Swap(item, _items[swapIndex]);
  75.                                 else
  76.                                         return;
  77.                         }
  78.                         else
  79.                                 return;
  80.  
  81.                 }
  82.         }
  83.  
  84.         void SortUp(T item)
  85.         {
  86.                 int parentIndex = (item.HeapIndex - 1) / 2;
  87.  
  88.                 while(true)
  89.                 {
  90.                         T parentItem = _items[parentIndex];
  91.  
  92.                         if(item.CompareTo(parentItem) > 0)
  93.                         {
  94.                                 Swap(item, parentItem);
  95.                         }
  96.                         else
  97.                         {
  98.                                 break;
  99.                         }
  100.  
  101.                         parentIndex = (item.HeapIndex - 1) / 2;
  102.                 }
  103.         }
  104.  
  105.         void Swap(T itemA, T itemB)
  106.         {
  107.                 _items[itemA.HeapIndex] = itemB;
  108.                 _items[itemB.HeapIndex] = itemA;
  109.  
  110.                 int itemAIndex = itemA.HeapIndex;
  111.                 itemA.HeapIndex = itemB.HeapIndex;
  112.                 itemB.HeapIndex = itemAIndex;
  113.         }
  114. }
  115.  
  116. public interface IHeapItem<T> : IComparable<T>
  117. {
  118.         int HeapIndex
  119.         {
  120.                 get;
  121.                 set;
  122.         }
  123. }
RAW Paste Data
Top