优先伫列，非堆莫属。
一：堆结构
1: 性质
堆是一种很松散的序结构树，只储存了父节点和孩子节点的大小关系，并不规定左右孩子的大小，不像排序树那样严格，又因为堆是一种完全二叉
树，设节点为 i, 则 i/2 是 i 的父节点，2i 是 i 的左孩子，2i+1 是 i 的右孩子，所以在实现方式上可以采用轻量级的阵列。
2：用途
如果大家玩过微软的 MSMQ 的话，我们发现它其实也是一个优先伫列，还有刚才说的抓取 url，不过很遗憾，为什么.net 类库中没有优先伫列，而 java1.5
中就已经支援了。
3：实现
<1>堆结构节点定义：
我们在每个节点上定义一个 level，表示该节点的优先顺序，也是构建堆时采取的依据。
1 ///
3 ///
4 private List
5
6 #region 堆节点定义
7 ///
9 ///
10 public class HeapNode
11 {
12 ///
14 ///
15 public T t { get; set; }
16
17 ///
19 ///
20 public int level { get; set; }
21
22 public HeapNode(T t, int level)
23 {
24 this.t = t;
25 this.level = level;
26 }
27
28 public HeapNode() { }
29 }
30 #endregion
<2> 入队操作
入队操作时我们要注意几个问题：
①：完全二叉树的构建操作是 “从上到下，从左到右” 的形式，所以入队的节点是放在阵列的最后，也就是树中叶子层的有序最右边空位。
②：当节点插入到最后时，有可能破坏了堆的性质，此时我们要进行 “上滤操作”，当然时间复杂度为 O(lgN) 。
当我将节点 “20” 插入到堆尾的时候，此时破坏了堆的性质，从图中我们可以清楚的看到节点 “20” 的整个上滤过程，有意思吧，还有一点
就是：获取插入节点的父亲节点的演算法是：parent=list.count/2-1 。这也得益于完全二叉树的特性。
1 #region 新增操作
2 ///
4 ///
5 public void Eequeue(T t, int level = 1)
6 {
7 //将当前节点追加到堆尾
8 nodeList.Add(new HeapNode(t, level));
9
10 //如果只有一个节点，则不需要进行筛操作
11 if (nodeList.Count == 1)
12 return;
13
14 //获取最后一个非叶子节点
15 int parent = nodeList.Count / 2 – 1;
16
17 //堆调整
18 UpHeapAdjust(nodeList, parent);
19 }
20 #endregion
21
22 #region 对堆进行上滤操作，使得满足堆性质
23 ///
25 ///
26 ///
27 /// 非叶子节点的之后指标（这里要注意：我们
28 /// 的筛操作时针对非叶节点的）
29 ///
30 public void UpHeapAdjust(List
31 {
32 while (parent >= 0)
33 {
34 //当前 index 节点的左孩子
35 var left = 2 * parent + 1;
36
37 //当前 index 节点的右孩子
38 var right = left + 1;
39
40 //parent 子节点中最大的孩子节点，方便于 parent 进行比较
41 //预设为 left 节点
42 var max = left;
43
44 //判断当前节点是否有右孩子
45 if (right < nodeList.Count)
46 {
47 //判断 parent 要比较的最大子节点
48 max = nodeList[left].level < nodeList[right].level ? right : left;
49 }
50
51 //如果 parent 节点小于它的某个子节点的话，此时筛操作
52 if (nodeList[parent].level < nodeList[max].level)
53 {
54 //子节点和父节点进行交换操作
55 var temp = nodeList[parent];
56 nodeList[parent] = nodeList[max];
57 nodeList[max] = temp;
58
59 //继续进行更上一层的过滤
60 parent = (int)Math.Ceiling(parent / 2d) - 1;
61 }
62 else
63 {
64 break;
65 }
66 }
67 }
68 #endregion
<3> 出队操作
从图中我们可以看出，优先顺序最大的节点会在一阵痉挛后上升到堆顶，出队操作时，我们采取的方案是：弹出堆顶元素，然后将叶子层中
的最右子节点赋给堆顶，同样这时也会可能存在破坏堆的性质，最后我们要被迫进行下滤操作。
我图中可以看出：首先将堆顶 20 弹出，然后将 7 赋给堆顶，此时堆性质遭到破坏，最后我们清楚的看到节点 7 的下滤过程，从摊还分析的角度上
来说，下滤的层数不超过 2-3 层，所以整体上来说出队的时间复杂度为一个常量 O(1) 。
1 #region 优先伫列的出队操作
2 ///
4 ///
5 ///
6 public HeapNode Dequeue()
7 {
8 if (nodeList.Count == 0)
9 return null;
10
11 //出伫列操作，弹出资料头元素
12 var pop = nodeList[0];
13
14 //用尾元素填充头元素
15 nodeList[0] = nodeList[nodeList.Count – 1];
16
17 //删除尾节点
18 nodeList.RemoveAt(nodeList.Count – 1);
19
20 //然后从根节点下滤堆
21 DownHeapAdjust(nodeList, 0);
22
23 return pop;
24 }
25 #endregion
26
27 #region 对堆进行下滤操作，使得满足堆性质
28 ///
30 ///
31 ///
32 /// 非叶子节点的之后指标（这里要注意：我们
33 /// 的筛操作时针对非叶节点的）
34 ///
35 public void DownHeapAdjust(List
36 {
37 while (2 * parent + 1 < nodeList.Count)
38 {
39 //当前 index 节点的左孩子
40 var left = 2 * parent + 1;
41
42 //当前 index 节点的右孩子
43 var right = left + 1;
44
45 //parent 子节点中最大的孩子节点，方便于 parent 进行比较
46 //预设为 left 节点
47 var max = left;
48
49 //判断当前节点是否有右孩子
50 if (right < nodeList.Count)
51 {
52 //判断 parent 要比较的最大子节点
53 max = nodeList[left].level < nodeList[right].level ? right : left;
54 }
55
56 //如果 parent 节点小于它的某个子节点的话，此时筛操作
57 if (nodeList[parent].level < nodeList[max].level)
58 {
59 //子节点和父节点进行交换操作
60 var temp = nodeList[parent];
61 nodeList[parent] = nodeList[max];
62 nodeList[max] = temp;
63
64 //继续进行更下一层的过滤
65 parent = max;
66 }
67 else
68 {
69 break;
70 }
71 }
72 }
73 #endregion
最后我还扩充套件了一个弹出并下降节点优先顺序的方法，好吧，这个方法大家自己琢磨琢磨，很有意思的，实际应用中使用到了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;
namespace ConsoleApplication2
{
public class Program
{
public static void Main()
{
PriorityQueue
//随机插入 20 个节点
for (int i = 1; i < 20; i++)
{
var rand = new Random().Next(1, 20);
Thread.Sleep(10);
heap.Eequeue(new Url() { Data = "test" + i }, i);
}
while (true)
{
var node = heap.Dequeue();
if (node == null)
break;
Console.WriteLine("当前 url 的优先顺序为:{0}, 资料为:{1}", node.level, node.t.Data);
}
Console.Read();
}
}
#region 定义一个实体
///
///
public class Url
{
public string Data { get; set; }
}
#endregion
public class PriorityQueue
{
///
///
private List
#region 堆节点定义
///
///
public class HeapNode
{
///
///
public T t { get; set; }
///
///
public int level { get; set; }
public HeapNode(T t, int level)
{
this.t = t;
this.level = level;
}
public HeapNode() { }
}
#endregion
#region 新增操作
///
///
public void Eequeue(T t, int level = 1)
{
//将当前节点追加到堆尾
nodeList.Add(new HeapNode(t, level));
//如果只有一个节点，则不需要进行筛操作
if (nodeList.Count == 1)
return;
//获取最后一个非叶子节点
int parent = nodeList.Count / 2 – 1;
//堆调整
UpHeapAdjust(nodeList, parent);
}
#endregion
#region 对堆进行上滤操作，使得满足堆性质
///
///
///
/// 非叶子节点的之后指标（这里要注意：我们
/// 的筛操作时针对非叶节点的）
///
public void UpHeapAdjust(List
{
while (parent >= 0)
{
//当前 index 节点的左孩子
var left = 2 * parent + 1;
//当前 index 节点的右孩子
var right = left + 1;
//parent 子节点中最大的孩子节点，方便于 parent 进行比较
//预设为 left 节点
var max = left;
//判断当前节点是否有右孩子
if (right < nodeList.Count)
{
//判断 parent 要比较的最大子节点
max = nodeList[left].level < nodeList[right].level ? right : left;
}
//如果 parent 节点小于它的某个子节点的话，此时筛操作
if (nodeList[parent].level < nodeList[max].level)
{
//子节点和父节点进行交换操作
var temp = nodeList[parent];
nodeList[parent] = nodeList[max];
nodeList[max] = temp;
//继续进行更上一层的过滤
parent = (int)Math.Ceiling(parent / 2d) - 1;
}
else
{
break;
}
}
}
#endregion
#region 优先伫列的出队操作
///
///
///
public HeapNode Dequeue()
{
if (nodeList.Count == 0)
return null;
//出伫列操作，弹出资料头元素
var pop = nodeList[0];
//用尾元素填充头元素
nodeList[0] = nodeList[nodeList.Count – 1];
//删除尾节点
nodeList.RemoveAt(nodeList.Count – 1);
//然后从根节点下滤堆
DownHeapAdjust(nodeList, 0);
return pop;
}
#endregion
#region 对堆进行下滤操作，使得满足堆性质
///
///
///
/// 非叶子节点的之后指标（这里要注意：我们 /// //获取头元素 //设定指定优先顺序（如果为 MinValue 则为 — 操作） //下滤堆 return nodeList[0]; #region 获取元素并下降优先顺序 ///
/// 的筛操作时针对非叶节点的）
///
public void DownHeapAdjust(List
{
while (2 * parent + 1 < nodeList.Count)
{
//当前 index 节点的左孩子
var left = 2 * parent + 1;
//当前 index 节点的右孩子
var right = left + 1;
//parent 子节点中最大的孩子节点，方便于 parent 进行比较
//预设为 left 节点
var max = left;
//判断当前节点是否有右孩子
if (right < nodeList.Count)
{
//判断 parent 要比较的最大子节点
max = nodeList[left].level < nodeList[right].level ? right : left;
}
//如果 parent 节点小于它的某个子节点的话，此时筛操作
if (nodeList[parent].level < nodeList[max].level)
{
//子节点和父节点进行交换操作
var temp = nodeList[parent];
nodeList[parent] = nodeList[max];
nodeList[max] = temp;
//继续进行更下一层的过滤
parent = max;
}
else
{
break;
}
}
}
#endregion
#region 获取元素并下降到指定的 level 级别
///
///
public HeapNode GetAndDownPriority(int level)
{
if (nodeList.Count == 0)
return null;
var pop = nodeList[0];
nodeList[0].level = level == int.MinValue ? –nodeList[0].level : level;
DownHeapAdjust(nodeList, 0);
}
#endregion
///
///
public HeapNode GetAndDownPriority()
{
//下降一个优先顺序
return GetAndDownPriority(int.MinValue);
}
#endregion
}
}