[8527] | 1 |
|
---|
| 2 | using System;
|
---|
| 3 | using System.Collections.Generic;
|
---|
| 4 | using HeuristicLab.Algorithms.GraphRouting.Interfaces;
|
---|
| 5 | namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
|
---|
[8541] | 6 | public sealed class BinaryHeap<K, V> : IHeap<K, V>
|
---|
[8527] | 7 | where K : IComparable
|
---|
| 8 | where V : IComparable {
|
---|
| 9 | private class HeapElement {
|
---|
| 10 | public K Key { get; set; }
|
---|
| 11 | public V Value { get; set; }
|
---|
| 12 | }
|
---|
| 13 |
|
---|
| 14 | private int capacity;
|
---|
| 15 | private int size;
|
---|
| 16 | private HeapElement[] data;
|
---|
| 17 |
|
---|
[8541] | 18 | public BinaryHeap(int cap) {
|
---|
[8527] | 19 | size = 0;
|
---|
| 20 | capacity = cap;
|
---|
| 21 | data = new HeapElement[capacity];
|
---|
| 22 | }
|
---|
| 23 |
|
---|
| 24 | public int Size {
|
---|
| 25 | get { return size; }
|
---|
| 26 | }
|
---|
| 27 |
|
---|
| 28 | public void Insert(K key, V value) {
|
---|
| 29 | HeapElement elem = new HeapElement();
|
---|
| 30 | elem.Key = key;
|
---|
| 31 | elem.Value = value;
|
---|
| 32 | data[size] = elem;
|
---|
| 33 | HeapifyDown(size);
|
---|
| 34 | size++;
|
---|
| 35 | }
|
---|
| 36 |
|
---|
| 37 | public KeyValuePair<K, V> PeekMin() {
|
---|
| 38 | if (size == 0) {
|
---|
| 39 | throw new InvalidOperationException("Heap is empty");
|
---|
| 40 | }
|
---|
| 41 | return new KeyValuePair<K, V>(data[0].Key, data[0].Value);
|
---|
| 42 | }
|
---|
| 43 |
|
---|
| 44 | public K PeekMinKey() {
|
---|
| 45 | return data[0].Key;
|
---|
| 46 | }
|
---|
| 47 |
|
---|
| 48 | public V PeekMinValue() {
|
---|
| 49 | return data[0].Value;
|
---|
| 50 | }
|
---|
| 51 |
|
---|
| 52 | public void RemoveMin() {
|
---|
| 53 | RemoveAt(0);
|
---|
| 54 | }
|
---|
| 55 |
|
---|
| 56 | public void DecreaseKey(K key, V value) {
|
---|
| 57 | for (int i = 0; i < size; i++) {
|
---|
| 58 | if (data[i].Value.CompareTo(value) == 0) {
|
---|
| 59 | RemoveAt(i);
|
---|
| 60 | Insert(key, value);
|
---|
| 61 | break;
|
---|
| 62 | }
|
---|
| 63 | }
|
---|
| 64 | }
|
---|
| 65 |
|
---|
| 66 | private void RemoveAt(int idx) {
|
---|
| 67 | if (size == 1) {
|
---|
| 68 | size--;
|
---|
| 69 | } else {
|
---|
| 70 | if (idx < size - 1) {
|
---|
| 71 | Swap(idx, size - 1);
|
---|
| 72 | HeapifyUp(idx);
|
---|
| 73 | }
|
---|
| 74 | size--;
|
---|
| 75 | }
|
---|
| 76 | }
|
---|
| 77 |
|
---|
| 78 | private void HeapifyDown(int start) {
|
---|
| 79 | int i = start;
|
---|
| 80 | int j = (i - 1) / 2;
|
---|
| 81 | while (i > 0 && (data[i].Key.CompareTo(data[j].Key) == -1)) {
|
---|
| 82 | Swap(i, j);
|
---|
| 83 | i = j;
|
---|
| 84 | j = (i - 1) / 2;
|
---|
| 85 | }
|
---|
| 86 | }
|
---|
| 87 |
|
---|
| 88 | private void HeapifyUp(int start) {
|
---|
| 89 | int idx = start;
|
---|
| 90 | int left = 2 * idx + 1;
|
---|
| 91 | int right = 2 * idx + 2;
|
---|
| 92 | while ((left < size - 1 && data[idx].Key.CompareTo(data[left].Key) != -1) ||
|
---|
| 93 | (right < size - 1 && data[idx].Key.CompareTo(data[right].Key) != -1)) {
|
---|
[8539] | 94 | if ((right >= size - 1) || (data[left].Key.CompareTo(data[right].Key) == -1)) {
|
---|
[8527] | 95 | Swap(left, idx);
|
---|
| 96 | idx = left;
|
---|
| 97 | } else {
|
---|
| 98 | Swap(right, idx);
|
---|
| 99 | idx = right;
|
---|
| 100 | }
|
---|
| 101 | left = 2 * idx + 1;
|
---|
| 102 | right = 2 * idx + 2;
|
---|
| 103 | }
|
---|
| 104 | }
|
---|
| 105 |
|
---|
| 106 | private void Swap(int i, int j) {
|
---|
| 107 | var elem = data[i];
|
---|
| 108 | data[i] = data[j];
|
---|
| 109 | data[j] = elem;
|
---|
| 110 | }
|
---|
| 111 | }
|
---|
| 112 | }
|
---|