STL之Heap

Posted on

heap在STL中并不属于容器组建，而且作为priority queue的助手,你可以在<algorithms>中找到关于heap的算法，如

  • make_heap
  • is_heap
  • pop_heap
  • push_heap
  • sort_heap

在进行heap的分析之前，我们先了解一下priority queue(优先队列)

许多应用程序需要处理有序的元素，但不一定要求它们全部有序，有时候我们只想处理优先级最高的元素(例如基于优先级的调度器)，这样，就要求一个能够

  • 删除最大元素
  • 插入元素

的数据结构，我们称其为priority queue,实现priority queue的合适做法是使用binary heap，所谓的binary heap就是一种完全二叉树，因此我们可以用数组来实现它，例如下面的例子

5

用数组表示就是

1
{1,2,3,4,5}

有序化

前面也提到了，priority queue是有序的，而且可以删除最大的元素，然后插入元素依旧可以保持有序，其中的奥秘就是在进行删除和插入的操作的时候，priority queue会按照一定的规则进行有序化

上浮

如果堆的有序状态因为某个节点变得比它的父节点大而被打破，例如在数组后面插入一个很大很大的节点，那么就要交换该节点和其父节点，然后，交换之后，仍旧可能大于父节点，然后继续交换，这种行为称为上浮

下沉

和上浮相反

push_heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template <class _RandomAccessIterator>
inline void 
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) //RandomAccessIteraotr说明用的是内存连续的数据结构
{
  __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
                 _LessThanComparable);
  __push_heap_aux(__first, __last,
                  __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
}

template <class _RandomAccessIterator, class _Distance, class _Tp>
inline void 
__push_heap_aux(_RandomAccessIterator __first,
                _RandomAccessIterator __last, _Distance*, _Tp*)
{
  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
              _Tp(*(__last - 1)));
}

template <class _RandomAccessIterator, class _Distance, class _Tp>
void 
__push_heap(_RandomAccessIterator __first,
            _Distance __holeIndex, _Distance __topIndex, _Tp __value)
{
  _Distance __parent = (__holeIndex - 1) / 2; //找出父节点的位置
  while (__holeIndex > __topIndex && *(__first + __parent) < __value) { //新值大于父节点，且还没到达根节点
      //交换父节点和新节点
    *(__first + __holeIndex) = *(__first + __parent); 
    __holeIndex = __parent;
      //交换完毕，找出交换之后新节点的父节点
    __parent = (__holeIndex - 1) / 2;
  }    
  *(__first + __holeIndex) = __value;
}

pop_heap

值得注意的是，虽然是pop_heap，但并没有在操作结束之后把元素给删除，而是将其移动到容器末尾，然后再由用户决定是否删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
template <class _RandomAccessIterator>
inline void pop_heap(_RandomAccessIterator __first, 
                     _RandomAccessIterator __last)
{
  __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
                 _LessThanComparable);
  __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
}

template <class _RandomAccessIterator, class _Tp>
inline void 
__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
               _Tp*)
{
  __pop_heap(__first, __last - 1, __last - 1, 
             _Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
}

template <class _RandomAccessIterator, class _Tp, class _Distance>
inline void 
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
           _RandomAccessIterator __result, _Tp __value, _Distance*)
{
  *__result = *__first;
  __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
}

template <class _RandomAccessIterator, class _Distance, class _Tp>
void 
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
              _Distance __len, _Tp __value)
{
  _Distance __topIndex = __holeIndex;
  _Distance __secondChild = 2 * __holeIndex + 2; //右子节点相对于父节点的位置，见注
  while (__secondChild < __len) {
    if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) //比较左右两节点，找出较大者
      __secondChild--;
    *(__first + __holeIndex) = *(__first + __secondChild); //与较大者交换
    __holeIndex = __secondChild;
    __secondChild = 2 * (__secondChild + 1); //找出交换之后的右子节点
  }
  if (__secondChild == __len) { //如果只有左节点，没有右子节点
    *(__first + __holeIndex) = *(__first + (__secondChild - 1)); //与左节点交换
    __holeIndex = __secondChild - 1;
  }
  __push_heap(__first, __holeIndex, __topIndex, __value);
}

注：{1,2,3,4,5,6}，数组长度为6，3的下标为2，3只有左节点6，2 * 2 + 2 = 6, 6等于数组长度，故3没有右节点，如果大于数组长度，说明3没有左节点

sort_heap

1
2
3
4
5
6
7
8
9
template <class _RandomAccessIterator>
void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
  __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
                 _LessThanComparable);
  while (__last - __first > 1)
    pop_heap(__first, __last--);
}

这个就很简单，既然我们知道，pop_heap能够将heap的根节点(也就是heap的最大节点)移动到末尾，那么只要对堆不断进行pop_heap操作，然后缩小pop_heap所操作的的范围，就能获取有序的数据集

make_heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template <class _RandomAccessIterator>
inline void 
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
  __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
                 _LessThanComparable);
  __make_heap(__first, __last,
              __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
}

template <class _RandomAccessIterator, class _Tp, class _Distance>
void 
__make_heap(_RandomAccessIterator __first,
            _RandomAccessIterator __last, _Tp*, _Distance*)
{
  if (__last - __first < 2) return;
  _Distance __len = __last - __first;
  _Distance __parent = (__len - 2)/2;
    
  while (true) {
    __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
    if (__parent == 0) return;
    __parent--;
  }
}

也就是对当前的数组不断地进行调整，然后得到一个heap