在《
基于双端堆实现的优先级队列（1）：原理》一文中讲述了双端堆的相关原理，本文则详细讲述具体的内部实现，便于区分，内部函数名称都以双下划线作为前缀，在这里，有几个关键问题需要说明
1）怎么求一个结点的对称结点：如果完全二叉树根结点从索引1开始但不存储元素，那么最小堆根结点则在索引2，最大堆根结点则在索引3，4和5为2的左右孩子，6和7为3的左右孩子，依次排下来，可以发现2(00000010)^1(00000001)=3(000000011)，3(00000011)^1(00000001)=2，4(00000100)^2(00000010)=6(00000110)，6(00000110)^2(00000010)=4(00000100)，......因此，使用异或运算就可求得对称结点，问题的关键变为如何求得另一操作数如 和2,3异或的1，和4,6异或的2，这个1，2正是2(3)，4(6)的以2为底的整数对数（向下取整）值，而这个值可以使用位运算来高效地完成。这里的索引有效范围是非负数。
2）怎么判断结点在最小堆或最大堆内：由1）分析，显而易见可得，2(00000010)&1(00000001)=0,3(00000011)&1(00000001)=1,4(00000100)&2(00000010)=0,6(00000110)&2(00000010)=2,......因此，可以使用与运算来高效地判断。
3）为了充分利用空间，我的实现是最小堆根结点在索引0，最大堆根结点在索引1处，那么在这种情况下，解决以上问题1），就需要将结点索引先加2，再从结果中减去2；解决以上问题2）需要将结点索引加2即可。当双端堆元素数量占尽全部空间容量时，次最大索引为空间容量减2，加2可能导致整数溢出，因此在实现中须区分处理。
下面是双端堆操作算法的内部函数实现
1、 以2为底的整数对数（向下取整）
1
struct _64bit_int
{};
2struct _no_64bit_int{};
3
4template<typename _Distance>
5inline _Distance __log2(_Distance _val,_no_64bit_int)
6{
7
assert(_val > 0);
8
9 _Distance _ret = 0, _tmp;
10
_tmp = _val >> 16; if (_tmp) { _ret += 16; _val = _tmp;}
11 _tmp = _val >> 8; if (_tmp) { _ret += 8; _val = _tmp; }
12 _tmp = _val >> 4; if (_tmp) { _ret += 4; _val = _tmp; }
13 _tmp = _val >> 2; if (_tmp) { _ret += 2; _val = _tmp; }
14 _ret += (_val >> 1);
15
16 return _ret;
17
}
18
19template<typename _Distance>
20inline _Distance __log2(_Distance _val,_64bit_int)
21{
22 assert(_val > 0);
23
24 _Distance _ret = 0, _tmp;
25 _tmp = _val >> 32; if (_tmp) { _ret += 32; _val = _tmp;}
26 _tmp = _val >> 16; if (_tmp) { _ret += 16; _val = _tmp;}
27 _tmp = _val >> 8; if (_tmp) { _ret += 8; _val = _tmp; }
28 _tmp = _val >> 4; if (_tmp) { _ret += 4; _val = _tmp; }
29 _tmp = _val >> 2; if (_tmp) { _ret += 2; _val = _tmp; }
30 _ret += (_val >> 1);
31
32 return _ret;
33}
34
35template<typename _Distance>
36inline _Distance __log2(_Distance val)
37{
38 return __log2(val,typename cppext::mpl::if_then_else<8==sizeof(_Distance),_64bit_int,_no_64bit_int>::type());
39}
2、对称结点计算和判断函数
1
template<typename _Distance>
2inline bool __is_max_dheap_until(_Distance _dist)
3
{
4
assert(_dist > 1);
5 return 0!=(_dist&(((_Distance)1)<<(__log2(_dist)-1)));
6
}
7
8template<typename _Distance>
9inline bool __is_max_dheap(_Distance _dist)
10{
11 _Distance _tmp = _dist + 2;
12 return _tmp > _dist ? __is_max_dheap_until(_tmp) : __is_max_dheap_until((_dist>>1) - 1);
13}
14
15template<typename _Distance>
16inline _Distance __partner_dheap_until(_Distance _dist)
17{
18 assert(_dist > 1);
19 return _dist^(((_Distance)1)<<(__log2(_dist)-1));
20}
21
22template<typename _Distance>
23inline _Distance __partner_dheap(_Distance _dist)
24{
25 _Distance _tmp = _dist + 2;
26 return _tmp > _dist ? __partner_dheap_until(_tmp) - 2 : __partner_dheap_until((_dist>>1) - 1) - 2;
27}
3、最大堆最小堆的插入
1template<typename _RandIt,typename _Distance,typename _Ty>
2inline void __push_min_dheap(_RandIt _first,_Distance _hole,_Distance _top,_Ty _val,bool _flag = true)
3{
4 for (_Distance _parent;_hole > _top;)
5
{
6 _parent = (_hole - 2) >> 1;
7 if (!_flag && _parent == _top || *(_first + _parent) < _val)
8 break;
9 *(_first + _hole) = *(_first + _parent);
10 _hole = _parent;
11
}
12 *(_first + _hole) = _val;
13}
14
15template<typename _RandIt,typename _Distance,typename _Ty,typename _Compare>
16inline void __push_min_dheap(_RandIt _first,_Distance _hole,_Distance _top,_Ty _val,_Compare _comp,bool _flag = true)
17{
18 for (_Distance _parent;_hole > _top;)
19 {
20 _parent = (_hole - 2) >> 1;
21 if (!_flag && _parent == _top || _comp(*(_first + _parent),_val))
22 break;
23 *(_first + _hole) = *(_first + _parent);
24 _hole = _parent;
25 }
26 *(_first + _hole) = _val;
27}
28
29template<typename _RandIt,typename _Distance,typename _Ty>
30inline void __push_max_dheap(_RandIt _first,_Distance _hole,_Distance _top,_Ty _val,bool _flag = true)
31{
32 for (_Distance _parent;_hole > _top;)
33 {
34 _parent = (_hole - 2) >> 1;
35 if (!_flag && _parent == _top || _val < *(_first + _parent))
36 break;
37 *(_first + _hole) = *(_first + _parent);
38 _hole = _parent;
39 }
40 *(_first + _hole) = _val;
41}
42
43template<typename _RandIt,typename _Distance,typename _Ty,typename _Compare>
44inline void __push_max_dheap(_RandIt _first,_Distance _hole,_Distance _top,_Ty _val,_Compare _comp,bool _flag = true)
45{
46 for (_Distance _parent;_hole > _top;)
47 {
48 _parent = (_hole - 2) >> 1;
49 if (!_flag && _parent == _top || _comp(_val,*(_first + _parent)))
50 break;
51 *(_first + _hole) = *(_first + _parent);
52 _hole = _parent;
53 }
54 *(_first + _hole) = _val;
55}
4、最大堆调整
1template<typename _RandIt,typename _Distance,typename _Ty>
2inline void __adjust_max_dheap(_RandIt _first,_Distance _len,_Distance _hole,_Ty _val,bool _flag = true)
3{
4 assert(_len > 0);
5
6 _Distance _parent,_child,_tmp,_part,_min,_max,_bottom = _len - 1, _half = _bottom >> 1;
7 for(_parent = _hole;_parent < _half;)
8 {
9 _child = (_parent + 1) << 1;
10 if (_child < _bottom)
11 {
12 _tmp = _child;
13 if (++_tmp <= _bottom && *(_first + _child) < *(_first + _tmp))
14 ++_child;
15 }
16 *(_first + _parent) = *(_first + _child);
17 _parent = _child;
18 }
19
20 _part = __partner_dheap(_parent),_tmp = (_part + 1) << 1;
21 if(_tmp != _bottom)
22 {
23 if (_tmp < _bottom)
24 _part = _tmp, ++_tmp ;
25 else
26 (_part&1)==0 ? _tmp = _part + 1 : _tmp = _part - 1;
27
28 if (*(_first + _part) < *(_first + _tmp))
29 _min = _part,_max = _tmp;
30 else
31 _min = _tmp,_max = _part;
32 }
33 else
34 {
35 _min = _max = _tmp;
36 }
37
38 if (*(_first + _min) < _val)
39 {
40 if (_val < *(_first + _max))
41 {
42 if (*(_first + _parent) < *(_first + _max))
43 *(_first + ((_parent - 2) >> 1)) = *(_first + _max);
44 else
45 *(_first + _parent) = *(_first + _max);
46 *(_first + _max) = _val;
47 }
48 else
49 {
50 __push_max_dheap(_first,_parent,_hole,_val);
51 }
52 }
53 else
54 {
55 if (*(_first + _parent) < *(_first + _max))
56 *(_first + ((_parent - 2) >> 1)) = *(_first + _max);
57 else
58 *(_first + _parent) = *(_first + _max);
59 *(_first + _max) = *(_first + _min);
60 __push_min_dheap(_first,_min,__partner_dheap(_hole),_val,_flag);
61 }
62}
63
64template<typename _RandIt,typename _Distance,typename _Ty,typename _Compare>
65inline void __adjust_max_dheap(_RandIt _first,_Distance _len,_Distance _hole,_Ty _val,_Compare _comp,bool _flag = true)
66{
67 assert(_len > 0);
68
69 _Distance _parent,_child,_tmp,_part,_min,_max,_bottom = _len - 1, _half = _bottom >> 1;
70 for(_parent = _hole;_parent < _half;)
71 {
72 _child = (_parent + 1) << 1;
73 if (_child < _bottom)
74 {
75 _tmp = _child;
76 if (++_tmp <= _bottom && _comp(*(_first + _child),*(_first + _tmp)))
77 ++_child;
78 }
79 *(_first + _parent) = *(_first + _child);
80 _parent = _child;
81 }
82
83 _part = __partner_dheap(_parent),_tmp = (_part + 1) << 1;
84 if(_tmp != _bottom)
85 {
86 if (_tmp < _bottom)
87 _part = _tmp, ++_tmp;
88 else
89 (_part&1)==0 ? _tmp = _part + 1 : _tmp = _part - 1;
90
91 if (_comp(*(_first + _part),*(_first + _tmp)))
92 _min = _part,_max = _tmp;
93 else
94 _min = _tmp,_max = _part;
95 }
96 else
97 {
98 _min = _max = _tmp;
99 }
100
101 if (_comp(*(_first + _min),_val))
102 {
103 if (_comp(_val,*(_first + _max)))
104 {
105 if (_comp(*(_first + _parent),*(_first + _max)))
106 *(_first + ((_parent - 2) >> 1)) = *(_first + _max);
107 else
108 *(_first + _parent) = *(_first + _max);
109 *(_first + _max) = _val;
110 }
111 else
112 {
113 __push_max_dheap(_first,_parent,_hole,_val,_comp);
114 }
115 }
116 else
117 {
118 if (_comp(*(_first + _parent),*(_first + _max)))
119 *(_first + ((_parent - 2) >> 1)) = *(_first + _max);
120 else
121 *(_first + _parent) = *(_first + _max);
122 *(_first + _max) = *(_first + _min);
123 __push_min_dheap(_first,_min,__partner_dheap(_hole),_val,_comp,_flag);
124 }
125}
5、最小堆调整
1template<typename _RandIt,typename _Distance,typename _Ty>
2inline void __adjust_min_dheap(_RandIt _first,_Distance _len,_Distance _hole,_Ty _val)
3{
4 assert(_len > 0);
5
6 _Distance _parent,_child,_tmp,_part,_bottom = _len - 1, _half = _bottom >> 1;
7 for(_parent = _hole;_parent < _half;)
8 {
9 _child = (_parent + 1) << 1;
10 if (_child < _bottom)
11 {
12 _tmp = _child;
13 if (++_tmp <= _bottom && *(_first + _tmp) < *(_first + _child))
14 ++_child;
15 }
16 *(_first + _parent) = *(_first + _child);
17 _parent = _child;
18 }
19
20 _part = __partner_dheap(_parent);
21 if (_part > 1 && _part > _bottom) _part = (_part - 2) >> 1;
22
23 if (1 != _part && *(_first + _part) < _val)
24 {
25 *(_first + _parent) = *(_first + _part);
26 __push_max_dheap(_first,_part,__partner_dheap(_hole),_val);
27 }
28 else
29 {
30 __push_min_dheap(_first,_parent,_hole,_val);
31 }
32}
33
34template<typename _RandIt,typename _Distance,typename _Ty,typename _Compare>
35inline void __adjust_min_dheap(_RandIt _first,_Distance _len,_Distance _hole,_Ty _val,_Compare _comp)
36{
37 assert(_len > 0);
38
39 _Distance _parent,_child,_tmp,_part,_bottom = _len - 1, _half = _bottom >> 1;
40 for(_parent = _hole;_parent < _half;)
41 {
42 _child = (_parent + 1) << 1;
43 if (_child < _bottom)
44 {
45 _tmp = _child;
46 if (++_tmp <= _bottom && _comp(*(_first + _tmp),*(_first + _child)))
47 ++_child;
48 }
49 *(_first + _parent) = *(_first + _child);
50 _parent = _child;
51 }
52
53 _part = __partner_dheap(_parent);
54 if (_part > 1 && _part > _bottom) _part = (_part - 2) >> 1;
55
56 if (1 != _part && _comp(*(_first + _part),_val))
57 {
58 *(_first + _parent) = *(_first + _part);
59 __push_max_dheap(_first,_part,__partner_dheap(_hole),_val,_comp);
60 }
61 else
62 {
63 __push_min_dheap(_first,_parent,_hole,_val,_comp);
64 }
65}
7、堆调整
1template<typename _RandIt,typename _Distance,typename _Ty>
2inline void __adjust_dheap(_RandIt _first,_Distance _len,_Distance _hole,_Ty _val,bool _flag = true)
3{
4 __is_max_dheap(_hole) ? __adjust_max_dheap(_first,_len,_hole,_val,_flag) : __adjust_min_dheap(_first,_len,_hole,_val);
5}
6
7template<typename _RandIt,typename _Distance,typename _Ty,typename _Compare>
8inline void __adjust_dheap(_RandIt _first,_Distance _len,_Distance _hole,_Ty _val,_Compare _comp,bool _flag = true)
9{
10 __is_max_dheap(_hole) ? __adjust_max_dheap(_first,_len,_hole,_val,_comp,_flag) : __adjust_min_dheap(_first,_len,_hole,_val,_comp);
11}
posted on 2011-10-03 17:54
春秋十二月 阅读(2165)
评论(1) 编辑 收藏 引用 所属分类:
Algorithm