2020-03-20 刷题2（堆）

最小的k个数

采用最大堆（优先队列）的做法，首先将前k个元素入堆，剩下的元素依次与堆顶元素比较，如果更小，就将堆顶元素弹出，小元素入堆。最后堆中的k个元素就是最小的k个数。每次入堆的代价是O(logn)，所以总的时间代价是O(klogn).

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> min_k;
        priority_queue<int> heap;
        int i = 0;
        for(; i < k; i++)
            heap.push(arr[i]);
        while(k && i < arr.size()){
            if(arr[i] < heap.top()){
                heap.pop();
                heap.push(arr[i]);
            }
            i++;
        }
        for(int i = 0; i < k; i++){
            min_k.push_back(heap.top());
            heap.pop();
        }
        return min_k;
    }
};

23 合并k个有序列表

还是用堆来做的，以ListNode*为节点建一个堆，需要重载一下比较运算符，重载的操作还是要记一下的。

class Solution {
public:
    struct cmp{
        bool operator()(ListNode *a, ListNode *b){
            return a -> val > b -> val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
        ListNode *merge_list = new ListNode(0), *cur = merge_list;
        int k = lists.size();
        for(int i = 0; i < k; i++){
            if(lists[i] != NULL)
                heap.push(lists[i]);
        }
        while(!heap.empty()){
            ListNode *tmp = heap.top();
            heap.pop();
            if(tmp -> next != NULL)
                heap.push(tmp -> next);
            cur -> next = tmp;
            cur = tmp;
        }
        return merge_list -> next;
    }
};