C++ make_heap等堆函数的使用

我会带着你远行 2024-04-01 19:27 25阅读 0赞

#### 一、介绍 ####

C++的STL提供了make\_heap、push\_heap、pop\_heap、sort\_heap等算法，它们用来将一个随机存储的数组转换为一个堆（heap）。这里所说的转换为heap意思是将原来数据的存储顺序改变，它将转换成的堆，然后通过层序遍历，得到的元素顺序，作为数组新的元素顺序(简单的描述就是对原来的数组，用一个算法改变一下元素顺序)。

#### 二、make\_heap ####

make\_heap()用于把一个可迭代容器变成一个堆，默认是大顶堆。  
它有三个参数。第一个参数是指向开始元素的迭代器，第二个参数是指向最末尾元素的迭代器，第三个参数是less<>()或是greater<>()，前者用于生成大顶堆，后者用于生成小顶堆，默认情况下为less<>()。

template <class RandomAccessIterator>
    	void make_heap(RandomAccessIterator first, RandomAccessIterator last);
    	
    template <class RandomAccessIterator, class Compare>
    	void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

#### 三、push\_heap() ####

push\_heap()是在堆的基础上进行数据的插入操作，参数与make\_heap()相同，push\_heap的功能是往堆中插入一个数据。但是，它的默认前提是区间\[first, last - 1)已经满足堆结构，并且要插入的数据已经插入到区间的最后一个位置。STL库提供的push\_heap算法并没有进行插入元素操作，仅仅是完成调整工作，将插入元素后的区间恢复成堆结构。

我们需要注意，当一次性插入多个数据然后再调用push\_heap进行调整的时候，除最后插入的数据之外的其他前面插入的数据，必须保证和已有数据依然能够构成堆结构，因为push\_heap只是对左闭右开区间的最后一个数据进行调整，并且认为前面的数据已经满足堆结构，所以如果前面插入的数据不能保证堆结构的话就会报错。

template <class RandomAccessIterator>
    	void push_heap(RandomAccessIterator first, RandomAccessIterator last);
    	
    template <class RandomAccessIterator, class Compare>
    	void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

#### 四、 pop\_heap() ####

pop\_heap()用于将堆的第零个元素与最后一个元素交换位置，然后针对前n - 1个元素调用make\_heap()函数，它也有三个参数，参数意义与make\_heap()相同，第三个参数应与make\_heap时的第三个参数保持一致。

需要注意的是每次pop一个元素后，下一次pop时就需要将区间缩小1(last减1)。如果要删除这个元素，还需要对数组进行pop\_back()操作。

### 五、sort\_heap() ###

sort\_heap()是将堆进行排序，排序后，序列将失去堆的特性（子节点的键值总是小于或大于它的父节点）。它也具有三个参数，参数意义与make\_heap()相同，第三个参数应与make\_heap时的第三个参数保持一致。大顶堆sort\_heap()后是一个递增序列，小顶堆是一个递减序列。

#### 六、使用 ####

实例一

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include <queue>
    #include <functional>
    using namespace std;
    
    void display(vector<int> q) {
        for (int i = 0; i < q.size(); i++) {
            cout << q[i] << " ";
        }
        cout << endl;
    }
    
    
    int main()
    {
        vector<int> q;
        for (int i = 0; i < 10; i++) {
            q.push_back(i);
        }
        make_heap(q.begin(), q.end(), less<int>());
        cout << "插入前" << endl;
        display(q);
    
        q.push_back(12);
        push_heap(q.begin(), q.end(), less<int>());
        cout << "插入后" << endl;
    
        display(q);
    
    	return 0;
    }

![3c2e73cdea4848659861306acb42700d.png][]

实例二

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include <queue>
    #include <functional>
    using namespace std;
    
    void display(vector<int> q) {
        for (int i = 0; i < q.size(); i++) {
            cout << q[i] << " ";
        }
        cout << endl;
    }
    
    
    int main()
    {
        vector<int> v = { 5, 7, 9, 30, 4, 1, 0, 2 };
        display(v);
        cout << endl;
    
        //生成一个小堆
        make_heap(v.begin(), v.end(), greater<int>());
        display(v);
        cout << endl;
    
        pop_heap(v.begin(), v.end(), greater<int>()); // 将堆的第零个元素与最后一个元素交换
        display(v);
        cout << endl;
    
        v.pop_back(); // 删除最后位置的元素
        display(v);
        cout << endl;
    
    
        cout << "排序后"<< endl;
        sort_heap(v.begin(), v.end(), greater<int>());
        display(v);
    
    	return 0;
    }

![856c9f40b03c4c30b0ab70207ad99c97.png][]

参考：

[make\_heap()等函数的用法 - 阳离子 - 博客园][make_heap_ - _ -]

[heap算法函数—make\_heap、push\_heap、pop\_heap和sort\_heap\_小-豪-豪的博客-CSDN博客\_push\_heap][heap_make_heap_push_heap_pop_heap_sort_heap_-_-_-CSDN_push_heap]

[3c2e73cdea4848659861306acb42700d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5bc7237684894c4ba661237c76472d02.png
[856c9f40b03c4c30b0ab70207ad99c97.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/81624c28d46844c791a894f067f79cbb.png
[make_heap_ - _ -]: https://www.cnblogs.com/woxiaosade/p/10628388.html
[heap_make_heap_push_heap_pop_heap_sort_heap_-_-_-CSDN_push_heap]: https://blog.csdn.net/qq_39014877/article/details/104578971