[toc]
一、優(yōu)先隊列
普通隊列：先進(jìn)先出，后進(jìn)后出
優(yōu)先隊列：出隊順序呢入隊順序無關(guān)；和優(yōu)先級相關(guān)
優(yōu)先隊列的各種實現(xiàn)比較
| 結(jié)構(gòu) | 入隊 | 出隊(拿出最大的元素) |
|---|---|---|
| 普通線性結(jié)構(gòu) | O(1) | O(n) |
| 順序線性結(jié)構(gòu) | O(n) | O(1) |
| 堆 | O(logn) | O(logn) |
二、二叉堆 Binary Heap
- 二叉堆是一個完全二叉樹
注意：滿二叉樹是值除了葉子節(jié)點，其他節(jié)點都含有左右子節(jié)點
完全二叉樹：不一定是一個滿二叉樹，但是缺失的那部分一定在整棵樹的右下側(cè)；也就是從上到下，從左到右，一層一層的鋪，鋪滿一層再鋪下一層，把元素順序排列成樹的形狀，
- 最大堆（同樣可以定義最小堆) 堆中某個節(jié)點的值，總是不大于其父節(jié)點的值(子節(jié)點的值永遠(yuǎn)小于等于父節(jié)點的值)
注意：二叉堆不同層元素之間無明確比較性，層級越淺不一定比層級更深的大。
二叉堆(完全二叉樹)與數(shù)組索引之間的關(guān)系
利用動態(tài)數(shù)組儲存二叉堆，從上到下，從左到右，從0開始索引編號，對于第i節(jié)點的左孩子的索引為2i + 1 , 右孩子為2i + 2，而對于第i節(jié)點的父節(jié)點，索引為(i - 1) /2
二叉堆在內(nèi)存中是以動態(tài)數(shù)組儲存的，而邏輯上是用二叉樹的思想實現(xiàn)的
這里用的數(shù)組為之前實現(xiàn)的動態(tài)數(shù)組Array
SiftUP操作：向最大堆中添加節(jié)點，先將節(jié)點添加到完全二叉樹中，然后將節(jié)點與父節(jié)點比較，如果大于父節(jié)點，就進(jìn)行交換。
SiftDown：從堆中取出元素：具體的算法思想是將堆頂上的值返回，然后將完全二叉樹最后一個元素放在堆頂，然后將堆最后一個元素刪除。將頂?shù)脑嘏c孩子進(jìn)行比較，如果不存在左孩子，則不需要置換，如果存在左孩子且存在右孩子且右孩子大于左孩子，則將節(jié)點與右孩子進(jìn)行置換，否則與左孩子進(jìn)行置換。再根據(jù)情況判斷是否進(jìn)入下一個循環(huán)。
詳細(xì)請參考下面的代碼MaxHeap類。
replace
取出最大元素后，放入一個新的元素，先將最大元素返回，然后將最大元素替換為一個新的元素，然后進(jìn)行Sift Down,這樣復(fù)雜度就變?yōu)镺(logn)級別的了。
Heapify
通過構(gòu)造函數(shù)實現(xiàn)，傳入一個數(shù)組，將其轉(zhuǎn)換為一個最大堆，
算法思想：找到完全二叉樹中最后一個含有子節(jié)點的節(jié)點索引(其實就為動態(tài)數(shù)組最后一個節(jié)點的父節(jié)點)，以此位置為基礎(chǔ)，倒著遍歷完全二叉樹的節(jié)點，反復(fù)進(jìn)行shiftDown操作。這樣操作的復(fù)雜度為O(logn)
- Array.java 動態(tài)數(shù)組中添加的部分置換代碼
/**一個新的構(gòu)造函數(shù)*/
/** 交換兩個索引對應(yīng)的值 */
public void swap(int i, int j){
if(i < 0 || i >= size || j < 0 || j >= size)
throw new IllegalArgumentException("Index is illegal.");
E t = data[i];
data[i] = data[j];
data[j] = t;
}
- 最大堆
public class MaxHeap<E extends Comparable<E>> {
/**引入之前寫的動態(tài)數(shù)組類Array*/
private Array<E> data;
public MaxHeap(int capacity){
data = new Array<>(capacity);
}
public MaxHeap(){
data = new Array<>();
}
/**返回堆中的元素個數(shù)*/
public int size(){
return data.getSize();
}
/**返回一個布爾值，表示堆中是否為空*/
public boolean isEmpty(){
return data.isEmpty();
}
/**找到一個索引的父節(jié)點*/
private int parent(int index){
if(index == 0)
throw new IllegalArgumentException("Index-0 doesn't have parent.");
return (index - 1) / 2;
}
/**找到一個索引的左子節(jié)點*/
private int leftChild(int index){
return index * 2 + 1;
}
/**找到一個索引的右子節(jié)點*/
private int rightChild(int index){
return index * 2 + 2;
}
/**向堆中添加元素 sift up
* 將節(jié)點添加到樹中，反復(fù)與父節(jié)點比較，
* 為了滿足最大堆可以將其進(jìn)行反復(fù)交換*/
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(data.getSize() == 0)
throw new IllegalArgumentException("Can not findMax when heap is empty.");
return data.get(0);
}
/**取出堆中最大的元素*/
public E extrackMax(){
E ret = findMax();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return ret;
}
/**shiftDown的思想實現(xiàn)*/
private void siftDown(int k){
// 如果存在左節(jié)點則進(jìn)行循環(huán)（不可能只有右節(jié)點，這是個完全二叉樹）
while(leftChild(k) < data.getSize()){
/**獲得最大子節(jié)點的索引*/
// j 暫存可能會被替換的索引
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中最大的
/**將父節(jié)點與最大子節(jié)點比較*/
if(data.get(k).compareTo(data.get(j)) >= 0)
break;
data.swap(k, j);
k = j;
}
}
}
三、優(yōu)先隊列
- 優(yōu)先隊列實現(xiàn)的接口
Queue.java
public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
- 優(yōu)先隊列的實現(xiàn)
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
private MaxHeap<E> maxHeap;
public PriorityQueue(){
maxHeap = new MaxHeap<>();
}
@Override
public int getSize(){
return maxHeap.size();
}
@Override
public boolean isEmpty(){
return this.maxHeap.size() == 0;
}
@Override
public E getFront(){
return maxHeap.findMax();
}
@Override
public void enqueue(E e){
maxHeap.add(e);
}
@Override
public E dequeue(){
return maxHeap.extrackMax();
}
}
- 測試代碼
Main.java
import java.util.Random;
public class Main {
public static double testHeap(Integer[] testData, boolean isHeapify){
long startTime = System.nanoTime();
/**指定泛型的類型*/
MaxHeap<Integer> maxHeap;
if(isHeapify)
maxHeap = new MaxHeap<>(testData);
else {
maxHeap = new MaxHeap<>();
for(Integer data : testData)
maxHeap.add(data);
}
int[] arr = new int[testData.length];
for(int i = 0; i < testData.length; i ++)
arr[i] = maxHeap.extrackMax();
for(int i = 1; i < testData.length; i ++){
if(arr[i - 1] < arr[i])
throw new IllegalArgumentException("error");
}
System.out.println("Test MaxHeap completed.");
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] agrs){
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.extrackMax();
}
for(int i = 1; i < n; i++){
if(arr[i - 1] < arr[i])
throw new IllegalArgumentException("Error");
}
System.out.println("Test MaxHeap completed");
/**============================================*/
int m = 1000000;
Random random2 = new Random();
Integer[] testData = new Integer[m];
for(int i = 0; i < m; i ++){
testData[i] = random2.nextInt(Integer.MAX_VALUE);
}
double time1 = testHeap(testData, false);
System.out.println("Without heapify: " + time1 + " s");
double time2 = testHeap(testData, true);
System.out.println("With heapify: " + time2 + " s");
}
}
四、Leetcode上的347號問題
在N個元素中選出前M個元素(N遠(yuǎn)遠(yuǎn)大于M)
并歸排序時間復(fù)雜度: NlogN
使用優(yōu)先隊列（基于堆）：NlogM
思路：使用優(yōu)先隊列，只維護(hù)當(dāng)前看得到的前M個元素
多態(tài)compareTo方法實現(xiàn)。
347號問題：請點擊Leecode進(jìn)行查看
1、用自己實現(xiàn)的最大堆實現(xiàn)
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
public class Solution {
/**重寫入堆的優(yōu)先級，implements了Comparable
* 必須實現(xiàn)compareTo方法*/
private class Freq implements Comparable<Freq> {
private int e, freq;
private Freq(int e, int freq) {
this.e = e;
this.freq = freq;
}
/**重寫compareTo方法，重新定義優(yōu)先級的規(guī)則
* 從而利用最大堆來儲存'最小堆'，這波操作特別六*/
@Override
public int compareTo(Freq another) {
if(this.freq < another.freq)
return 1;
else if(this.freq > another.freq)
return -1;
else
return 0;
}
}
/**List是一個接口，需要制定底層的實現(xiàn)，這里用的ArrayList進(jìn)行實現(xiàn)的*/
public List<Integer> topKFrequent(int[] nums, int k) {
/**先用map統(tǒng)計詞頻*/
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);
}
/**優(yōu)先隊列，最大堆
* 利用最大堆儲存一個最小堆(很神奇是吧)，
* 利用優(yōu)先隊列只保存所需個數(shù)的長度，數(shù)頂是當(dāng)前最小頻率的數(shù)
* 然后將之后遍歷得到的頻率與最小的比較，如果比最小的大，就將
* 頂?shù)臄?shù)出隊列，然后將當(dāng)前的入隊列并自動排序，當(dāng)遍歷完map中所有
* 的key,優(yōu)先隊列里面保存的就是所需的前頻次最高的數(shù)*/
PriorityQueue<Freq> pq = new PriorityQueue<>();
for(int key: map.keySet()) {
if(pq.getSize() < k)
pq.enqueue(new Freq(key, map.get(key)));
else if(map.get(key) > pq.getFront().freq) {
pq.dequeue();
pq.enqueue(new Freq(key, map.get(key)));
}
}
LinkedList<Integer> res = new LinkedList<>();
while(!pq.isEmpty()) {
res.add(pq.dequeue().e);
}
return res;
}
private static void printList(List<Integer> nums) {
for(int num : nums)
System.out.println(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {1,1,1,1,1,2,2,2,3,3,3,4,4,6,7,8,0};
int k = 4;
printList((new Solution()).topKFrequent(nums, k));
}
}
2、使用Java標(biāo)準(zhǔn)類庫中提供的PriorityQueue(底層是使用的最小堆)實現(xiàn)
- (基礎(chǔ)版)使用一個新的類Freq，實現(xiàn)比較接口Comparable進(jìn)行實現(xiàn)
/**使用Java標(biāo)準(zhǔn)庫中 PriorityQueue，是用最小堆實現(xiàn)的
* 但是可以自己傳入一個 自定義優(yōu)先級*/
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
import java.util.PriorityQueue;
public class MySolution {
public class Freq implements Comparable<Freq> {
public int e, freq;
public Freq(int e, int freq) {
this.e = e;
this.freq = freq;
}
// 定義優(yōu)先級，
@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 List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
// 利用map統(tǒng)計詞頻
for(int num : nums) {
if(map.containsKey(num))
map.put(num, map.get(num) + 1);
else
map.put(num, 1);
}
// 利用優(yōu)先隊列儲存,最小堆，
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;
}
private static void printList(List<Integer> nums) {
for(int num : nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {1,1,1,1,2,2,2,2,3,3,4,5,6,7,7};
int k = 2;
printList((new MySolution()).topKFrequent(nums, k));
}
}
- (進(jìn)階版)自定義一個比較的方法，交給優(yōu)先隊列(通過構(gòu)造函數(shù))，告訴優(yōu)先隊列使用自己實現(xiàn)比較的方法
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Comparator;
public class MySolution {
public class Freq {
public int e, freq;
public Freq(int e, int freq) {
this.e = e;
this.freq = freq;
}
}
/**實現(xiàn)Comparator，定制比較的方法*/
public class FreqComparator implements Comparator<Freq> {
@Override
public int compare(Freq a, Freq b) {
return a.freq - b.freq;
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
// 利用map統(tǒng)計詞頻
for(int num : nums) {
if(map.containsKey(num))
map.put(num, map.get(num) + 1);
else
map.put(num, 1);
}
// 調(diào)用定制比較方法的構(gòu)造函數(shù)。
PriorityQueue<Freq> pq = new PriorityQueue<>(new FreqComparator());
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;
}
private static void printList(List<Integer> nums) {
for(int num : nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {1,1,1,1,2,2,2,2,3,3,4,5,6,7,7};
int k = 2;
printList((new MySolution()).topKFrequent(nums, k));
}
}
- (高階版)在2的基礎(chǔ)上使用匿名函數(shù),并去掉Freq類
package maxHeap;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Comparator;
public class MySolution {
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
// 利用map統(tǒng)計詞頻
for(int num : nums) {
if(map.containsKey(num))
map.put(num, map.get(num) + 1);
else
map.put(num, 1);
}
// 調(diào)用定制比較方法的構(gòu)造函數(shù)。使用匿名函數(shù)的方式
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return map.get(o1) - map.get(o2);
}
});
for(int key: map.keySet()) {
if(pq.size() < k)
pq.add(key);
else if(map.get(key) > map.get(pq.peek())) {
pq.remove();
pq.add(key);
}
}
LinkedList<Integer> res = new LinkedList<>();
while(!pq.isEmpty()) {
res.add(pq.remove());
}
return res;
}
private static void printList(List<Integer> nums) {
for(int num : nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {1,1,1,1,2,2,2,2,3,3,4,5,6,7,7};
int k = 2;
printList((new MySolution()).topKFrequent(nums, k));
}
}
- (終極牛逼版)使用lamda表達(dá)式的方式
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Comparator;
public class MySolution {
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
// 利用map統(tǒng)計詞頻
for(int num : nums) {
if(map.containsKey(num))
map.put(num, map.get(num) + 1);
else
map.put(num, 1);
}
/**使用lamda的方式，定義優(yōu)先隊列的優(yōu)先級*/
PriorityQueue<Integer> pq = new PriorityQueue<>(
(a, b) -> map.get(a) - map.get(b)
);
for(int key: map.keySet()) {
if(pq.size() < k)
pq.add(key);
else if(map.get(key) > map.get(pq.peek())) {
pq.remove();
pq.add(key);
}
}
LinkedList<Integer> res = new LinkedList<>();
while(!pq.isEmpty()) {
res.add(pq.remove());
}
return res;
}
private static void printList(List<Integer> nums) {
for(int num : nums)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {1,1,1,1,2,2,2,2,3,3,4,5,6,7,7};
int k = 3;
printList((new MySolution()).topKFrequent(nums, k));
}
}
五、和堆相關(guān)的更多話題和廣義隊列
| d叉堆 d-ary heap | 索引堆 | 二項堆 | 斐波那契堆 |
|---|---|---|---|
| 時間復(fù)雜度為NlogdM,對應(yīng)的代價就是 | 比較高級 |
- 廣義隊列 支持一個普遍的接口
廣義隊列接口.png
普通隊列：先進(jìn)先出
優(yōu)先隊列：優(yōu)先級高的先出
棧，也可以理解為一個隊列
六、整合案例：實現(xiàn)一個比較器來定義二叉堆元素的優(yōu)先級，默認(rèn)為最小堆
從底層到測試實現(xiàn)的思路
Array.java :
Array是一個動態(tài)數(shù)組，可以根據(jù)儲蓄的容量自動擴(kuò)容和自動縮容，自動擴(kuò)容和縮容也進(jìn)行了邊界的優(yōu)化。這里就不展示全部的代碼了在我前面的一篇筆記 動態(tài)數(shù)組中詳細(xì)介紹了實現(xiàn)的思路。
MinHeap.java
MinHeap是一個最小堆，基于Array實現(xiàn)的，支持自定義優(yōu)先級排序只需要在構(gòu)造方法中傳入一個比較器(規(guī)定返回值為int,小于等于0則第一個參數(shù)的優(yōu)先級高，否則第二個優(yōu)先級高)，如果不傳入比較器，默認(rèn)以入堆的元素的最小堆進(jìn)行排序，并且內(nèi)部實現(xiàn)了siftUp/shiftDown/replace/Heapify操作
import java.util.Comparator;
/**設(shè)計一個最小堆，默認(rèn)是最小堆，但是支持自定義優(yōu)先隊列的優(yōu)先級
* 底層是以數(shù)組形式儲存的，索引從0開始*/
public class MinHeap<E extends Comparable<E>> {
private Array<E> data;
/**接收定義優(yōu)先級方法，默認(rèn)使用最小堆進(jìn)行堆排序
* priority下面的compare接受兩個參數(shù)compare(E a, E b)
* 統(tǒng)一規(guī)定，返回的結(jié)果<=0,a的優(yōu)先級高，反之b的優(yōu)先級高*/
private Comparator<E> priority;
public MinHeap(int capacity) {
this.data = new Array<>(capacity);
this.priority = null;
}
public MinHeap() {
this.data = new Array<>();
this.priority = null;
}
/**設(shè)計一個支持自定義優(yōu)先級的構(gòu)造函數(shù)
* 需要用戶傳遞一個實現(xiàn)了Comparator接口的類，并且返回int類型*/
public MinHeap(Comparator<E> priority) {
this.data = new Array<>();
this.priority = priority;
}
/**返回堆中的元素個數(shù)*/
public int size() {
return data.getSize();
}
/**判斷堆是否為空*/
public boolean isEmpty() {
return data.isEmpty();
}
/**找到完全二叉樹相應(yīng)節(jié)點的父節(jié)點*/
private int parent(int index) {
if(index == 0)
throw new IllegalArgumentException("Index '0' doesn't has a parent!");
return (index - 1) / 2;
}
/**找到一個索引的左子節(jié)點*/
private int leftChild(int index) {
return index * 2 + 1;
}
/**找到一個索引的右子節(jié)點*/
private int rightChild(int index) {
return index * 2 + 2;
}
public void add(E e) {
data.addLast(e);
siftUp(data.getSize() - 1);
}
/**sift up,將節(jié)點添加到完全二叉樹的末尾，
* 反復(fù)與父節(jié)點比較，按照優(yōu)先級進(jìn)行交換，
* 直到與滿足最小堆*/
private void siftUp(int k) {
/**實現(xiàn)默認(rèn)情況下的最小堆*/
if(this.priority == null) {
while (k > 0 && data.get(k).compareTo(data.get(parent(k))) < 0) {
data.swap(k, parent(k));
k = parent(k);
}
} else {
/**規(guī)定接收定義優(yōu)先級方法，默認(rèn)使用最小堆進(jìn)行堆排序
* priority下面的compare接受兩個參數(shù)compare(E a, E b)
* 規(guī)定，返回的結(jié)果<=0,a的優(yōu)先級高，反之b的優(yōu)先級高*/
while (k > 0 && priority.compare(data.get(k), data.get(parent(k))) < 0) {
data.swap(k, parent(k));
k = parent(k);
}
}
}
/** shiftDown 操作
* 對于傳進(jìn)來的索引，根據(jù)這個索引與其節(jié)點最小的子節(jié)點
* 進(jìn)行交換，一直交換到滿足最小堆*/
private void siftDown(int k) {
while (leftChild(k) < data.getSize()) {
int j = leftChild(k);
if(j + 1 < data.getSize()) {
/**默認(rèn)最小堆的情況*/
if(this.priority == null){
if(data.get(j + 1).compareTo(data.get(j)) < 0)
j ++;
} else {
/**規(guī)定接收定義優(yōu)先級方法，默認(rèn)使用最小堆進(jìn)行堆排序
* priority下面的compare接受兩個參數(shù)compare(E a, E b)
* 規(guī)定，返回的結(jié)果<=0,a的優(yōu)先級高，反之b的優(yōu)先級高*/
if(this.priority.compare(data.get(j + 1), data.get(j)) < 0)
j ++;
}
}
/**將父節(jié)點與最大子節(jié)點比較*/
if(this.priority == null) {
if(data.get(j).compareTo(data.get(k)) < 0)
data.swap(j, k);
} else {
if(this.priority.compare(data.get(j), data.get(k)) < 0)
data.swap(j, k);
}
k = j;
}
}
/**查看堆中的最大元素*/
public E peek() {
if(data.getSize() == 0)
throw new IllegalArgumentException("The minHeap is empty!");
return data.get(0);
}
/**取出堆中最大的元素*/
public E extrackTop() {
E res = this.peek();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return res;
}
/**取出堆中最大的元素，并且替換成元素e*/
public E replace(E e) {
E ret = this.peek();
data.set(0, e);
this.siftDown(0);
return ret;
}
/**Heapify操作,使用構(gòu)造函數(shù)實現(xiàn)*/
public MinHeap(E[] arr) {
data = new Array<>();
for(int i = parent(arr.length - 1); i >= 0; i --) {
siftDown(i);
}
}
}
Queue.java
Queue是普通隊列的一個接口
public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
PriorityQueue.java
PriorityQueue是基于MinHeap實現(xiàn)的Queue接口的一個優(yōu)先隊列，默認(rèn)的構(gòu)造函數(shù)創(chuàng)建默認(rèn)最小堆，帶有參數(shù)的構(gòu)造函數(shù)創(chuàng)建帶有比較器的自定義堆。強烈建議傳入一個lamda表達(dá)式。
import java.util.Comparator;
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
private MinHeap<E> minHeap;
public PriorityQueue() {
this.minHeap = new MinHeap<>();
}
/**傳入一個自定義優(yōu)先級，構(gòu)造函數(shù)*/
public PriorityQueue(Comparator<E> priority) {
this.minHeap = new MinHeap<>(priority);
}
@Override
public int getSize() {
return this.minHeap.size();
}
@Override
public boolean isEmpty() {
return this.minHeap.size() == 0;
}
@Override
public E getFront() {
return this.minHeap.peek();
}
@Override
public void enqueue(E e) {
this.minHeap.add(e);
}
@Override
public E dequeue() {
return minHeap.extrackTop();
}
public void replace(E e) {
minHeap.replace(e);
}
}
Main.java
主類進(jìn)行測試，測試用例是：有一個容量為1000000的裝int類型的數(shù)組，里面有很多重復(fù)的元素，而且是亂序，現(xiàn)在要求快速找出頻率最高的前10個元素并打印出來。
很low的思路：我可以先把這1000000排個序，啥冒泡排序啊，選擇排序啊，并歸排序啊三路塊排啊什么什么的，排序后的數(shù)組標(biāo)記為arr1，然后再建立一個裝小數(shù)組arrL(長度為2)的大數(shù)組allB(長度為1000000)，arrL第一個元素用于儲存元素，arrL第二個儲存統(tǒng)計的頻率，遍歷arr1,將相關(guān)數(shù)據(jù)儲存到arrL,再將arrL裝到allB，然后再根據(jù)arrL[1]進(jìn)行從大到小排序，最后取前10個。對應(yīng)的這種系統(tǒng)開銷是非常可觀的，對應(yīng)的時間復(fù)雜度大概為O(n^2)級別的。數(shù)據(jù)量越大，復(fù)雜度結(jié)果越可怕。。。
牛逼思路：遍歷這個數(shù)組A，利用標(biāo)準(zhǔn)庫中的TreeMap統(tǒng)計各個數(shù)組出現(xiàn)的頻率，利用優(yōu)先隊列，限制只儲存10個元素，根據(jù)對應(yīng)的頻率大小確定入隊的優(yōu)先級，儲存相關(guān)頻率對應(yīng)的數(shù)字，采用最小堆(注意，優(yōu)先隊列中儲蓄的是數(shù)字，儲存的數(shù)字本身大小不參與優(yōu)先級的排序，參與排序的是數(shù)字對應(yīng)map中的頻率，而且是最小堆，堆頂是10個中頻率最小的),遍歷TreeMap,將數(shù)字存入優(yōu)先隊列，當(dāng)優(yōu)先隊列中存入了10個元素后，之后遍歷的數(shù)字與優(yōu)先隊列頂進(jìn)行優(yōu)先級比較(比較對應(yīng)的頻率)，如果遍歷的數(shù)字頻率大于頂?shù)念l率，就進(jìn)行replace操作，就是將這個數(shù)與頂?shù)臄?shù)進(jìn)行交換，然后進(jìn)行SiftDown
請參照上面的SiftDown操作。遍歷完了優(yōu)先隊列中儲存的就為頻率最大的前10個數(shù)。對應(yīng)的時間復(fù)雜度大概為O(nlogm) ，n個數(shù)，取前m個數(shù)
import java.util.Comparator;
import java.util.Random;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
int[] res0 = {1,1,1,1,1,1,3,3,5,5,5,5,5,5,7,7,8,8,8,8,8,9,0,2,3,4,5,6,7,8,9,0,1};
int m0 = 3;
printArray(findPro(res0, m0));
System.out.println("===================");
/**統(tǒng)計一個容量為n的數(shù)組中頻次最高的前m個元素
* 時間復(fù)雜度估計為O(nlogm), (如果不對請批評指教，我對于時間復(fù)雜度的計算不是特別熟)
* 隨機生成int類型的數(shù)字*/
int n = 1000000;
int m = 10;
int[] res = new int[n];
Random random = new Random();
for(int i = 0; i < n; i ++) {
res[i] = random.nextInt(Integer.MAX_VALUE);
}
printArray(findPro(res, m));
}
/**打印結(jié)果*/
public static void printArray(int[] array) {
for(int num : array) {
System.out.print(num + " ");
}
System.out.println();
}
/**通過標(biāo)準(zhǔn)庫的treeMap統(tǒng)計詞頻然后利用自己實現(xiàn)的基于動態(tài)
* 數(shù)組->最小堆->優(yōu)先隊列統(tǒng)計，使用自定義實現(xiàn)Comparator確定優(yōu)先級，
* 找出前頻次最高的元素*/
public static int[] findPro(int[] array, int k) {
// 利用map統(tǒng)計字頻
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int arr : array) {
if(!map.containsKey(arr))
map.put(arr, 1);
else
map.put(arr, map.get(arr) + 1);
}
/**通過優(yōu)先隊列遍歷并儲蓄m個最高的詞頻， 拋出的接口表示，
* 返回值<=0，則第一個參數(shù)的優(yōu)先級高。
* 匿名函數(shù) 或者 lamda表達(dá)式能夠訪問當(dāng)前的作用域*/
/** 匿名函數(shù)的寫法
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return map.get(o1) - map.get(o2);
}
});*/
/** (高級玩兒法)lamda表達(dá)式*/
PriorityQueue<Integer> pq = new PriorityQueue<>(
(Integer o1, Integer o2) -> map.get(o1) - map.get(o2)
);
for(int key : map.keySet()) {
if(pq.getSize() < k) {
pq.enqueue(key);
} else {
if(map.get(key).compareTo(map.get(pq.getFront())) > 0){
pq.replace(key);
}
}
}
int[] ret = new int[k];
for(int i = 0; i < k; i ++) {
ret[i] = pq.dequeue();
}
return ret;
}
}
謝謝閱讀，如有錯誤的地方請批評指出，讓大家一起進(jìn)步！
