STL中heap的用法

本是古典何须时尚 2021-11-09 06:04 270阅读 0赞

### 文章目录 ###

*   *  介绍
     *  heap的四种操作
     *   *  make\_heap()
         *  push\_heap()
         *  pop\_heap()
         *  sort\_heap()

## 介绍 ##

STL的堆操作在头文件<**algorithm**>中，堆是以数组或者vector实现的完全二叉树结构(**如果一个二叉树深度为h, 除了最后一层之外，其他层都达到最大个数，最后一层满足从左到右的顺序没有空隙**)

*  大顶堆：所有父节点>=子节点(数组中：array\[i\] >= array\[2*i+1\] && array\[i\]>=array\[2*i+2\])
 *  小顶堆：所有父节点<=子节点(数组中：array\[i\] <= array\[2*i+1\] && array\[i\]>=array\[2*i+2\])

## heap的四种操作 ##

### make\_heap() ###

建立堆，要么大顶堆(less<T>())，要么小顶堆(greater<T>())

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    
    void print(int a)
    { 
        cout << a << " "  ;
    }
    void Print(const vector<int>& array)
    { 
       for_each(array.begin(), array.end(), print); 
       cout << endl;
    }
    
    int main(void)
    { 
        vector<int> array;
        for(int i=0; i<9; i++)
        { 
    	array.push_back(i);
        }
    
        make_heap(array.begin(), array.end(),greater<int>());  // 小顶堆: 0 1 2 3 4 5 6 7 8 
        // make_heap(array.begin(), array.end(),less<int>()); //大顶堆: 8 7 6 3 4 5 2 1 0
        // make_heap(array.begin(), array.end()); //不提供仿函数，默认大顶堆: 8 7 6 3 4 5 2 1 0
        Print(array);
        return 0;
    }

--------------------

### push\_heap() ###

添加一个元素在末尾，重现调整堆，需要注意的是:  必须是数组本来已经是一个堆的前提下，且push\_heap的第三个参数需要和原来的堆相同。

vector<int> array;
        for(int i=0; i<9; i++)
        { 
    	array.push_back(i);
        }
    
         make_heap(array.begin(), array.end(), less<int>());
         Print(array);
    
        array.push_back(100);　//首先数组push_back插入元素，
        push_heap(array.begin(), array.end(),less<int>()); //然后再调用push_heap 
        Print(array);

--------------------

### pop\_heap() ###

将堆顶的元素和数组末尾的元素交换，end-1（算法将不包括数组最后一个元素），再从新调整堆，结束之后，数组最后一个元素还在，大部分情况需要再手动 push\_back()

vector<int> array;
        for(int i=0; i<9; i++)
        { 
    	array.push_back(i);
        }
    
         make_heap(array.begin(), array.end(), less<int>());
         Print(array);
    
        array.push_back(100);
        push_heap(array.begin(), array.end(),less<int>());  // 100 8 6 3 7 5 2 1 0 4
        Print(array);
    
        pop_heap(array.begin(), array.end(), less<int>());// 8 7 6 3 4 5 2 1 0 100
        array.pop_back() // 8 7 6 3 4 5 2 1 0
        Print(array);

--------------------

### sort\_heap() ###

将一个**原有的堆**进行堆排序，得到一个排序的数组，第三个参数必须和原有的堆一样的(原来的是大顶堆，参数是less<T>()，否则相反)，pop\_heap()一次将最大放到最后，再重新调整成新的堆；其实不断pop\_heap()（次数：数组长度）的过程。

vector<int> array;
        for(int i=0; i<9; i++)
        { 
    	array.push_back(i);
        }
    
         make_heap(array.begin(), array.end(), less<int>()); //8 7 6 3 4 5 2 1 0
         Print(array);
    
        array.push_back(100);
        push_heap(array.begin(), array.end(),less<int>()); //100 8 6 3 7 5 2 1 0 4
        Print(array);
    
        pop_heap(array.begin(), array.end(), less<int>()); // 8 7 6 3 4 5 2 1 0 100 
        Print(array);
        array.pop_back(); // 8 7 6 3 4 5 2 1 0 
    
        sort_heap(array.begin(), array.end(), less<int>()); // 0 1 2 3 4 5 6 7 8 
        Print(array);