Daly的游戲人生

統計

隨筆 - 13
文章 - 0
評論 - 27
引用 - 0

常用鏈接

隨筆分類

隨筆檔案

開源項目

網絡資源

有價值的博客

_那誰_
DBANotes博客
kasicass
TimYang后端技術
vczh大神
云風的博客

閱讀排行榜

動態優先隊列

很多圖算法實現中都需要用到優先隊列，這些優先隊列需要能動態改變堆內對應元素的值，并更新堆。比如在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

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

只有注冊用戶登錄后才能發表評論。


相關文章: 高效的Timer實現紅黑樹的實現與討論動態優先隊列閑話STL與數據結構實現

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品