2 using System.Collections.Generic;
11 class Heap<TKey, TValue> where TKey : IComparable
16 List<KeyValuePair<TKey, TValue>> list =
new List<KeyValuePair<TKey, TValue>>();
22 internal KeyValuePair<TKey, TValue> Top {
get {
return list[0]; } }
27 internal int Count {
get {
return list.Count; } }
34 internal void Push(TKey key, TValue value)
36 list.Add(
new KeyValuePair<TKey, TValue>(key, value));
37 int index = list.Count - 1;
38 while (index > 0 && list[index].Key.CompareTo(list[(index - 1) >> 1].Key) < 0)
40 Swap(index, (index - 1) >> 1);
41 index = (index - 1) >> 1;
49 internal KeyValuePair<TKey, TValue> Pop()
51 KeyValuePair<TKey, TValue> toReturn =
52 new KeyValuePair<TKey, TValue>(list[0].Key, list[0].Value);
53 list[0] = list[list.Count - 1];
54 list.RemoveAt(list.Count - 1);
60 int son1 = (index << 1) + 1;
61 int son2 = (index << 1) + 2;
62 if (son2 < list.Count)
64 int lessSon = list[son1].Key.CompareTo(list[son2].Key) > 0 ? son2 : son1;
65 if (list[index].Key.CompareTo(list[lessSon].Key) >= 0)
72 else if (son1 < list.Count)
74 if (list[index].Key.CompareTo(list[son1].Key) >= 0)
98 private void Swap(
int index1,
int index2)
100 KeyValuePair<TKey, TValue> pom = list[index1];
101 list[index1] = list[index2];
Heap data structure where values of items are ordered by their keys.