C# 우선순위 큐

Heap.cs

class Heap { int _lastIndex = -1; int _capacity = 0; HeapItem[] _array = new HeapItem[0]; public bool IsEmpty{get {return _lastIndex == -1;}} public int RemainItems { get { return _lastIndex + 1; } } public Heap() { } public void InsertItem(HeapItem item) { if(_lastIndex +1 == _capacity) { _capacity += 2; Array.Resize(ref _array, _capacity); } _array[++_lastIndex] = item; int currentPosition = _lastIndex; int parentPosition = getParentIndex(currentPosition); while (currentPosition > 0 && (_array[currentPosition].Ranking < _array[parentPosition].Ranking)) { itemSwap(currentPosition, parentPosition); currentPosition = parentPosition; parentPosition = getParentIndex(currentPosition); } } public HeapItem DeleteItem() { if (IsEmpty) return null; HeapItem root = _array[0]; _array[0] = _array[_lastIndex]; _array[_lastIndex] = null; _lastIndex--; int parent = 0; int leftChild = getLeftChild(parent); int rightChild = leftChild + 1; while (true) { int selectedChild = 0; if (leftChild > _lastIndex) break; if (rightChild > _lastIndex) selectedChild = leftChild; else { if (_array[leftChild].Ranking > _array[rightChild].Ranking) selectedChild = rightChild; else selectedChild = leftChild; } if (_array[selectedChild].Ranking < _array[parent].Ranking) { itemSwap(selectedChild, parent); parent = selectedChild; } else break; leftChild = getLeftChild(parent); rightChild = leftChild + 1; } if (_lastIndex < _capacity / 2) { _capacity /= 2; Array.Resize(ref _array, _capacity); } return root; } public void PrintHeap() { foreach(HeapItem item in _array) { if(item != null) Console.WriteLine(string.Format("{0}, {1}", item.Ranking, item.Value)); } Console.WriteLine(); } private void itemSwap(int index0, int index1) { HeapItem item = _array[index0]; _array[index0] = _array[index1]; _array[index1] = item; } private int getLeftChild(int parent) { return 2 * parent + 1; } private int getRightChild(int parent) { return 2 * parent + 2; } private int getParentIndex(int childPosition) { return (childPosition - 1) / 2; } }

HeapItem.cs

class HeapItem { public int Ranking { get; set; } public object Value { get; set; } public HeapItem(int rank, object value) { this.Ranking = rank; this.Value = value; } }

사용

Heap h = new Heap(); h.InsertItem(new HeapItem(111, "화장실")); h.InsertItem(new HeapItem(1, "밥")); h.InsertItem(new HeapItem(10, "청소")); while (true) { HeapItem item = h.DeleteItem(); if (item == null) break; } h.InsertItem(new HeapItem(111, "화장실")); h.InsertItem(new HeapItem(1, "밥")); h.InsertItem(new HeapItem(10, "청소"));