動態優先隊列
很多圖算法實現中都需要用到優先隊列,這些優先隊列需要能動態改變堆內對應元素的值,并更新堆。比如在dijkstra算法中,每次松弛都要更新頂點的權值,但一般的優先隊列無法找到頂點在堆中的位置。本文實現一種數據結構"動態優先隊列",利用兩個數組保存了原數據數組位置----堆位置的映射,能實現快速修改。該數據結構的大部分應用場合中,元素個數是固定的,因此代碼中沒有追加新元素的操作。代碼和大部分堆操作一樣,m_indices數組保存了原數組 到 堆位置映射, m_pmap保存了逆向映射。堆調整時,原數組的數據位置不變,只改變m_pmap映射。該實現是最小優先隊列,在模板參數添加用于比較的Functor可改造為任意堆。
1
template<typename _Type>
2
static void gs_swap(_Type &x, _Type &y)
3

{
4
static _Type tmp;
5
tmp = x;
6
x = y;
7
y = tmp;
8
}
9
10
11
/**//**
12
* DynamicPQ : dynamic priority queue (with indices mapping to original array position)
13
* It's a min-heap and has following feature
14
* 1. detemine the min value
15
* 2. modify the corresponding k in original array
16
* 3. pop the top value
17
* it can't be append new value
18
*/
19
template<typename _Type>
20
class DynamicPQ
21

{
22
public:
23
/**//**
24
* @param array the original array to processed
25
* @param max_n the original size of the array
26
*/
27
DynamicPQ(_Type *array, unsigned int max_n)
28
: m_array(array), m_size(max_n)
29
{
30
unsigned int i;
31
m_indices = new unsigned int[max_n];
32
m_pmap = new unsigned int[max_n];
33
for (i=0; i<m_size; i++)
{
34
m_indices[i] = m_pmap[i] = i;
35
}
36
//make_heap
37
for (i=m_size/2; i>0; i--)
{
38
adjust_down(i);
39
}
40
adjust_down(0);
41
}
42
43
~DynamicPQ()
{
44
delete[] m_indices;
45
delete[] m_pmap;
46
}
47
/**//**
48
* change the key
49
* @param k the original index, not the position of the min-heap
50
* @param value new value
51
*/
52
void modify_key(unsigned int k, _Type value)
53
{
54
unsigned int idx = m_indices[k]; //find the coresponding position of the heap
55
if (value < m_array[ m_pmap[idx] ])
{
56
m_array[ m_pmap[idx] ] = value; //decrease key
57
adjust_up(idx);
58
}
59
else
{
60
m_array[ m_pmap[idx] ] = value; //increase key
61
adjust_down(idx);
62
}
63
}
64
_Type top()
{ return m_array[ m_pmap[0] ];}
65
/**//**
66
* extract the min value
67
*/
68
_Type pop_top()
{
69
gs_swap(m_pmap[0], m_pmap[m_size-1]);
70
m_indices[ m_pmap[0] ] = m_size - 1;
71
m_indices[ m_pmap[m_size-1] ] = 0;
72
--m_size;
73
adjust_down(0);
74
return m_array[ m_pmap[m_size]];
75
}
76
inline unsigned int size()
{ return m_size; }
77
78
protected:
79
//update the value. up to the root
80
void adjust_up(unsigned int i)
81
{
82
unsigned int parent = (i-1) / 2;
83
while (i>0 && m_array[ m_pmap[i] ] < m_array[ m_pmap[parent] ])
{
84
gs_swap(m_pmap[i], m_pmap[parent]);
85
m_indices[ m_pmap[i]] = i; //update index mapping after exchange
86
i = parent;
87
parent = (i-1) / 2;
88
}
89
m_indices[ m_pmap[i] ] = i; //update the final position of i
90
}
91
//min-heapify
92
void adjust_down(unsigned int i)
93
{
94
unsigned int lf = i*2 + 1; //left child
95
unsigned int rt = i*2 + 2; //right child
96
unsigned int min_pos;
97
unsigned int tmp_i = m_pmap[i];
98
while(lf < m_size)
{
99
if (m_array[ m_pmap[lf] ] < m_array[ m_pmap[i] ])
100
min_pos = lf;
101
else
102
min_pos = i;
103
if (rt < m_size && m_array[ m_pmap[rt] ] < m_array[ m_pmap[min_pos] ])
{
104
min_pos = rt;
105
}
106
if (min_pos != i)
{
107
gs_swap(m_pmap[min_pos], m_pmap[i]);
108
m_indices[ m_pmap[i]] = i; //update after exchange
109
i = min_pos; //next loop
110
lf = i*2 + 1;
111
rt = i*2 + 2;
112
continue;
113
}
114
else
{
115
m_indices[tmp_i] = i; //update index
116
break;
117
}
118
}
119
}
120
121
protected:
122
_Type *m_array;
123
unsigned int *m_indices; //index mapping(array[k] --> heap position)
124
unsigned int *m_pmap; //pointer mapping(heap position --> array[k])
125
unsigned int m_size;
126
};
127
template<typename _Type>2
static void gs_swap(_Type &x, _Type &y)3


{ 4
static _Type tmp;5
tmp = x;6
x = y;7
y = tmp;8
}9

10

11

/**//** 12
* DynamicPQ : dynamic priority queue (with indices mapping to original array position)13
* It's a min-heap and has following feature14
* 1. detemine the min value15
* 2. modify the corresponding k in original array16
* 3. pop the top value17
* it can't be append new value18
*/ 19
template<typename _Type>20
class DynamicPQ21


{22
public:23

/**//** 24
* @param array the original array to processed25
* @param max_n the original size of the array26
*/27
DynamicPQ(_Type *array, unsigned int max_n)28
: m_array(array), m_size(max_n)29

{30
unsigned int i;31
m_indices = new unsigned int[max_n];32
m_pmap = new unsigned int[max_n];33

for (i=0; i<m_size; i++)
{34
m_indices[i] = m_pmap[i] = i;35
}36
//make_heap37

for (i=m_size/2; i>0; i--)
{38
adjust_down(i);39
}40
adjust_down(0);41
}42

43

~DynamicPQ()
{44
delete[] m_indices;45
delete[] m_pmap;46
}47

/**//** 48
* change the key49
* @param k the original index, not the position of the min-heap50
* @param value new value51
*/52
void modify_key(unsigned int k, _Type value)53

{54
unsigned int idx = m_indices[k]; //find the coresponding position of the heap55

if (value < m_array[ m_pmap[idx] ])
{56
m_array[ m_pmap[idx] ] = value; //decrease key57
adjust_up(idx);58
}59

else
{60
m_array[ m_pmap[idx] ] = value; //increase key61
adjust_down(idx);62
}63
}64

_Type top()
{ return m_array[ m_pmap[0] ];}65

/**//** 66
* extract the min value67
*/68

_Type pop_top()
{69
gs_swap(m_pmap[0], m_pmap[m_size-1]);70
m_indices[ m_pmap[0] ] = m_size - 1;71
m_indices[ m_pmap[m_size-1] ] = 0;72
--m_size;73
adjust_down(0); 74
return m_array[ m_pmap[m_size]];75
}76

inline unsigned int size()
{ return m_size; }77

78
protected:79
//update the value. up to the root80
void adjust_up(unsigned int i)81

{82
unsigned int parent = (i-1) / 2;83

while (i>0 && m_array[ m_pmap[i] ] < m_array[ m_pmap[parent] ])
{84
gs_swap(m_pmap[i], m_pmap[parent]);85
m_indices[ m_pmap[i]] = i; //update index mapping after exchange86
i = parent;87
parent = (i-1) / 2;88
}89
m_indices[ m_pmap[i] ] = i; //update the final position of i90
}91
//min-heapify92
void adjust_down(unsigned int i)93

{94
unsigned int lf = i*2 + 1; //left child95
unsigned int rt = i*2 + 2; //right child96
unsigned int min_pos;97
unsigned int tmp_i = m_pmap[i];98

while(lf < m_size)
{ 99
if (m_array[ m_pmap[lf] ] < m_array[ m_pmap[i] ]) 100
min_pos = lf;101
else 102
min_pos = i;103

if (rt < m_size && m_array[ m_pmap[rt] ] < m_array[ m_pmap[min_pos] ])
{104
min_pos = rt;105
}106

if (min_pos != i)
{107
gs_swap(m_pmap[min_pos], m_pmap[i]);108
m_indices[ m_pmap[i]] = i; //update after exchange109
i = min_pos; //next loop110
lf = i*2 + 1;111
rt = i*2 + 2;112
continue;113
}114

else
{115
m_indices[tmp_i] = i; //update index116
break;117
}118
}119
}120
121
protected:122
_Type *m_array; 123
unsigned int *m_indices; //index mapping(array[k] --> heap position)124
unsigned int *m_pmap; //pointer mapping(heap position --> array[k])125
unsigned int m_size;126
};127

posted on 2009-11-17 11:38 Daly 閱讀(1011) 評論(0) 編輯 收藏 引用 所屬分類: 數據結構與算法

