|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
internal class Heap : StorageObjectSort { private object[] items; public int Size { get; set; } = 0; public override IEnumerable<T> Sort<T>(IComparer<T> sortFunction, IEnumerable<T> collection) { List<T> objectList = collection.ToList(); Initialize(objectList.Count); objectList.ForEach(o => Insert(o, sortFunction)); objectList.Clear(); while (Size > 0) objectList.Add((T)Remove(sortFunction)); return objectList; } protected override void Insert<T>(object item, IComparer<T> sortFunction) { items[Size] = item; Size++; UpHeap(sortFunction); } protected override object Remove<T>(IComparer<T> sortFunction) { object buffer = items[0]; items[0] = null; Size--; DownHeap(sortFunction); return buffer; } private void Initialize(int count) { items = new object[count]; } private void Swap(int first, int second) { object buffer = items[first]; items[first] = items[second]; items[second] = buffer; } private int GetLeftChild(int index) { return GetRightChild(index) - 1; } private int GetRightChild(int index) { return 2 * (index + 1); } private int GetParent(int index) { return (index + 1) / 2 - 1; } private void UpHeap<T>(IComparer<T> sortFunction) { if (Size <= 1) return; int currentElement = Size - 1; int currentElementParent = GetParent(currentElement); while(currentElementParent >= 0 && sortFunction.Compare((T)items[currentElementParent], (T)items[currentElement]) > 0) { Swap(currentElement, currentElementParent); currentElement = currentElementParent; currentElementParent = GetParent(currentElement); } } private void DownHeap<T>(IComparer<T> sortFunction) { int currentIndex = 0; int leftChild = GetLeftChild(currentIndex); int rightChild = GetRightChild(currentIndex); while (leftChild < items.Length || rightChild < items.Length) { int smallerChild = GetSmallerChild<T>(sortFunction, leftChild, rightChild); if (smallerChild == -1) return; //There is no smaller child. if (items[currentIndex] == null || sortFunction.Compare((T)items[smallerChild], (T)items[currentIndex]) < 0) { Swap(smallerChild, currentIndex); currentIndex = smallerChild; leftChild = GetLeftChild(currentIndex); rightChild = GetRightChild(currentIndex); continue; } return; } } private int GetSmallerChild<T>(IComparer<T> sortFunction, int first, int second) { if (first >= items.Length) return second; else if (second >= items.Length) return first; else if (items[first] != null && items[second] == null) return first; else if (items[second] != null && items[first] == null) return second; else if (items[first] == null && items[second] == null) return -1; return (sortFunction.Compare((T)items[first], (T)items[second]) < 0) ? first : second; } } |