1. 堆介绍

优先队列（priority queue）可以在 O(1) 时间内获得最大值，并且可以在 O(logn)时间内取出
最大值或插入任意值。
优先队列常常用堆（heap）来实现。堆是一个完全二叉树，其每个节点的值总是大于等于子
节点的值。实际实现堆时，我们通常用一个数组而不是用指针建立一个树。这是因为堆是完全二
叉树，所以用数组表示时，位置 i 的节点的父节点位置一定为i/2，而它的两个子节点的位置又一定分别为 2i 和 2i+1。

2. 大根堆C++的实现

这里需要注意的是, 堆在数组中的存储是从heap[1]开始, 这是为了满足i的父节点是i/2, 子节点是2i和2i+1; 否则是不对滴, 所以这里将heap[0]随意赋值

以下是堆的实现方法，其中最核心的两个操作是上浮和下沉：如果一个节点比父节点大，那
么需要交换这个两个节点；交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操
作，我们称之为上浮；类似地，如果一个节点比父节小，也需要不断地向下进行比较和交换操作，
我们称之为下沉。如果一个节点有两个子节点，我们总是交换最大的子节点。

class Heap{
private:
    int N = 0;
    vector<int> heap = {0};// 这个没有意义的是
public:
    // 获取最大值
    int top(){
        return heap[1];
    }

    // 数据首先插入末尾 ,然后上浮
    void push(int k){
        heap.push_back(k); // 直接放到后面, 然后上浮
        this->N++;
        swim(heap.size()-1); 
        // print();
    }

    // 删除最大值, 最后一位放到开头, 然后在下沉
    void pop(){
        heap[1] = heap.back(); // 最后一位上位, 然后在下沉
        heap.pop_back();
        this->N--;
        sink(1);  
        // print();
    }

    // 下面是小根堆
    // 上浮, 在每次插入数据的时候
    void swim(int pos){
        while(pos>1 && heap[pos/2] < heap[pos]){  // 子节点大于父节点 
            swap(heap[pos/2] , heap[pos]); // 交换两个位置
            pos /= 2; // 节点切换到上一层 
        }
    }

    // 下沉, 在每次删除数据的时候
    void sink(int pos){
        int i; 
        while(2*pos <=N){ //2pos是子节点
            i = 2*pos;
            if(i<N && heap[i]<heap[i+1]) i++; // i指向子节点中最大的
            if(heap[pos] >= heap[i]) break; // 已经找到pos应该的位置了
            swap(heap[pos], heap[i]);
            pos = i;
        }
    }
    
    void print(){
        cout<<"打印heap所有值"<<endl;
		for(const auto& num: heap){
            cout<< num<< " ";
        }cout<<endl;
    }
};

void test(){
    Heap* heap = new Heap();
    heap->push(2);heap->print();
    heap->push(17);heap->print();
    heap->push(7);heap->print();
    heap->push(3);
    heap->push(19);
    heap->print();
}

3. 应用大根堆解题

3.1 第K个最大元素

本文主要围绕解决下面215题展开的
LeetCode 215题数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

解题思路:

• 一种是快排解题思路, 找到对应的倒数第K个值即可
• 另一种利用堆先排序, 然后在pop, 大根堆pop到k-1个值, 第k个即为所求
• 本文主要是实现堆, 虽然可以用优先队列进行实现, 但是面试官当然不是希望你用个优先队列的代码, 所以这里用C++的vector数组实现一个大根堆;

这里利用上面实现的大根堆解决该题

int findKthLargest(vector<int>& nums, int k) {
    Heap* heap_big = new Heap(); 
    int n=nums.size();
    for(const auto& num: nums){
        heap_big->push(num);
    }

    for(int i=0; i<k-1; i++){
        heap_big->pop();
    }
    // cout<<heap_big->top()<<endl;
    return heap_big->top();
}

3.2 利用std自带的优先队列实现堆排序解决

#include <queue> // priority_queue
int findKthLargest(vector<int>& nums, int k) {
    // priority_queue<int, vector<int>, greater<int> > a; // 小根堆
    // priority_queue<int, vector<int>, less<int> > b; // 大根堆
    priority_queue<int> heap_big; // 创建大根堆, 默认
    int n=nums.size();
    for(const auto& num: nums){
        heap_big.push(num);
    }
    for(int i=0; i<k-1; i++){
        heap_big.pop();
    }
    return heap_big.top();
}

3.3 利用快排选择解决该题

快排具体思路请跳转

// 找到val的绝对位置, 并且返回val的绝对位置, 同时将val的左右进行分类
int quickSelection(vector<int>& nums, int low, int high){
    int l=low, h=high;
    int val = nums[low];
    while(low<high){ 
        while(low<high && val<=nums[high]) high--;
        nums[low] = nums[high];
        while(low<high && nums[low]<=val) low++;
        nums[high] = nums[low];
    }
    nums[low] = val;
    return low;
}

// 找出第K大的值
int findKthLargest(vector<int>& nums, int k) {
    if(nums.size() < k) return -1;
    int n=nums.size(); 
    int destination = n-k;
    int low=0, high=n-1;
    while(true){
        int mid = quickSelection(nums, low, high);
        if(mid == destination) return nums[mid];
        else if(mid < destination) low = mid+1;
        else high = mid-1;  
    }
}

4. 小根堆解多个链表排序问题

注意的知识点是:

1. map.count(key)返回值只有0,1 用来判定key 的存在性更加方便
2. 堆排的定义方式 priority_queue<ListNode*, vector<ListNode*>, myCompare> temp;

23. 合并K个升序链表

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

class Solution {
public:
    struct myCompare{
        bool operator()(ListNode *H1, ListNode *H2){
            return H1->val > H2->val; // 小根堆排序
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;

        // 创建优先队列, 保存的值是ListNode*, 底层存储是容器, 小根堆
        priority_queue<ListNode*, vector<ListNode*>, myCompare> temp;

        // 先将多个链表头都放到优先队列, 小根堆中
        for(ListNode* head : lists){
            if(head){
                temp.push(head);
            }
        }

        ListNode *dummy = new ListNode(0);
        ListNode * cur = dummy;

        while(!temp.empty()){
            cur->next = temp.top(); // 最小节点拿出来
            temp.pop(); // 出堆
            cur = cur->next; // 结果链表指针后移
            if(cur->next){
                temp.push(cur->next); // 最小节点下一个节点放进去
            }
        }

        return dummy->next;
    }
};