*miscHEADmaster

1 files changed, 160 insertions, 0 deletions

diff --git a/Assets/CollectionsExt/MinHeap.cs b/Assets/CollectionsExt/MinHeap.cs
new file mode 100644
index 0000000..68ddabb
--- /dev/null
+++ b/Assets/CollectionsExt/MinHeap.cs
@@ -0,0 +1,160 @@
+using System;
+using System.Collections.Generic;
+
+namespace CollectionsExt
+{
+    // 最小堆，堆顶是最小值。
+    // 如果需要维护一个优先队列，用堆结构，调堆的效率是O(logn)快于遍历的O(n)
+    public class MinHeap<T>
+    {
+        private const int InitialCapacity = 4;
+
+        private T[] _arr;
+        private int _lastItemIndex;
+        private IComparer<T> _comparer;
+
+        public MinHeap()
+            : this(InitialCapacity, Comparer<T>.Default)
+        {
+        }
+
+        public MinHeap(int capacity)
+            : this(capacity, Comparer<T>.Default)
+        {
+        }
+
+        public MinHeap(Comparison<T> comparison)
+            : this(InitialCapacity, Comparer<T>.Create(comparison))
+        {
+        }
+
+        public MinHeap(IComparer<T> comparer)
+            : this(InitialCapacity, comparer)
+        {
+        }
+
+        public MinHeap(int capacity, IComparer<T> comparer)
+        {
+            _arr = new T[capacity];
+            _lastItemIndex = -1;
+            _comparer = comparer;
+        }
+
+        public int Count
+        {
+            get
+            {
+                return _lastItemIndex + 1;
+            }
+        }
+
+        public void Add(T item)
+        {
+            if (_lastItemIndex == _arr.Length - 1)
+            {
+                Resize();
+            }
+
+            _lastItemIndex++;
+            _arr[_lastItemIndex] = item;
+
+            MinHeapifyUp(_lastItemIndex);
+        }
+
+        public T Remove()
+        {
+            if (_lastItemIndex == -1)
+            {
+                throw new InvalidOperationException("The heap is empty");
+            }
+
+            T removedItem = _arr[0];
+            _arr[0] = _arr[_lastItemIndex];
+            _lastItemIndex--;
+
+            MinHeapifyDown(0);
+
+            return removedItem;
+        }
+
+        public T Peek()
+        {
+            if (_lastItemIndex == -1)
+            {
+                throw new InvalidOperationException("The heap is empty");
+            }
+
+            return _arr[0];
+        }
+
+        public void Clear()
+        {
+            _lastItemIndex = -1;
+        }
+
+        // 调堆,O(logn)
+        private void MinHeapifyUp(int index)
+        {
+            if (index == 0)
+            {
+                return;
+            }
+
+            int childIndex = index;
+            int parentIndex = (index - 1) / 2;
+
+            // 堆顶是最小值
+            if (_comparer.Compare(_arr[childIndex], _arr[parentIndex]) < 0)
+            {
+                // swap the parent and the child
+                T temp = _arr[childIndex];
+                _arr[childIndex] = _arr[parentIndex];
+                _arr[parentIndex] = temp;
+
+                // 递归
+                MinHeapifyUp(parentIndex);
+            }
+        }
+
+        // 调堆,O(logn)
+        private void MinHeapifyDown(int index)
+        {
+            int leftChildIndex = index * 2 + 1;
+            int rightChildIndex = index * 2 + 2;
+            int smallestItemIndex = index; // The index of the parent
+
+            if (leftChildIndex <= _lastItemIndex &&
+                _comparer.Compare(_arr[leftChildIndex], _arr[smallestItemIndex]) < 0)
+            {
+                smallestItemIndex = leftChildIndex;
+            }
+
+            if (rightChildIndex <= _lastItemIndex &&
+                _comparer.Compare(_arr[rightChildIndex], _arr[smallestItemIndex]) < 0)
+            {
+                smallestItemIndex = rightChildIndex;
+            }
+
+            if (smallestItemIndex != index)
+            {
+                // swap the parent with the smallest of the child items
+                T temp = _arr[index];
+                _arr[index] = _arr[smallestItemIndex];
+                _arr[smallestItemIndex] = temp;
+
+                MinHeapifyDown(smallestItemIndex);
+            }
+        }
+
+        private void Resize()
+        {
+            T[] newArr = new T[_arr.Length * 2];
+            for (int i = 0; i < _arr.Length; i++)
+            {
+                newArr[i] = _arr[i];
+            }
+
+            _arr = newArr;
+        }
+    }
+}