4、优先队列.md

### 优先队列

* 底层实现全部都是堆
* jdk 提供了 `Queue<String> q = new PriorityQueue<>();`（注意：是小堆）



#### [347. 前 K 个高频元素](https://leetcode-cn.com/problems/top-k-frequent-elements/)

难度中等629收藏分享切换为英文接收动态反馈

给定一个非空的整数数组，返回其中出现频率前 ***k\*** 高的元素。

 

**示例 1:**

```
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
```

**示例 2:**

```
输入: nums = [1], k = 1
输出: [1]
```





**题解**

```java
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer , Integer> map = new HashMap<>();
        for(int i : nums){
            map.put(i , map.getOrDefault(i , 0) + 1);
        }

        Queue<Integer> queue = new PriorityQueue<>((o1 , o2) -> map.get(o2) - map.get(o1));
        queue.addAll(map.keySet());

        int[] res = new int[k];
        for(int i = 0 ; i < k ; i ++){
            res[i] = queue.poll();
        }

        return res;
    }
}
```



#### [23. 合并K个升序链表](https://leetcode-cn.com/problems/merge-k-sorted-lists/)

难度困难1125收藏分享切换为英文接收动态反馈

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

 

**示例 1：**

```
输入：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
```

**示例 2：**

```
输入：lists = []
输出：[]
```

**示例 3：**

```
输入：lists = [[]]
输出：[]
```



**题解**

* 其实最简单的做法是直接全部都放到优先队列 priorityQueue（compareable 都不用重写），直接出队到空即可。

多路归并：

```java
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = null;
        if(lists == null){
            return res;
        }

        int[] idxs = new int[lists.length];
        ListNode resNow = null;

        while(true){
            int minIdx = 0 ;
            for(int i = 0 ; i < lists.length ; i ++){
                if(lists[minIdx] != null){
                     break;
                }
                minIdx ++;
            }

            if(minIdx == lists.length){
                break;
            }

            for(int i = minIdx ; i < lists.length ; i ++){
                if(lists[i] != null && lists[i].val < lists[minIdx].val){
                    minIdx = i;
                }
            }

            if(res == null){
                res = resNow = lists[minIdx];
                lists[minIdx] = lists[minIdx].next;
                resNow.next = null;
            }else {
                resNow.next = lists[minIdx];
                lists[minIdx] = lists[minIdx].next;
                resNow = resNow.next;
            }
        }

        return res;
    }
}
```
#### [703. 数据流中的第 K 大元素](https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/)

难度简单223收藏分享切换为英文接收动态反馈

设计一个找到数据流中第 `k` 大元素的类（class）。注意是排序后的第 `k` 大元素，不是第 `k` 个不同的元素。

请实现 `KthLargest` 类：

- `KthLargest(int k, int[] nums)` 使用整数 `k` 和整数流 `nums` 初始化对象。
- `int add(int val)` 将 `val` 插入数据流 `nums` 后，返回当前数据流中第 `k` 大的元素。

 

**示例：**

```
输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]

解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8
```

**题解**
```java
class KthLargest {

    PriorityQueue<Integer> queue;
    int k;

    public KthLargest(int k, int[] nums) {
        queue = new PriorityQueue<>();
        this.k = k;

        for(int i = 0 ; i < nums.length ; i ++){
            add(nums[i]);
        }
    }
    
    public int add(int val) {
        if(queue.size() < k){
            queue.offer(val);
        }else if(val > queue.peek()) {
            queue.poll();
            queue.offer(val);
        }

        return queue.peek();
    }
}

```