1 優(yōu)先隊列（Priority Queue）
優(yōu)先隊列與普通隊列的區(qū)別：普通隊列遵循先進先出的原則；優(yōu)先隊列的出隊順序與入隊順序無關(guān)沸久，與優(yōu)先級相關(guān)季眷。
優(yōu)先隊列可以使用隊列的接口，只是在實現(xiàn)接口時卷胯，與普通隊列有兩處區(qū)別子刮，一處在于優(yōu)先隊列出隊的元素應(yīng)該是優(yōu)先級最高的元素，另一處在于隊首元素也是優(yōu)先級最高的元素窑睁。
優(yōu)先隊列也可以使用不同的底層實現(xiàn)挺峡，不同底層實現(xiàn)的時間復(fù)雜度如下：
從上圖可以看出，使用"堆"這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)優(yōu)先隊列是比較高效的担钮。
2 二叉堆（Binary Heap）
二叉堆就是一棵滿足特殊性質(zhì)的二叉樹
首先橱赠，二叉堆是一棵完全二叉樹，"完全二叉樹"箫津，不一定是滿二叉樹狭姨，不滿的部分一定位于整棵樹的右下側(cè)。
其次苏遥，堆中某個節(jié)點的值總是不大于其父節(jié)點的值（最大堆）饼拍；相應(yīng)的，堆中的某個節(jié)點的值總是不小于其父節(jié)點的值（最小堆）田炭。
節(jié)點值的大小與其所處的層次沒有必然聯(lián)系师抄，即，最大堆中诫肠，只需保證每個節(jié)點不大于其父節(jié)點即可司澎，至于大不大于其父節(jié)點的兄弟節(jié)點，沒有任何關(guān)系栋豫。
可以用數(shù)組來存儲二叉堆挤安，如下圖所示：
用動態(tài)數(shù)組實現(xiàn)二叉堆的業(yè)務(wù)邏輯如下：
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data = new Array<>();
// 構(gòu)造函數(shù)
public MaxHeap(int capacity) {
data = new Array<>(capacity);
}
// 無參數(shù)構(gòu)造函數(shù)
public MaxHeap() {
data = new Array<>();
}
// 接收參數(shù)為數(shù)組的構(gòu)造函數(shù)
public MaxHeap(E[] arr) {
data = new Array<>(arr);
for (int i = parent(arr.length - 1); i >= 0; i--) {
SiftDown(i);
}
}
// 實現(xiàn)getSize方法，返回堆中的元素個數(shù)
public int getSize() {
return data.getSize();
}
// 實現(xiàn)isEmpty方法丧鸯，返回堆是否為空
public boolean isEmpty() {
return data.isEmpty();
}
// 返回完全二叉樹的數(shù)組表示中蛤铜，一個索引所表示的元素的父節(jié)點的索引
private int parent(int index) {
if (index == 0) {
throw new IllegalArgumentException("Index-0 doesn't have parent.");
}
return (index - 1) / 2;
}
// 返回完全二叉樹的數(shù)組表示中，一個索引所表示的元素的左孩子的索引
private int leftChild(int index) {
return index * 2 + 1;
}
// 返回完全二叉樹的數(shù)組表示中，一個索引所表示的元素的右孩子的索引
private int rightChild(int index) {
return index * 2 + 2;
}
// 實現(xiàn)add方法围肥，向堆中添加元素
public void add(E e) {
data.addLast(e);
SiftUp(data.getSize() - 1);
}
// 實現(xiàn)元素的上浮
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);
}
}
// 實現(xiàn)findMax方法剿干，查看堆中的最大元素
public E findMax() {
if (data.getSize() == 0) {
throw new IllegalArgumentException("Can not findMax when heap is empty.");
}
return data.get(0);
}
// 實現(xiàn)extractMax方法，取出堆中的最大元素
public E extractMax() {
E ret = findMax();
data.swap(0, data.getSize() - 1);
data.removeLast();
SiftDown(0);
return ret;
}
// 實現(xiàn)元素的下沉
private void SiftDown(int k) {
while (leftChild(k) < data.getSize()) {
int j = leftChild(k);
if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
j = rightChild(k);
// data[j]是leftChild和rightChild中的對大值
}
if (data.get(k).compareTo(data.get(j)) >= 0) {
break;
} else {
data.swap(k, j);
k = j;
}
}
}
// 實現(xiàn)replace方法穆刻，取出堆中的最大元素置尔，并替換為元素e
public E replace(E e) {
E ret = findMax();
data.set(0, e);
SiftDown(0);
return ret;
}
}
測試用動態(tài)數(shù)組實現(xiàn)的二叉堆
import java.util.Random;
public class Main {
public static void main(String[] args) {
int n = 1000000;
MaxHeap<Integer> maxHeap = new MaxHeap<>();
Random random = new Random();
for (int i = 0; i < n; i++) {
maxHeap.add(random.nextInt(Integer.MAX_VALUE));
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = maxHeap.extractMax();
}
for (int i = 1; i < n; i++) {
if (arr[i - 1] < arr[i]) {
throw new IllegalArgumentException("Error");
}
}
System.out.println("Test MaxHeap completed.");
}
}
二叉堆的時間復(fù)雜度分析
由于堆是一棵完全二叉樹，所以堆不會退化成鏈表氢伟。
3.用最大堆實現(xiàn)一個優(yōu)先隊列（Priority Queue）
實現(xiàn)優(yōu)先隊列的業(yè)務(wù)邏輯如下：
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
private MaxHeap<E> maxHeap;
// 構(gòu)造函數(shù)
public PriorityQueue() {
maxHeap = new MaxHeap<>();
}
// 實現(xiàn)getSize方法
@Override
public int getSize() {
return maxHeap.getSize();
}
// 實現(xiàn)isEmpty方法
@Override
public boolean isEmpty() {
return maxHeap.isEmpty();
}
// 實現(xiàn)getFront方法
@Override
public E getFront() {
return maxHeap.findMax();
}
// 實現(xiàn)enqueue方法
@Override
public void enqueue(E e) {
maxHeap.add(e);
}
// 實現(xiàn)dequeue方法
@Override
public E dequeue() {
return maxHeap.extractMax();
}
}
4.優(yōu)先隊列的應(yīng)用：從N個元素中榜轿，選出前M個
解決方案：使用優(yōu)先隊列，維護當前的M個元素朵锣，然后不斷更新元素谬盐，直到掃描完所有N個元素。
需要使用"最小堆"來進行底層的實現(xiàn)诚些，因為最終獲取的是前M個元素飞傀，通過最小堆的extractMin方法，可以不斷的剔除堆中的最小元素
也可以使用最大堆來實現(xiàn)诬烹，我們只要規(guī)定元素越小砸烦，優(yōu)先級越高。
使用最小堆實現(xiàn)的業(yè)務(wù)邏輯如下：
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeMap;
public class Solution2 {
private class Freq implements Comparable<Freq> {
public int e, freq;
public Freq(int e, int freq) {
this.e = e;
this.freq = freq;
}
public int compareTo(Freq another) {
if (this.freq < another.freq)
return -1;
else if (this.freq > another.freq)
return 1;
else
return 0;
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int num : nums) {
if (map.containsKey(num))
map.put(num, map.get(num) + 1);
else
map.put(num, 1);
}
PriorityQueue<Freq> pq = new PriorityQueue<>();
for (int key : map.keySet()) {
if (pq.size() < k)
pq.add(new Freq(key, map.get(key)));
else if (map.get(key) > pq.peek().freq) {
pq.remove();
pq.add(new Freq(key, map.get(key)));
}
}
LinkedList<Integer> res = new LinkedList<>();
while (!pq.isEmpty())
res.add(pq.remove().e);
return res;
}
}
