堆排序以及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;
}