C++ 大根堆源码实现/优先队列(堆)/小根堆解决多链表排序

素颜马尾好姑娘i 2022-10-06 06:51 284阅读 0赞

### 文章目录 ###

*  1. 堆介绍
 *  2. 大根堆C++的实现
 *  3. 应用大根堆解题
 *   *  3.1 第K个最大元素
     *  3.2 利用std自带的优先队列实现堆排序解决
     *  3.3 利用快排选择解决该题
 *  4. 小根堆解多个链表排序问题

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70]

# 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个最大元素][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 利用快排选择解决该题 ##

[快排具体思路请跳转][Link 1]

// 找到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个升序链表][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;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70]: /images/20221005/b59c7d317e004a43850a8e1dc47d44fb.png
[LeetCode 215_K]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
[Link 1]: https://blog.csdn.net/qq_32460819/article/details/119823151
[23. _K]: https://leetcode-cn.com/problems/merge-k-sorted-lists/