题解 | #最小的K个数#

class Solution {
void maxHeapify(vector<int>& heap, int index) {
    /*
        将指定的index视为根节点，对heap中index以后的部分的树进行最大堆化
    */
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int largest = index;

    if (left < heap.size() && heap[largest] < heap[left]) {
        largest = left;
    }
    if (right < heap.size() && heap[largest] < heap[right]) {
        largest = right;
    }

    if (largest != index) {
        swap(heap[index],
             heap[largest]);  // largest是左或右节点的索引，交换两个元素的位置
        maxHeapify(heap,
                   largest);  // 再以左或右节点为堆顶，维持其子树的最小堆性质
    }

vector<int>  buildMaxHeap_knums(vector<int>& heap, int k) {
  	/*
		由heap构建最大堆，返回整个最大堆的前k个元素
	*/
    for (int i = (heap.size() - 1) / 2; i >= 0; i--) {
        maxHeapify(heap, i);  // 从最大堆的底部往上进行堆化
    }
    vector<int> result(heap.begin(), heap.begin() + k);
    return result;
}
public:
vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
    vector<int> resultVec;
    if (input.size() == 0 || k == 0) {
        return resultVec;
    }
    if (input.size() <= k) {
        return input;
    }
    resultVec = buildMaxHeap_knums(input, k);
    for (int i = k; i < input.size(); i++) {
        if (resultVec[0] > input[i]) {
            resultVec[0] = input[i];
            maxHeapify(resultVec, 0);
        }
    }
    std::reverse(resultVec.begin(), resultVec.end());
    return resultVec;
    }
};