c++ heap学习

heap并不属于STL容器组件，它分为 max heap 和min heap，在缺省情况下，max-heap是优先队列（priority queue）的底层实现机制。

而这个实现机制中的max-heap实际上是以一个vector表现的完全二叉树（complete binary tree）。
二叉堆（binary heap）就是i一种完全二叉树。也即是。整棵二叉树除了最底层的叶节点以外，都是填满的，而最低层的叶子结点必须是从左到右不留空隙。
至于max-heap和min-heap，前者的任何一个父亲结点都必须大于等于他的任意子结点，而后者相反。

《在这里值得一提的是》，heap对于map/unordered_map的排序（大小排序方式）是根据key值来排序的。

操作：

push_heap()：新添加一个元素在末尾，然后重新调整堆序。也就是把元素添加在底层vector的end()处。

该算法必须是在一个已经满足堆序的条件下，添加元素。该函数接受两个随机迭代器，分别表示first,end,区间范围。

关键是我们执行一个siftup()函数，上溯函数来重新调整堆序。

pop_heap()这个算法跟push_heap类似，参数一样。不同的是我们把堆顶元素取出来，放到了数组或者是vector的末尾，用原来末尾元素去替代，然后end迭代器减1，执行siftdown()下溯函数来重新调整堆序。

注意算法执行完毕后，最大的元素并没有被取走，而是放于底层容器的末尾。如果要取走，则可以使用底部容器（vector）提供的pop_back()函数。

sort_heap（）算法：既然每次pop_heap可以获得堆中最大的元素，那么我们持续对整个heap做pop_heap操作，每次将操作的范围向前缩减一个元素。

sort_heap（）算法：接受两个随机迭代器作为参数。表示操作的范围。

make_heap()算法：建立一个堆。很简单吧。接受的参数同上。

#include <iostream>

#include <algorithm> // make_heap(), pop_heap(), push_heap()

#include <vector>

using namespace std;

void printVector(vector<int> &num)

{

    for(int i = ; i < num.size(); i++)

        cout<<num[i]<<" ";

    cout<<endl;

}

int main()

{

    // init

    int arr[] = {,,,,,};

    vector<int> num(arr,arr+);

    printVector(num);

    // build

    make_heap(num.begin(),num.end());

    printVector(num); // 9 5 6 1 4 3 默认大顶堆

    // get the biggest number

    // 从vector的角度来取得

    cout<<num[]<<endl; // 9

    // or num.front();

    cout<<num.front()<<endl; // 9

    // delete 堆顶，即最大的元素

    // 返回值为 void

    // 将堆顶的元素放到最后一个位置上

    // 弹出一个元素后，剩下的又重建了 heap，仍保持heap的性质

    pop_heap(num.begin(),num.end());

    printVector(num); // 6 5 3 1 4 9

    // vector 删除末尾元素

    num.pop_back();

    printVector(num);

    num.push_back(); //首先在vector上扩容，增加一个元素到尾部

    printVector(num); // 6 5 3 1 4 7

    push_heap(num.begin(),num.end());  // 指定区间的最后一个元素加入堆中并使整个区间成为一个新的堆。注意前提是最后一个元素除外的所有元素已经构成一个堆。

    printVector(num);  // 7 5 6 1 4 3

    // 判断是否为堆

    bool ret = is_heap(num.begin(),num.end());

    cout<<ret<<endl;

    num.push_back();

    printVector(num);  // 7 5 6 1 4 3 9

    cout<< is_heap(num.begin(),num.end()) <<endl;

    push_heap(num.begin(),num.end());

    printVector(num); // 9 5 7 1 4 3 6

    sort_heap(num.begin(),num.end());

    printVector(num); // 1 3 4 5 6 7 9

}

// 小顶堆

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

class greater_class{

public:

    bool operator()(int a, int b)

    {

        return a > b;

    }

};

int main()

{

    // init

    int arr[] = {,,,,,};

    vector<int> num(arr,arr+);

    printVector(num);

    make_heap(num.begin(), num.end(), greater_class());

    printVector(num); // 1 4 3 9 5 6 

    num.push_back();

    printVector(num); // 1 4 3 9 5 6 2

    push_heap(num.begin(),num.end(),greater_class());

    printVector(num); // 1 4 2 9 5 6 3 

    while (num.size())

    {

        pop_heap(num.begin(),num.end(),greater_class());

        long min = num.back();

        num.pop_back();

        cout << min << std::endl;

    } // 1 2 3 4 5 6 9

}

巴特西

c++ heap学习

最新文章

热门文章