STL之heap实现详解（内部使用）

不念不忘少年蓝@ 2022-05-29 04:41 155阅读 0赞

# 堆 #

先前的文章已经对堆说得足够清楚了，可以参考。  
可以参考  
[libevent之最小堆][libevent]  
[经典排序算法][Link 1]

堆无非就是分为最大堆(父节点大于等于子节点)和最小堆(父节点小于等于子节点)。STL里面实现的都是最大堆。还有就是堆一般通过数组实现。那么问题就有两个。假如不用数组索引0的位置，那么算法会很简单，那么N的父节点索引就是N/2；N的左右子节点分别是2N和2N+1。假如使用了索引0位置，那么N的父节点索引就是（N-1）/2；N的左右子节点分别是2N+1和2（N+1），STL实现使用了索引0位置，并且仅仅实现了最大堆。

# 插入元素后上浮操作 #

当元素已经插入到了`vector`之后，通过调用`push_heap`可以将元素上浮到`vector`合适的位置，使其满足最大堆属性，下面是上浮操作，基本和libevent和算法第四版里面实现一样。

template <class RandomAccessIterator>
    inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
       //上浮操作
      __push_heap_aux(first, last, distance_type(first), value_type(first));
    }
    template <class RandomAccessIterator, class Distance, class T>
    inline void __push_heap_aux(RandomAccessIterator first,
                                RandomAccessIterator last, Distance*, T*) {
      __push_heap(first, Distance((last - first) - 1), Distance(0), 
                  T(*(last - 1)));//holeIndex尾部，插入值为尾部元素，从0处开始，所以这里在vector元素插入之后，在调用push_heap。
    }
    //这是堆实现的标准实现，libevent里面也是这样实现的。
    template <class RandomAccessIterator, class Distance, class T>
    void __push_heap(RandomAccessIterator first, Distance holeIndex,
                     Distance topIndex, T value) {
      Distance parent = (holeIndex - 1) / 2;//找出父节点
      while (holeIndex > topIndex && *(first + parent) < value) {
       //尚未到顶端，并且父节点小于新值
        *(first + holeIndex) = *(first + parent);//将洞值令为父值
        holeIndex = parent;//更新holeindex，继续向上层比较
        parent = (holeIndex - 1) / 2;//更新父节点
      }    
      *(first + holeIndex) = value;//令洞值为新值，完成插入操作。直到存放新值的位置即可，不必每次交换位置
    }

# 下沉操作后获取最大元素 #

pop\_push将最大堆中的最大元素放置到底部`vector`容器最尾端，尚未取走。可以使用底部容器提供的back读取数值，也可以使用pop\_back移除。这里的实现操作也和前面叙述一样。

template <class RandomAccessIterator>
    inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
      __pop_heap_aux(first, last, value_type(first));
    }
    
    template <class RandomAccessIterator, class T>
    inline void __pop_heap_aux(RandomAccessIterator first,
                               RandomAccessIterator last, T*) {
      __pop_heap(first, last - 1, last - 1, T(*(last - 1)), distance_type(first));
    }
    
    template <class RandomAccessIterator, class T, class Distance>
    inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                           RandomAccessIterator result, T value, Distance*) {
      *result = *first;
      __adjust_heap(first, Distance(0), Distance(last - first), value);
    }
    
    //下沉，这里的写法没有libevent里面简单，将最小值移到尾端
    template <class RandomAccessIterator, class Distance, class T>
    void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
                       Distance len, T 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);
    }

# 堆排序操作 #

`vector`已经满足最大堆属性，那么通过调用`sort_heap`可以将堆排序，过程就是不断将最大的元素移至最尾端即可。

template <class RandomAccessIterator>
    void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
      while (last - first > 1) pop_heap(first, last--);
    }//堆排序，依次将最大元素放置尾端，即可实现堆排序了

# 构造堆 #

构造堆意思就是将`vector`容器里面的已有数据，构造成满足堆属性的数据组合。构造过程在算法上面说的很清楚，可以看前面的参考链接。就是通过下沉阶段完成的。

//采用下沉操作，构造堆，和算法书上面说的方法一样。
    template <class RandomAccessIterator, class Compare, class T, class Distance>
    void __make_heap(RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp, T*, Distance*) {
      if (last - first < 2) return;
      Distance len = last - first;
      Distance parent = (len - 2)/2;//父节点，然后下沉
    
      while (true) {
        __adjust_heap(first, parent, len, T(*(first + parent)), comp);//parent下沉到合适的位置
        if (parent == 0) return;//构造完成
        parent--;
      }
    }

# 使用例子 #

#include <iostream>
    #include <list>
    #include <algorithm>
    #include <iterator>
    #include <deque>
    #include <algorithm>
    #include<stdio.h>
    using namespace std;
    int main()
    {
        int a[9] = {
       0,1,2,3,4,8,9,3,5};
        make_heap(a , a+9 );//将a以堆排放,[a,a+9)左闭合右开
        sort_heap(a , a+9 );//进行堆排序
        for(int i = 0 ; i < 9 ; i++)
            printf("%d " , a[i]);
        printf("\n");
        make_heap(a , a+9);
        pop_heap(a , a+9);//将最大元素放到尾端
        printf("%d\n",a[8]);
    
        vector<int> ivec(a ,a+9);//通过a初始化ivec
        make_heap(ivec.begin() , ivec.end());//在vector构造堆，使vector成堆有序
        for(int i = 0 ; i < 9 ; i++)
            printf("%d " , ivec[i]);
        printf("\n");
        ivec.push_back(7);//先插入，然后通过pop_heap将尾部元素进行上浮操作
        push_heap(ivec.begin() , ivec.end());
        for(int i = 0 ; i < ivec.size() ; i++)
            printf("%d " , ivec[i]);
        printf("\n");
        pop_heap(ivec.begin() , ivec.end());//将堆顶元素移到尾端
        std::cout << ivec.back() << endl;//读取元素
        ivec.pop_back();//弹出最后元素
    
        for(int i = 0 ; i < ivec.size() ; i++)//打印堆有序vector
            printf("%d " , ivec[i]);
        std::cout << endl;
    
        sort_heap(ivec.begin() , ivec.end());//堆有序的vector进行堆排序
        for(int i = 0 ; i < ivec.size() ; i++)//打印排序后的vector
            printf("%d " , ivec[i]);
        std::cout << endl;
     }

![这里写图片描述][Image 1]  
要点：堆是通过数组或者底层list、vector、deque容器实现。`pop_heap、push_heap、make_heap、sort_heap`都是在已存在的数组或者底层容器对象上面操作。特别对于`push_heap`操作得现在尾部插入元素，才可以进行。`make_heap`是将堆顶元素移至尾端。通过看源代码，可以看得比较清楚，很简单的。

[libevent]: http://blog.csdn.net/u010710458/article/details/79430442#t3
[Link 1]: http://blog.csdn.net/u010710458/article/details/78438880
[Image 1]: