最近一次面试被问到的题，太紧张了没答出来，重新巩固下~~

堆的基本知识和应用

说起堆，更多能联想到的是堆排序，那个时间复杂度为nlogn的排序算法，以及topK问题的应用。
而堆的实现最关键的操作是怎么上浮或者下陷，有关堆的知识可以参考这里（链接）

堆的上浮和下陷

下面我们以最大堆为例，先来实现一下核心的下陷操作（上浮也同理）：

void Max_Heapify_core(vector<int> &a, int i) {
  int largest = i;
  int left = 2*i;
  int right = 2*i + 1; //堆由于是完全二叉树，可以放在一个数组里面表示
  if(left < heapsize && a[left] > a[i]) largest = left;
  if(right < heapsize && a[right] > a[i]) largest = right;
  if(largest != i) {
    swap(a,largest,i); //交换两个值
    Max_Heapify_core(a,largest);
  }
}

将无序数组构建为堆

有了上面那个核心的操作，便可以将一个无序数组变为一个最大堆（吐槽下我自己，面试的时候居然想要排序整个数组~~还是太容易紧张了）

void Build_Max_Heapify(vector<int> &a) {
  for(int i = Parent(a.size()-1); i >=0; --i) { //求得最后一个叶子节点的父节点
    Max_Heapify_core(a,i);
  }
}

堆排序

void Heapify_Sort(vector<int> &a) {
  Build_Max_Heapify(a);
  for(int i = a.size()-1; i >= 1; --i) {
    swap(a,0,i);
    heapsize -= 1;   //将最大值放在末尾，再将前面的数组生成最大堆，持续这个过程
    Max_Heapify_core(a,0);
  }
}