STL

STL解析 —— heap

Standard Template Library —— heap

ZingLix May 27, 2018

heap 又称二叉堆,是一个十分常用的数据结构,可以看成一个完全二叉树,但可以使用数组来实现。在这有过更详细的介绍。

heap.jpg

在 STL 中,heap 并不作为一个容器,而是在 algorithm 库中以算法的形式实现,并且都接受firstlast两个参数,并要求其为 随机迭代器(Random Access Iterator)。另外,这些函数都提供两个版本,一个通过 < 来比较,从而实现最大堆,另一个利用模板,从而可以指定比较函数Comp来比较。两者实现相似,所以本文用前者,另一版本可以在Github查看。

标准中定义了如下五个函数:

  • is_heap: 判断 [first, last) 中元素是否为最大堆。
  • make_heap:在 [first, last) 中构造最大堆。
  • push_heap:将 last-1 中元素插入到 [first, last-1) 的最大堆中。
  • pop_heap:交换在位置 first 的值和在位置 last-1 的值,并令子范围 [first, last-1) 变为最大堆。
  • sort_heap:转换最大堆 [first, last) 为以升序排序的范围。

辅助函数

首先是用于得到子节点或者父节点的函数,使之后实现更为方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class Distance>
Distance _left(Distance i) {
    return 2 * i + 1;
}

template<class Distance>
Distance _right(Distance i) {
    return 2 * i + 2;
}

template<class Distance>
Distance _parent(Distance i) {
    return (i - 1) / 2 ;
}

另外还有个函数帮助维护堆的性质,使某个不满足堆性质的节点移动到正确的位置。思路很简单,就是和左右节点比较,在三个节点中找到最大的一个与其互换,然后对新子树再进行该操作。若无需说明已满足最大堆条件则结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<class RandomIt,class Distance>
void _max_heapify(RandomIt first,Distance index,Distance size) {
    Distance l = _left(index),r=_right(index);
    Distance largest;
    if(l<size&&*(first+l)>*(first+index)) {
        largest = l;
    } else {
        largest = index;
    }
    if(r<size&&*(first+r)>*(first+largest)) {
        largest = r;
    }
    if(largest!=index) {
        auto tmp = *(first + index);
        *(first + index) = *(first + largest);
        *(first + largest) = tmp;
        _max_heapify(first, largest, size);
    }
}

前一个函数使得节点可以下降,同时很可能需要将某个节点上升,思路与前者相似。

1
2
3
4
5
6
7
8
9
10
11
template<class RandomIt,class Distance>
void _percolate_up(RandomIt first,Distance index) {
    auto value = *(first + index);
    auto parent =_parent(index);
    while (index!=0&& value > *(first + parent)) {
        *(first + index) = *(first + parent);
        index = parent;
        parent = _parent(parent);
    } 
    *(first + index) = value;
}

push_heap

这一函数用于将最后一个元素插入到前面的最大堆中,所以我们只需要利用percolate_up将最后一个元素上升即可。

1
2
3
4
template<class RandomIt>
void push_heap(RandomIt first,RandomIt last) {
    _percolate_up(first, last - first-1);
}

pop_heap

pop_heap用于将最大的元素出堆,但实际上是将其放到最后,而原本在最后的元素需要将其调整到合适的位置。所以这一函数思路为将最前和最后的元素互换,再对新的第一个元素调用max_heapify维护堆的性质。

1
2
3
4
5
6
7
template<class RandomIt>
void pop_heap(RandomIt first, RandomIt last) {
    auto tmp = *first;
    *first= *(last - 1);
    *(last - 1) = tmp;
    _max_heapify(first, first-first, last - first-1);
}

make_heap

max_heapify可以使某个节点满足堆性质,那么对所有节点都调用一次就可以得到最大堆。而有一半节点为叶节点,所以只用对一半节点做该操作。

1
2
3
4
5
6
7
template<class RandomIt>
void make_heap(RandomIt first, RandomIt last) {
    auto size = last - first;
    for(auto i=size/2;i>=0;--i) {
        _max_heapify(first, i, size);
    }
}

sort_heap

利用pop_heap将最大的元素放至最后这一特性,那么只需要将所有元素出堆就得到了有序的数组。

HeapSort.gif

1
2
3
4
5
6
template<class RandomIt>
void sort_heap(RandomIt first,RandomIt last) {
    while(last-first>1) {
        lix::pop_heap(first, last--);
    }
}

is_heap

依次遍历并判断是否满足最大堆性质便可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class RandomIt,class Distance>
bool _is_heap(RandomIt first,Distance size){
    for(Distance i=0;i<size/2;++i) {
        if (_left(i) < size&&*(first + i) < *(first + _left(i))) 
            return false;
        if (_right(i) < size&& *(first + i) < *(first + _right(i))) 
            return  false;
    }
    return true;
}

template< class RandomIt >
bool is_heap(RandomIt first, RandomIt last) {
    return _is_heap(first, last - first);
}

后记

本文中的实现主要依靠_max_heapify_percolate_up两个函数。另外还有个 SGI_STL 的实现有所差异。这些关于堆的函数在优先队列的实现中有极大帮助。