优先队列
普通队列：先进先出；后进后出
优化队列：出队顺序和入队顺序无关，只跟优先级相关。
优化队列案例：
医生做手术，只按伤势来判断，动态选择伤势最严重的病人，而不管伤者来的先后顺序 。
系统的任务调度 (动态选择优先级最高的任务执行) 。
AI攻击敌人，也是动态去攻击优先级最高的敌人，优先级的定义由开发者定义（距离最近、体积最大、攻击力最高等等）。
底层实现分析
普通线性结构 ： 入队 O(1) 级别，出队 O(n) 级别 。
顺序线性结构 ： 入队 O(n) 级别，出队 O(1) 级别 。
堆 ： 入队 O(logn) 级别，出队 O(logn) 级别 。
二叉堆
二叉堆是一棵完全二叉树。节点都是从左到右插入进来的，最后一层一定是叶子节点，不满的部分一定是在右边部分。简单来说，就是把元素排列成树的形状，元素从左到右一层层的插入进来，那么元素不够的时候，缺失的部分一定是在最后一层的右边。
堆中某个节点的值总是不大于其父节点的值。（最大堆）
用数组来存储二叉堆
最大堆的代码实现
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap() {
data = new Array<>();
}
public MaxHeap(E[] arr) {
data = new Array<>(arr);
// 从最后一个节点的父子节点开始处理，少了一半的处理节点数量
for (int i = parent(data.getSize() - 1); i >= 0; i--) {
siftDown(i);
}
}
public MaxHeap(int capacity) {
data = new Array<>(capacity);
}
/**
* 向堆中添加元素
*/
public void add(E e) {
data.addLast(e);
siftUp(data.getSize() - 1);
}
/**
* 元素值上浮过程
*/
private void siftUp(int k) {
// 不是根节点，而且父节点比孩子节点小
while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
// 则交换两者之间的值
data.swap(k, parent(k));
// 将当前索引变成父节点索引
k = parent(k);
}
}
/**
* 看堆中的最大元素
*/
public E findMax() {
if (isEmpty()) {
throw new IllegalArgumentException("Can not findMax when heap is empty.");
}
return data.get(0);
}
/**
* 取出堆中最大的元素
*/
public E extractMax() {
// 先拿到最大的元素值
E ret = findMax();
// 根元素和最后的一个元素交换值
data.swap(0, data.getSize() - 1);
// 删除最后一个元素
data.removeLast();
// 将元素进行下沉操作
siftDown(0);
return ret;
}
/**
* 元素值下沉过程
*/
private void siftDown(int k) {
// 如果不是叶子节点，则循环处理
while (leftChild(k) < data.getSize()) {
// 在此轮循环中,data[k]和data[j]交换位置
int j = leftChild(k); // 此时 j 代表左孩子节点
if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
// 如果有右孩子且右孩子比左孩子大，则将索引加1，此时 j 代表右孩子节点
j++;
}
// data[j] 是 leftChild 和 rightChild 中的最大值
if (data.get(k).compareTo(data.get(j)) > 0) {
break;
}
data.swap(k, j);
k = j;
}
}
/**
* 取出堆中的最大元素，并且替换成元素e
*/
public E replace(E e) {
E ret = findMax();
// 将堆中最大的元素替换为 e
data.set(0, e);
// 下沉操作
siftDown(0);
return ret;
}
/**
* 返回堆中的元素个数
*/
public int size() {
return data.getSize();
}
/**
* 返回一个布尔值, 表示堆中是否为空
*/
public boolean isEmpty() {
return data.isEmpty();
}
/**
* 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
*/
private int parent(int index) {
if (index == 0) {
throw new IllegalArgumentException("index-0 does not have parent.");
}
return (index - 1) / 2;
}
/**
* 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
*/
private int leftChild(int index) {
return index * 2 + 1;
}
/**
* 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
*/
private int rightChild(int index) {
return index * 2 + 2;
}
}
底层为最大堆的优先队列
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
private MaxHeap<E> heap;
public PriorityQueue() {
heap = new MaxHeap<>();
}
@Override
public int getSize() {
return heap.size();
}
@Override
public boolean isEmpty() {
return heap.isEmpty();
}
@Override
public void enqueue(E e) {
heap.add(e);
}
@Override
public E dequeue() {
return heap.extractMax();
}
@Override
public E getFront() {
return heap.findMax();
}
}
LeetCode 的题目解答
347.前K个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
基于自己实现的优先队列来解答
public class Soluction347 {
public static void main(String[] args) {
int[] arr = {1, 1, 1, 2, 2, 3};
System.out.println(topKFrequent(arr, 2));
}
/**
* 基于自己实现的优先队列来处理，复杂度为 O(nlongK)
*/
public static List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
for (int num : nums) {
if (treeMap.containsKey(num)) {
treeMap.put(num, treeMap.get(num) + 1);
} else {
treeMap.put(num, 1);
}
}
PriorityQueue<Freq> pq = new PriorityQueue<Freq>();
for (Integer key : treeMap.keySet()) {
if (pq.getSize() < k) {
// 先入队 K 个元素
pq.enqueue(new Freq(key, treeMap.get(key)));
} else {
// 第 K+1 个元素开始做处理
if (treeMap.get(key) > pq.getFront().freq) {
// 出队最小频次节点（处于树的最顶的节点）
pq.dequeue();
// 将新节点放进来
pq.enqueue(new Freq(key, treeMap.get(key)));
}
}
}
LinkedList<Integer> linkedList = new LinkedList<>();
while (!pq.isEmpty()) {
linkedList.add(pq.dequeue().e);
}
return linkedList;
}
private static class Freq implements Comparable<Freq> {
int e, freq;
public Freq(int e, int freq) {
this.e = e;
this.freq = freq;
}
@Override
public int compareTo(Freq another) {
// 频次越大，优先级越低
if (this.freq > another.freq) {
return -1;
} else if (this.freq < another.freq) {
return 1;
} else {
return 0;
}
}
}
}
基于标准库的优先队列来解答
注意：系统库的优先队列默认是用最小堆来实现的。
public class Soluction347 {
public static void main(String[] args) {
int[] arr = {1, 1, 1, 2, 2, 3};
System.out.println(topKFrequent(arr, 2));
}
/**
* 基于标准库的优先队列来处理，复杂度为 O(nlongK)
*/
public static List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
for (int num : nums) {
if (treeMap.containsKey(num)) {
treeMap.put(num, treeMap.get(num) + 1);
} else {
treeMap.put(num, 1);
}
}
// 在构造函数中传入一个比较器(定义优先级)
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(treeMap::get));
for (Integer key : treeMap.keySet()) {
if (pq.size() < k) {
// 先入队 K 个元素
pq.add(key);
} else {
// 第 K+1 个元素开始做处理
if (treeMap.get(key) > treeMap.get(pq.peek())) {
// 出队最小频次节点（处于树的最顶的节点）
pq.remove();
// 将新节点放进来
pq.add(key);
}
}
}
LinkedList<Integer> linkedList = new LinkedList<>();
while (!pq.isEmpty()) {
linkedList.add(pq.remove());
}
return linkedList;
}
}