在《
基于双端堆实现的优先级队列(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![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct _64bit_int
{};
2![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct _no_64bit_int
{};
3![](/Images/OutliningIndicators/None.gif)
4
template<typename _Distance>
5
inline _Distance __log2(_Distance _val,_no_64bit_int)
6![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
7
assert(_val > 0);
8![](/Images/OutliningIndicators/InBlock.gif)
9
_Distance _ret = 0, _tmp;
10![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
_tmp = _val >> 16; if (_tmp)
{ _ret += 16; _val = _tmp;}
11![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
_tmp = _val >> 8; if (_tmp)
{ _ret += 8; _val = _tmp; }
12![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
_tmp = _val >> 4; if (_tmp)
{ _ret += 4; _val = _tmp; }
13![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
_tmp = _val >> 2; if (_tmp)
{ _ret += 2; _val = _tmp; }
14
_ret += (_val >> 1);
15![](/Images/OutliningIndicators/InBlock.gif)
16
return _ret;
17
}
18![](/Images/OutliningIndicators/None.gif)
19
template<typename _Distance>
20
inline _Distance __log2(_Distance _val,_64bit_int)
21![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
22
assert(_val > 0);
23![](/Images/OutliningIndicators/InBlock.gif)
24
_Distance _ret = 0, _tmp;
25![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
_tmp = _val >> 32; if (_tmp)
{ _ret += 32; _val = _tmp;}
26![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
_tmp = _val >> 16; if (_tmp)
{ _ret += 16; _val = _tmp;}
27![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
_tmp = _val >> 8; if (_tmp)
{ _ret += 8; _val = _tmp; }
28![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
_tmp = _val >> 4; if (_tmp)
{ _ret += 4; _val = _tmp; }
29![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
_tmp = _val >> 2; if (_tmp)
{ _ret += 2; _val = _tmp; }
30
_ret += (_val >> 1);
31![](/Images/OutliningIndicators/InBlock.gif)
32
return _ret;
33
}
34![](/Images/OutliningIndicators/None.gif)
35
template<typename _Distance>
36
inline _Distance __log2(_Distance val)
37![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
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>
2
inline bool __is_max_dheap_until(_Distance _dist)
3![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
4
assert(_dist > 1);
5
return 0!=(_dist&(((_Distance)1)<<(__log2(_dist)-1)));
6
}
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
template<typename _Distance>
9
inline bool __is_max_dheap(_Distance _dist)
10![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
11
_Distance _tmp = _dist + 2;
12
return _tmp > _dist ? __is_max_dheap_until(_tmp) : __is_max_dheap_until((_dist>>1) - 1);
13
}
14![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
15
template<typename _Distance>
16
inline _Distance __partner_dheap_until(_Distance _dist)
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
18
assert(_dist > 1);
19
return _dist^(((_Distance)1)<<(__log2(_dist)-1));
20
}
21![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
22
template<typename _Distance>
23
inline _Distance __partner_dheap(_Distance _dist)
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
25
_Distance _tmp = _dist + 2;
26
return _tmp > _dist ? __partner_dheap_until(_tmp) - 2 : __partner_dheap_until((_dist>>1) - 1) - 2;
27
}
3、最大堆最小堆的插入
1
template<typename _RandIt,typename _Distance,typename _Ty>
2
inline void __push_min_dheap(_RandIt _first,_Distance _hole,_Distance _top,_Ty _val,bool _flag = true)
3![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
4
for (_Distance _parent;_hole > _top;)
5![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
15
template<typename _RandIt,typename _Distance,typename _Ty,typename _Compare>
16
inline void __push_min_dheap(_RandIt _first,_Distance _hole,_Distance _top,_Ty _val,_Compare _comp,bool _flag = true)
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
18
for (_Distance _parent;_hole > _top;)
19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
29
template<typename _RandIt,typename _Distance,typename _Ty>
30
inline void __push_max_dheap(_RandIt _first,_Distance _hole,_Distance _top,_Ty _val,bool _flag = true)
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
32
for (_Distance _parent;_hole > _top;)
33![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
43
template<typename _RandIt,typename _Distance,typename _Ty,typename _Compare>
44
inline void __push_max_dheap(_RandIt _first,_Distance _hole,_Distance _top,_Ty _val,_Compare _comp,bool _flag = true)
45![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
46
for (_Distance _parent;_hole > _top;)
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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、最大堆调整
1
template<typename _RandIt,typename _Distance,typename _Ty>
2
inline void __adjust_max_dheap(_RandIt _first,_Distance _len,_Distance _hole,_Ty _val,bool _flag = true)
3![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
4
assert(_len > 0);
5![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
6
_Distance _parent,_child,_tmp,_part,_min,_max,_bottom = _len - 1, _half = _bottom >> 1;
7
for(_parent = _hole;_parent < _half;)
8![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
9
_child = (_parent + 1) << 1;
10
if (_child < _bottom)
11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
12
_tmp = _child;
13
if (++_tmp <= _bottom && *(_first + _child) < *(_first + _tmp))
14
++_child;
15
}
16
*(_first + _parent) = *(_first + _child);
17
_parent = _child;
18
}
19![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
20
_part = __partner_dheap(_parent),_tmp = (_part + 1) << 1;
21
if(_tmp != _bottom)
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
23
if (_tmp < _bottom)
24
_part = _tmp, ++_tmp ;
25
else
26
(_part&1)==0 ? _tmp = _part + 1 : _tmp = _part - 1;
27![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
28
if (*(_first + _part) < *(_first + _tmp))
29
_min = _part,_max = _tmp;
30
else
31
_min = _tmp,_max = _part;
32
}
33
else
34![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
35
_min = _max = _tmp;
36
}
37![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
38
if (*(_first + _min) < _val)
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
40
if (_val < *(_first + _max))
41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
50
__push_max_dheap(_first,_parent,_hole,_val);
51
}
52
}
53
else
54![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
64
template<typename _RandIt,typename _Distance,typename _Ty,typename _Compare>
65
inline void __adjust_max_dheap(_RandIt _first,_Distance _len,_Distance _hole,_Ty _val,_Compare _comp,bool _flag = true)
66![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
67
assert(_len > 0);
68![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
69
_Distance _parent,_child,_tmp,_part,_min,_max,_bottom = _len - 1, _half = _bottom >> 1;
70
for(_parent = _hole;_parent < _half;)
71![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
72
_child = (_parent + 1) << 1;
73
if (_child < _bottom)
74![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
83
_part = __partner_dheap(_parent),_tmp = (_part + 1) << 1;
84
if(_tmp != _bottom)
85![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
86
if (_tmp < _bottom)
87
_part = _tmp, ++_tmp;
88
else
89
(_part&1)==0 ? _tmp = _part + 1 : _tmp = _part - 1;
90![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
91
if (_comp(*(_first + _part),*(_first + _tmp)))
92
_min = _part,_max = _tmp;
93
else
94
_min = _tmp,_max = _part;
95
}
96
else
97![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
98
_min = _max = _tmp;
99
}
100![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
101
if (_comp(*(_first + _min),_val))
102![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
103
if (_comp(_val,*(_first + _max)))
104![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
113
__push_max_dheap(_first,_parent,_hole,_val,_comp);
114
}
115
}
116
else
117![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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、最小堆调整
1
template<typename _RandIt,typename _Distance,typename _Ty>
2
inline void __adjust_min_dheap(_RandIt _first,_Distance _len,_Distance _hole,_Ty _val)
3![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
4
assert(_len > 0);
5![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
6
_Distance _parent,_child,_tmp,_part,_bottom = _len - 1, _half = _bottom >> 1;
7
for(_parent = _hole;_parent < _half;)
8![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
9
_child = (_parent + 1) << 1;
10
if (_child < _bottom)
11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
12
_tmp = _child;
13
if (++_tmp <= _bottom && *(_first + _tmp) < *(_first + _child))
14
++_child;
15
}
16
*(_first + _parent) = *(_first + _child);
17
_parent = _child;
18
}
19![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
20
_part = __partner_dheap(_parent);
21
if (_part > 1 && _part > _bottom) _part = (_part - 2) >> 1;
22![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
23
if (1 != _part && *(_first + _part) < _val)
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
25
*(_first + _parent) = *(_first + _part);
26
__push_max_dheap(_first,_part,__partner_dheap(_hole),_val);
27
}
28
else
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
30
__push_min_dheap(_first,_parent,_hole,_val);
31
}
32
}
33![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
34
template<typename _RandIt,typename _Distance,typename _Ty,typename _Compare>
35
inline void __adjust_min_dheap(_RandIt _first,_Distance _len,_Distance _hole,_Ty _val,_Compare _comp)
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
37
assert(_len > 0);
38![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
39
_Distance _parent,_child,_tmp,_part,_bottom = _len - 1, _half = _bottom >> 1;
40
for(_parent = _hole;_parent < _half;)
41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
42
_child = (_parent + 1) << 1;
43
if (_child < _bottom)
44![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
53
_part = __partner_dheap(_parent);
54
if (_part > 1 && _part > _bottom) _part = (_part - 2) >> 1;
55![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
56
if (1 != _part && _comp(*(_first + _part),_val))
57![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
58
*(_first + _parent) = *(_first + _part);
59
__push_max_dheap(_first,_part,__partner_dheap(_hole),_val,_comp);
60
}
61
else
62![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
63
__push_min_dheap(_first,_parent,_hole,_val,_comp);
64
}
65
}
7、堆调整
1
template<typename _RandIt,typename _Distance,typename _Ty>
2
inline void __adjust_dheap(_RandIt _first,_Distance _len,_Distance _hole,_Ty _val,bool _flag = true)
3![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
4
__is_max_dheap(_hole) ? __adjust_max_dheap(_first,_len,_hole,_val,_flag) : __adjust_min_dheap(_first,_len,_hole,_val);
5
}
6![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
7
template<typename _RandIt,typename _Distance,typename _Ty,typename _Compare>
8
inline void __adjust_dheap(_RandIt _first,_Distance _len,_Distance _hole,_Ty _val,_Compare _comp,bool _flag = true)
9![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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
春秋十二月 阅读(2143)
评论(1) 编辑 收藏 引用 所属分类:
Algorithm