Microscopic Traffic Simulator
Heap.cs
Go to the documentation of this file.
1 using System;
2 using System.Collections.Generic;
3 
5 {
11  class Heap<TKey, TValue> where TKey : IComparable
12  {
16  List<KeyValuePair<TKey, TValue>> list = new List<KeyValuePair<TKey, TValue>>();
17 
18 
22  internal KeyValuePair<TKey, TValue> Top { get { return list[0]; } }
23 
27  internal int Count { get { return list.Count; } }
28 
34  internal void Push(TKey key, TValue value)
35  {
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)
39  {
40  Swap(index, (index - 1) >> 1);
41  index = (index - 1) >> 1;
42  }
43  }
44 
49  internal KeyValuePair<TKey, TValue> Pop()
50  {
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);
55  int index = 0;
56  bool end;
57  do
58  {
59  end = true;
60  int son1 = (index << 1) + 1;
61  int son2 = (index << 1) + 2;
62  if (son2 < list.Count)
63  {
64  int lessSon = list[son1].Key.CompareTo(list[son2].Key) > 0 ? son2 : son1;
65  if (list[index].Key.CompareTo(list[lessSon].Key) >= 0)
66  {
67  Swap(index, lessSon);
68  index = lessSon;
69  end = false;
70  }
71  }
72  else if (son1 < list.Count)
73  {
74  if (list[index].Key.CompareTo(list[son1].Key) >= 0)
75  {
76  Swap(index, son1);
77  index = son1;
78  end = false;
79  }
80  }
81  } while (!end);
82  return toReturn;
83  }
84 
88  internal void Clear()
89  {
90  list.Clear();
91  }
92 
98  private void Swap(int index1, int index2)
99  {
100  KeyValuePair<TKey, TValue> pom = list[index1];
101  list[index1] = list[index2];
102  list[index2] = pom;
103  }
104  }
105 }
Heap data structure where values of items are ordered by their keys.
Definition: Heap.cs:11