大根堆 小根堆

基本概念

查找数组中某个数的父结点和左右孩子结点，比如已知索引为i的数，那么

1.父结点索引：(i-1)/2（这里计算机中的除以2，省略掉小数）

2.左孩子索引：2*i + 1

3.右孩子索引：2*i + 2

所以上面两个数组可以脑补成堆结构，因为他们满足堆的定义性质：

大根堆：arr(i) > arr(2i+1) && arr(i) > arr(2i+2)

小根堆：arr(i) < arr(2i+1) && arr(i) < arr(2i+2)

原文链接： https://blog.csdn.net/u010452388/article/details/81283998

#include <iostream>
#include <queue>
using namespace std;

int main () {
  // 默认大根堆 
  //priority_queue<int> mypq;
  priority_queue<int, vector<int>, less<int>> mypq; // 大根堆
  //priority_queue<int, vector<int>, greater<int>> mypq; // 小根堆

  mypq.push(10);
  mypq.push(20);
  mypq.push(15);

  std::cout << "mypq.top() is now " << mypq.top() << '\n';
  // 小根堆
  priority_queue<int, vector<int>, greater<int> > c;

  return 0;
}

std::priority_queue::pop

http://www.cplusplus.com/reference/queue/priority_queue/pop/

// priority_queue::push/pop
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue

int main () {
  std::priority_queue<int> mypq;

  mypq.push(30);
  mypq.push(100);
  mypq.push(25);
  mypq.push(40);

  std::cout << "Popping out elements...";
  while (!mypq.empty()) {
     std::cout << ' ' << mypq.top();
     mypq.pop();
  }
  std::cout << '\n';

  return 0;
}

Output:

Popping out elements... 100 40 30 25

应用 接水问题 https://www.acwing.com/problem/content/444/

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    priority_queue<int, vector<int>, greater<int>> heap; // 小根堆
    for (int i = 0; i < m; i ++ ) {
        heap.push(0);
    }
    while (n --) {
        int x;
        cin >> x;
        int t = heap.top();
        heap.pop();
        heap.push(t + x);
    }
    for (int i = 0; i < m - 1; i ++ ) {
        heap.pop();
    }
    cout << heap.top() << endl;
    return 0;
}