题解 | #【模板】堆#

最大堆：记录一下

#include <iostream>
#include <utility>   
#include <string>
#include <vector>

// 构建最大堆则从 size/2 开始进行下沉

void sink(std::vector<int> &max_heap, int sink_node, int size) {  // 下沉操作
  while (sink_node*2 <= size) {  // 二叉树性质：左孩子为2i
    int j = 2 * sink_node;
    if (j < size && max_heap[j] < max_heap[j+1]) {  // 有右孩子且右孩子更大
      j++;   // 指向最大孩子
    }
    if (max_heap[sink_node] >= max_heap[j]) {
      break;
    } else {  // 下沉结点不是最大，交换
      std::swap(max_heap[sink_node], max_heap[j]);
    }
    sink_node = j;   // 继续下沉
  }
}

void rise(std::vector<int> &max_heap, int size) {  // 一直上浮直到满足最大堆或者到达根
  while (size > 1 && max_heap[size] > max_heap[size/2]) {
    std::swap(max_heap[size], max_heap[size/2]);
    size /= 2;
  }
}

void pop(std::vector<int> &max_heap) {   // 取首元素->首尾交换->弹出尾元素->调整最大堆（下沉）
  std::cout << max_heap[1] << std::endl;
  
  max_heap[1] = max_heap[max_heap.size()-1];
  max_heap.pop_back();
  
  sink(std::forward<std::vector<int>&>(max_heap), 1, max_heap.size()-1);  // 转发，下沉结点， 大小
}

void push(std::vector<int> &max_heap, int val) {
  max_heap.push_back(val);
  rise(std::forward<std::vector<int>&>(max_heap), max_heap.size()-1);  // 最后一个结点进行上浮
}

int main(int argc, char *argv[]) {
  // 操作次数和存放指令
  int count;
  std::string op;
  
  std::cin >> count;
  std::cin.get();    // 读取缓冲的换行符
  
  // 大根堆的数据结构
  std::vector<int> max_heap(1);  // 从一开始编号
  
  while (--count >= 0) {
    std::getline(std::cin, op);   // 读取空格！
    
    if (op.substr(0, 4) == "push") {
      int val = std::stoi(op.substr(5));
      push(max_heap, val);
    } 
    if (max_heap.size() == 1) {  // 空直接跳过本次循环（一位多余）
      std::cout << "empty" << std::endl;
      continue;
    }
    if (op.substr(0, 3) == "top") {
      std::cout << max_heap[1] << std::endl;
    }
    if (op.substr(0, 3) == "pop") {
      pop(max_heap);
    }
  }
  
  return 0;
}