優先佇列，非堆莫屬。
一：堆結構
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
}
}