堆排序 C++ 代码

class Solution {
public:
    int size = 0, num = 0;
    vector<int> heap;
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        heap = vector<int>(k);
        num = k;
        for(int i = 0; i < (int)input.size(); i++)
        {
            heapSort(input[i]);
        }

        sort(heap.begin(), heap.end());
        cout << heap.size() << endl;
        return heap;
    }

    void heapSort(int x)
    {
        if(size < num)
        {
            heap[size++] = x;
            if(size == num)
            {
                makeMinHeap(heap);
                size++;
            }
        }
        else if(heap[0] > x)
        {
            heap[0] = x;
            minHeapDown(heap, 0, num);
        }
    }

    void makeMinHeap(vector<int>& A)
    {
       int n = A.size();
       for(int i = n / 2 - 1; i >= 0; i--) 
            minHeapDown(A, i, n);
    }

    //维护一个大顶堆，堆中最大的元素在第一个
    void minHeapDown(vector<int>& A, int i, int n)
    {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if(left > n) return;
        int max = left;
        if(right >= n)
            max = left;
        else
        {
            if(A[right] > A[left])
                max = right;
        }
        if(A[i] >= A[max])
            return;
        swap(A[i], A[max]);
        minHeapDown(A, max, n);
    }

};