随笔-155  评论-223  文章-30  trackbacks-0
   在《基于双端堆实现的优先级队列(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为底的整数对数(向下取整)
 1struct _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 >> 16if (_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 >> 32if (_tmp) { _ret += 32; _val = _tmp;}
26    _tmp = _val >> 16if (_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、对称结点计算和判断函数
 1template<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 春秋十二月 阅读(2149) 评论(1)  编辑 收藏 引用 所属分类: Algorithm

评论:
# re: 基于双端堆实现的优先级队列:(3) 外观 2011-10-04 13:07 | 博洋家纺
不错,收藏了  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理