STL之heap相关数据结构和算法

场景：对付就业笔试+比赛+项目（精简代码，不影响效率）
在比赛等场景，需要大幅度的精简代码，希望借助STL，一些常用的算法就不自己实现了。
备注：在面试的场景，得会手撕。

一、STL中堆算法相关的函数

1）make_heap

把指定范围内的元素生成一个堆。重载版本使用自定义比较操作

template<class RanIt> 
void make_heap(RanIt first, RanIt last);
Output：无
Input：范围的迭代器的初始，结束

template<class RanIt, class Pred> 
void make_heap(RanIt first, RanIt last, Pred pr);

2)pop_heap

并不真正把最大元素从堆中弹出，而是重新排序堆。它把first和last-1交换，然后重新生成一个堆。可使用容器的back来访问被"弹出"的元素或者使用pop_back进行真正的删除。重载版本使用自定义的比较操作

template<class RanIt> 
void pop_heap(RanIt first, RanIt last);

template<class RanIt, class Pred> 
void pop_heap(RanIt first, RanIt last, Pred pr);

3)push_heap

假设first到last-1是一个有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向该函数前，必须先把元素插入容器后。重载版本使用指定的比较操作

template<class RanIt>
void push_heap(RanIt first, RanIt last);

template<class RanIt, class Pred> 
void push_heap(RanIt first, RanIt last, Pred pr);

4)sort_heap（注意观察后面的代码）

对指定范围内的序列重新排序，它假设该序列是个有序堆。重载版本使用自定义比较操作

template<class RanIt> 
void sort_heap(RanIt first, RanIt last);

template<class RanIt, class Pred> 
void sort_heap(RanIt first, RanIt last, Pred pr);

代码测试

// range heap example
#include<iostream>     
#include<algorithm>   
#include<vector>      
using namespace std;

int main () 
{
  int myints[] = {10,20,30,5,15};
  vector<int> v(myints,myints+5);

  //把指定范围内的元素构建堆，最大堆 
  make_heap (v.begin(),v.end());
  std::cout << "initial max heap   : " << v.front() << '\n';


  //弹出堆元素，其实也不是真正的弹出
  //并不真正把最大元素从堆中弹出，而是重新排序堆。
  //它把first和last-1(也就是最后一个元素）交换，然后重新生成一个堆 
  pop_heap (v.begin(),v.end()); 
  v.pop_back();
  cout << "max heap after pop : " << v.front() << '\n';


  //压入堆元素，注意，范围改变了。 
  v.push_back(99); 
  push_heap (v.begin(),v.end());
  cout << "max heap after push: " << v.front() << '\n';


  //对指定范围内的序列重新排序，它假设该序列是个有序堆 
  sort_heap (v.begin(),v.end());

  cout << "final sorted range :";
  //注意观察下面的 
  for (unsigned i=0; i<v.size(); i++)
  {
       cout << ' ' << v[i];
  } 

  return 0;
}

输出

initial max heap   : 30
max heap after pop : 20
max heap after push: 99
final sorted range : 5 10 15 20 99

二、题解

1)AC代码

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {

        make_heap(nums.begin(),nums.end());
        sort_heap(nums.begin(),nums.end());

        return nums;
    }
};

2)虽然没AC，但是观察到了现象

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {


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

        return nums;
    }
};

测试数据发现

[-1,4,3,2,2,0]

输出

[0,2,2,3,4,-1]

显然不对
所以，不能直接排序堆，要先建好堆，再排序。

最小堆

#include<bits/stdc++.h>
using namespace std;

bool cmp(int a,int b)
{
    return a<b;
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        vector<int> solution;
        for(int i=0;i<n;++i)
        {
            int temp;
            scanf("%d",&temp);
            solution.push_back(temp); 
        }

        //我需要最小堆
        make_heap(solution.begin(),solution.end(),cmp);

        for(int i=0;i<n;++i)
        {
            printf("%d\n",solution[i]);
        }


    }
    return 0;
}

测试

3
1 2 3

输出

3
2
1

应用举例

寻找第K大——传送门

第3章、STL之heap相关