堆排序以及topk问题

大根堆排序流程:

• 建堆, 构建二叉树, 父节点均大于子节点
• 将堆首元素与堆尾元素交换

• 重新调整堆, 不包含堆尾元素

  void adjustHeap(std::vector<int> &arr, int p_ind, int size){
  int l_child = 2 * p_ind + 1;
  while(l_child < size){
      if(l_child + 1 < size && arr[l_child] < arr[l_child + 1])
          l_child++;
      if(arr[l_child] > arr[p_ind]){
          int temp = arr[p_ind];
          arr[p_ind] = arr[l_child];
          arr[l_child] = temp;
          p_ind = l_child; 
      }
      l_child = 2 * l_child + 1;
  }
  }
  
  void buildHeap(std::vecto<int> &arr){
  int size = arr.size();
  for(int i = size/2 -1; i>=0;i --){
      adjustHeap(arr, i, size);
  }
  }
  
  void heapSort(std::vector<int> &arr){
  buildHeap(arr);
  for(int i=arr.size()-1; i>=0;i--){
      int temp = arr[i];
      arr[i] = arr[0];
      arr[0] = temp;
      adjustHeap(arr, 0, i);
  }
  }
  

查找N个数中, 最小或最大的K个数,最大构造大根堆, 最小构造小根堆.

// 查找最大的K个数
vector<int> top_k(vector<int> arr, int k){
    vector<int> dest(arr);
    vector<int> res;
    buildHeap(dest);
    int size = dest.size();
    for(int i=size-1; i>=size-k;i--){
        int temp = dest[0];
        dest[0] = dest[i];
        dest[i] = temp;
        adjustHeap(dest, 0, i);
        res.push_back(dest[i]);
    }
    return res;
}