本文讲述双端堆的5个公开泛型操作算法：make_dheap（原位构造双端堆）、push_dheap（插入元素）、pop_max_dheap（删除最大元素）、pop_min_dheap（删除最小元素），is_dheap（堆验证），每个算法都提供<小于运算符和仿函数比较2个版本，要注意的是比较必须是严格弱序的，即对于<版本存在a<b为真且b<a为假；对于仿函数版本，则存在comp(a，b)为真且comp(b，a)为假。而基于双端堆实现的优先级队列只是调用对应的泛型算法而已。代码如下：
1、构造堆
1
template<typename _RandIt>
2inline void make_dheap(_RandIt _first,_RandIt _last)
3
{
4
typedef typename std::iterator_traits<_RandIt>::difference_type _Distance;
5 typedef typename std::iterator_traits<_RandIt>::value_type _Value;
6
7 _Distance _len = _last - _first;
8 if (2 > _len) return;
9
10 _Distance _bottom = _len - 1,_half = _bottom >> 1,_index,_part;
11 _index = __partner_dheap(_bottom);
12 _index > _bottom ? _index = ((_index - 2) >> 1) + 1 : _index += 1;
13
14 for (;_index <= _bottom;++_index)
15
{
16 _part = __partner_dheap(_index);
17 if (__is_max_dheap(_index))
18 {
19 if (*(_first + _index) < *(_first + _part))
20 std::swap(*(_first + _index),*(_first + _part));
21
}
22 else
23 {
24 if (_part > _bottom) _part = (_part - 2) >> 1;
25 if (*(_first + _part) < *(_first + _index))
26 std::swap(*(_first + _index),*(_first + _part));
27 }
28 }
29 if (0 >= _half) return;
30
31 for (_index = _half - 1; _index >= 0; --_index)
32 {
33 __adjust_dheap(_first,_len,_index,*(_first + _index),false);
34 }
35
}
36
37template<typename _RandIt,typename _Compare>
38inline void make_dheap(_RandIt _first,_RandIt _last,_Compare _comp)
39{
40 typedef typename std::iterator_traits<_RandIt>::difference_type _Distance;
41 typedef typename std::iterator_traits<_RandIt>::value_type _Value;
42
43 _Distance _len = _last - _first;
44 if (2 > _len) return;
45
46 _Distance _bottom = _len - 1,_half = _bottom >> 1,_index,_part;
47 _index = __partner_dheap(_bottom);
48 _index > _bottom ? _index = ((_index - 2) >> 1) + 1 : _index += 1;
49
50 for (;_index <= _bottom;++_index)
51 {
52 _part = __partner_dheap(_index);
53 if (__is_max_dheap(_index))
54 {
55 if (_comp(*(_first + _index),*(_first + _part)))
56 std::swap(*(_first + _index),*(_first + _part));
57 }
58 else
59 {
60 if (_part > _bottom) _part = (_part - 2) >> 1;
61 if (_comp(*(_first + _part),*(_first + _index)))
62 std::swap(*(_first + _index),*(_first + _part));
63 }
64 }
65 if (0 >= _half) return;
66
67 for (_index = _half - 1; _index >= 0; --_index)
68 {
69 __adjust_dheap(_first,_len,_index,*(_first + _index),_comp,false);
70 }
71}
2、插入元素
1
template<typename _RandIt>
2inline void push_dheap(_RandIt _first,_RandIt _last)
3
{
4
typedef typename std::iterator_traits<_RandIt>::difference_type _Distance;
5 typedef typename std::iterator_traits<_RandIt>::value_type _Value;
6
7 _Distance _dist = _last - _first;
8 if (2 > _dist) return;
9
10 _Value _val = *(_last - 1);
11 _Distance _bottom = _dist - 1, _part = __partner_dheap(_bottom);
12 if (__is_max_dheap(_bottom))
13
{
14 if (*(_first + _bottom) < *(_first + _part))
15 {
16 *(_first + _bottom) = *(_first + _part);
17 __push_min_dheap(_first,_part,(_Distance)0,_val);
18
}
19 else
20 {
21 __push_max_dheap(_first,_bottom,(_Distance)1,_val);
22 }
23 }
24 else
25 {
26 if (_part > _bottom) _part = (_part - 2) >> 1;
27 if (*(_first + _bottom) < *(_first + _part))
28 {
29 __push_min_dheap(_first,_bottom,(_Distance)0,_val);
30 }
31 else
32 {
33 *(_first + _bottom) = *(_first + _part);
34 __push_max_dheap(_first,_part,(_Distance)1,_val);
35 }
36 }
37
}
38
39template<typename _RandIt,typename _Compare>
40inline void push_dheap(_RandIt _first,_RandIt _last,_Compare _comp)
41{
42 typedef typename std::iterator_traits<_RandIt>::difference_type _Distance;
43 typedef typename std::iterator_traits<_RandIt>::value_type _Value;
44
45 _Distance _dist = _last - _first;
46 if (2 > _dist) return;
47
48 _Value _val = *(_last - 1);
49 _Distance _bottom = _dist - 1, _part = __partner_dheap(_bottom);
50 if (__is_max_dheap(_bottom))
51 {
52 if (_comp(*(_first + _bottom),*(_first + _part)))
53 {
54 *(_first + _bottom) = *(_first + _part);
55 __push_min_dheap(_first,_part,(_Distance)0,_val,_comp);
56 }
57 else
58 {
59 __push_max_dheap(_first,_bottom,(_Distance)1,_val,_comp);
60 }
61 }
62 else
63 {
64 if (_part > _bottom) _part = (_part - 2) >> 1;
65 if (_comp(*(_first + _bottom),*(_first + _part)))
66 {
67 __push_min_dheap(_first,_bottom,(_Distance)0,_val,_comp);
68 }
69 else
70 {
71 *(_first + _bottom) = *(_first + _part);
72 __push_max_dheap(_first,_part,(_Distance)1,_val,_comp);
73 }
74 }
75}
3、删除最小元素
1template<typename _RandIt>
2inline void pop_min_dheap(_RandIt _first,_RandIt _last)
3{
4 typedef typename std::iterator_traits<_RandIt>::difference_type _Distance;
5 typedef typename std::iterator_traits<_RandIt>::value_type _Value;
6
7 _Distance _len = _last - _first;
8 if (2 > _len) return;
9
10 _Value _val = *(_last - 1); *(_last - 1) = *_first;
11 __adjust_min_dheap(_first,_len - 1,0,_val);
12}
13
14template<typename _RandIt,typename _Compare>
15inline void pop_min_dheap(_RandIt _first,_RandIt _last,_Compare _comp)
16{
17 typedef typename std::iterator_traits<_RandIt>::difference_type _Distance;
18 typedef typename std::iterator_traits<_RandIt>::value_type _Value;
19
20 _Distance _len = _last - _first;
21 if (2 > _len) return;
22
23 _Value _val = *(_last - 1); *(_last - 1) = *_first;
24 __adjust_min_dheap(_first,_len - 1,0,_val,_comp);
25}
4、删除最大元素
1template<typename _RandIt>
2inline void pop_max_dheap(_RandIt _first,_RandIt _last)
3{
4 typedef typename std::iterator_traits<_RandIt>::difference_type _Distance;
5 typedef typename std::iterator_traits<_RandIt>::value_type _Value;
6
7 _Distance _len = _last - _first;
8 if (2 > _len) return;
9
10 _Value _val = *(_last - 1); *(_last - 1) = *(_first + 1);
11 __adjust_max_dheap(_first,_len - 1,1,_val);
12}
13
14template<typename _RandIt,typename _Compare>
15inline void pop_max_dheap(_RandIt _first,_RandIt _last,_Compare _comp)
16{
17 typedef typename std::iterator_traits<_RandIt>::difference_type _Distance;
18 typedef typename std::iterator_traits<_RandIt>::value_type _Value;
19
20 _Distance _len = _last - _first;
21 if (2 > _len) return;
22
23 _Value _val = *(_last - 1); *(_last - 1) = *(_first + 1);
24 __adjust_max_dheap(_first,_len - 1,1,_val,_comp);
25}
5、堆验证
1template<typename _RandIt>
2inline bool is_dheap(_RandIt _first,_RandIt _last)
3{
4 typedef typename std::iterator_traits<_RandIt>::difference_type _Distance;
5
6 _Distance _parent, _child, _part,_dist = _last - _first;
7 if (2 > _dist) return true;
8
9 _Distance _bottom = _dist - 1, _half = _bottom >> 1;
10 for (_parent = 0; _parent < _half; ++_parent)
11 {
12 _child = (_parent + 1) << 1;
13 if (__is_max_dheap(_parent))
14 {
15 if (*(_first + _parent) < *(_first + _child))
16 return false;
17 if (_child < _bottom)
18 {
19 if (++_child <= _bottom && *(_first + _parent) < *(_first + _child))
20 return false;
21 }
22 }
23 else
24 {
25 if (*(_first + _child) < *(_first + _parent))
26 return false;
27 if (_child < _bottom)
28 {
29 if (++_child <= _bottom && *(_first + _child) < *(_first + _parent))
30 return false;
31 }
32 _part = __partner_dheap(_parent);
33 if (_part > _bottom) _part = ( _part - 2) >> 1;
34 if (*(_first + _part) < *(_first + _parent))
35 return false;
36 }
37 }
38 _parent = __partner_dheap(_bottom);
39 if (_parent > _bottom) _parent = ((_parent - 2) >> 1) + 1;
40 else _parent += 1;
41
42 for (; _parent <= _bottom; ++_parent)
43 {
44 _part = __partner_dheap(_parent);
45 if (__is_max_dheap(_parent))
46 {
47 if (*(_first + _parent) < *(_first + _part))
48 return false;
49 }
50 else
51 {
52 if (_part > _bottom) _part = (_part - 2) >> 1;
53 if (*(_first + _part) < *(_first + _parent))
54 return false;
55 }
56 }
57 return true;
58}
59
60template<typename _RandIt,typename _Compare>
61inline bool is_dheap(_RandIt _first,_RandIt _last,_Compare _comp)
62{
63 typedef typename std::iterator_traits<_RandIt>::difference_type _Distance;
64
65 _Distance _parent, _child, _part,_len = _last - _first;
66 if (2 > _len) return true;
67
68 _Distance _bottom = _len - 1, _half = _bottom >> 1;
69 for (_parent = 0; _parent < _half; ++_parent)
70 {
71 _child = (_parent + 1) << 1;
72 if (__is_max_dheap(_parent))
73 {
74 if (_comp(*(_first + _parent),*(_first + _child)))
75 return false;
76 if (_child < _bottom)
77 {
78 if (++_child <= _bottom && _comp(*(_first + _parent),*(_first + _child)))
79 return false;
80 }
81 }
82 else
83 {
84 if (_comp(*(_first + _child),*(_first + _parent)))
85 return false;
86 if (_child < _bottom)
87 {
88 if (++_child <= _bottom && _comp(*(_first + _child),*(_first + _parent)))
89 return false;
90 }
91 _part = __partner_dheap(_parent);
92 if (_part > _bottom) _part = ( _part - 2) >> 1;
93 if (_comp(*(_first + _part),*(_first + _parent)))
94 return false;
95 }
96 }
97 _parent = __partner_dheap(_bottom);
98 if (_parent > _bottom) _parent = ((_parent - 2) >> 1) + 1;
99 else _parent += 1;
100
101 for (; _parent <= _bottom; ++_parent)
102 {
103 _part = __partner_dheap(_parent);
104 if (__is_max_dheap(_parent))
105 {
106 if (_comp(*(_first + _parent),*(_first + _part)))
107 return false;
108 }
109 else
110 {
111 if (_part > _bottom) _part = (_part - 2) >> 1;
112 if (_comp(*(_first + _part),*(_first + _parent)))
113 return false;
114 }
115 }
116 return true;
117}
6、优先级队列
1template<typename _Ty,
2 class _Container= std::vector<_Ty>,
3 class _Compare = std::less<typename _Container::value_type>
4 >
5class priority_queue
6{
7 typedef typename _Container::iterator iterator;
8 typedef typename _Container::const_iterator const_iterator;
9
10public:
11 typedef typename _Container::value_type value_type;
12 typedef typename _Container::reference reference;
13 typedef typename _Container::const_reference const_reference;
14 typedef typename _Container::size_type size_type;
15 typedef typename _Container::difference_type difference_type;
16
17public:
18 priority_queue(const _Container& _c =_Container(),const _Compare& _comp = _Compare())
19 :c_(_c),comp_(_comp)
20 {
21 make_dheap(c_.begin(),c_.end(),comp_);
22 }
23 template<typename _Iter>
24 priority_queue(_Iter _first,_Iter _last,const _Compare& _comp = _Compare())
25 :c_(_first,_last),comp_(_comp)
26 {
27 make_dheap(c_.begin(),c_.end(),comp_);
28 }
29 template<typename _Iter>
30 priority_queue(_Iter _first,_Iter _last,const _Container& _c =_Container(),const _Compare& _comp = _Compare())
31 :c_(_c),comp_(_comp)
32 {
33 c_.insert(c_.end(),_first,_last);
34 make_dheap(c_.begin(),c_.end(),comp_);
35 }
36 void push(const value_type& val)
37 {
38 c_.push_back(val);
39 push_dheap(c_.begin(),c_.end(),comp_);
40 }
41 void pop_min()
42 {
43 pop_min_dheap(c_.begin(),c_.end(),comp_);
44 c_.pop_back();
45 }
46 void pop_max()
47 {
48 pop_max_dheap(c_.begin(),c_.end(),comp_);
49 c_.pop_back();
50 }
51 const_reference top_min() const
52 {
53 return c_.front();
54 }
55 const_reference top_max() const
56 {
57 if (1==c_.size()) return c_.front();
58 return *(c_.begin()+1);
59 }
60 size_type size() const
61 {
62 return c_.size();
63 }
64 bool empty() const
65 {
66 return c_.empty();
67 }
68
69private:
70 _Container c_;
71 _Compare comp_;
72};
posted on 2011-10-05 13:24
春秋十二月 阅读(2608)
评论(1) 编辑 收藏 引用 所属分类:
Algorithm