随笔-88  评论-224  文章-23  trackbacks-0
   本文讲述双端堆的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、构造堆
 1template<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、插入元素
 1template<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 春秋十二月 阅读(2224) 评论(1)  编辑 收藏 引用 所属分类: Algorithm

评论:
# re: 基于顺序存储实现的多叉树:(7) 深度遍历 2011-10-06 17:10 | 双星休闲鞋
一段时间没有接触,都是迷迷糊糊的。  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理