目錄
1. 優(yōu)先級隊(duì)列（Priority Queue）
2.堆的概念
3.堆的存儲方式
4.堆的創(chuàng)建
5.用堆模擬實(shí)現(xiàn)優(yōu)先級隊(duì)列
?6.PriorityQueue常用接口介紹
6.1?PriorityQueue的特點(diǎn)
6.2?PriorityQueue幾種常見的構(gòu)造方式
7.top-k問題
8.堆排序
本篇主要內(nèi)容總結(jié)
（1）優(yōu)先級隊(duì)列底層是堆來實(shí)現(xiàn)的
（2）堆的本質(zhì)是完全二叉樹? ，堆有大根堆和小根堆
（3）大根堆：根節(jié)點(diǎn)最大的堆； 小根堆：根節(jié)點(diǎn)最小的堆
（4）堆的創(chuàng)建實(shí)現(xiàn)：大根堆為例
大根堆創(chuàng)建：孩子結(jié)點(diǎn)和根節(jié)點(diǎn)比較交換，核心思想：向下調(diào)整? ?時間復(fù)雜度O(n)
堆的插入：插入到最后一個位置，和根結(jié)點(diǎn)交換，核心思想：向上調(diào)整
堆的刪除：只能刪除堆頂，然后重新向下調(diào)整組成新的大根堆
插入和刪除時間復(fù)雜度O（log n）
（4）priorityQueue建堆是小根堆，如果要建立大根堆就要寫比較器
（5）priorityQueue添加元素，要寫明比較的類型才能添加
（6）top-K問題：前K個最大的元素建小根堆；前K個最小的元素建大根堆
第K個最大元素建小根堆 拿棧頂；? ? 第K個最小元素建大根堆 拿棧頂
（7）堆排序：升序：大根堆? ? 降序：小根堆
核心思想：堆元素的刪除
在說堆的概念之前，先說一下堆的常用方法，從這個方向來寫這篇文章
堆的常用方法有
（1）用來構(gòu)建優(yōu)先級隊(duì)列
（2）支持堆排序（大堆或小堆）
（3）top-k問題
1. 優(yōu)先級隊(duì)列（Priority Queue）
優(yōu)先級隊(duì)列?：是不同于先進(jìn)先出隊(duì)列的另一種隊(duì)列。每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素。
優(yōu)先級隊(duì)列相對于普通隊(duì)列應(yīng)該提供兩個最基本的操作，
（1）返回最高優(yōu)先級對象（2）添加新的對象
在JDk1.8中的優(yōu)先級隊(duì)列底層使用了堆
2.堆的概念
簡單的說 ，堆這種數(shù)據(jù)結(jié)構(gòu)本質(zhì)上就是一個完全二叉樹
并且堆中某個結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值
小堆：根節(jié)點(diǎn)最小的堆，滿足Ki <= K2i+1 且 Ki <= K2i+2?
大堆：根節(jié)點(diǎn)最大的堆,? ?滿足Ki >= K2i+1 且 Ki >= K2i+2?
3.堆的存儲方式
堆是一顆完全二叉樹，所以按照層序來看，可以采用順序數(shù)組的存儲方式
但是非完全二叉樹就不適用于順序存儲了，這是因?yàn)榉峭耆鏄淙绻锌战Y(jié)點(diǎn)，那順序存儲也要存儲這個空節(jié)點(diǎn)，這就造成空間上的浪費(fèi)
i表示孩子結(jié)點(diǎn)，父親結(jié)點(diǎn)（i-1）/ 2
i表示根節(jié)點(diǎn) ，左孩子 2 * i + 1? ? 右孩子? ?2 * i + 2
4.堆的創(chuàng)建
5.用堆模擬實(shí)現(xiàn)優(yōu)先級隊(duì)列
按照大根堆來創(chuàng)建
先寫一個數(shù)組，按順序存儲的方式
public int[] elem;
public int userSize;//當(dāng)前堆中有效的元素?cái)?shù)據(jù)個數(shù)
public MyHeap() {
this.elem = new int[10];
this.userSize = 0;
}
public void initArray(int[] array) {
elem = Arrays.copyOf(array,array.length);
userSize = elem.length;
}(1) 創(chuàng)建堆
先寫一個向下調(diào)整的方法
/**
* @param parent: 每顆子樹的根節(jié)點(diǎn)下標(biāo)
* @param len:每顆子樹的結(jié)束位置
* @description 向下調(diào)整
*/
private void shiftDown(int parent,int len) {
int child = 2*parent+1;//左孩子
//必須要有左孩子
while(child < len) {
//如果一定有右孩子。那就判斷 左孩子和右孩子大小，誰大保存誰
if(child + 1 < userSize && elem[child] < elem[child+1]) {
child++;
}
//交換 比較孩子和根大小交換 然后根節(jié)點(diǎn)往下走繼續(xù)必須
if (elem[child] > elem[parent]) {
swap(elem,child,parent);
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}再寫一個交換根和孩子的方法
//交換 比較孩子和根大小交換
private void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}然后通過循環(huán)每個結(jié)點(diǎn)，向下調(diào)整，然后創(chuàng)建好這棵樹
/**
*建堆：大根堆
*時間復(fù)雜度O(n)
*/
public void createHeap() {
for (int parent = (userSize-1-1)/2; parent >= 0 ; parent--) {
shiftDown(parent,userSize);
}
}分析一下建堆的時間復(fù)雜度O(n)
?（2）堆的插入
先寫一個方法來判斷空間滿不滿
public boolean isFull() {
return userSize == elem.length;
}再寫一個向上調(diào)整
//向上調(diào)整
private void shiftUp(int child) {
int parent = (child - 1) / 2;
while(child > 0) {
if(elem[child] > elem[parent]) {
swap(elem,child,parent);
child = parent;
parent = (child - 1) / 2;
}else {
break;
}
}
}?最后再寫堆的插入，如果空間滿了就擴(kuò)容，然后再向上調(diào)整，變成新的大根堆
//堆的插入
public void offer(int x) {
if (isFull()) {
elem = Arrays.copyOf(elem,2*elem.length);
}
this.elem[userSize] = x;
userSize++;
shiftUp(userSize-1);
}?（3）堆的刪除（優(yōu)先級隊(duì)列刪除，只能刪除堆頂?shù)脑兀?/strong>
再刪除前，先要看堆是不是空的
public boolean isEmpty() {
return userSize == 0;
}然后再刪除堆頂元素
//堆的刪除 只能刪除堆頂元素
public int poll() {
if (isEmpty()) {
return -1;
}
int old = elem[0];
//1.交換
swap(elem,0,userSize-1);
//2.有效元素個數(shù)-1
userSize--;
//3.棧頂元素向下調(diào)整
shiftDown(0,userSize);
return old;
}看幾個選擇題把?
1.已知小根堆為8,15,10,21,34,16,12，刪除關(guān)鍵字8之后需重建堆，在此過程中，關(guān)鍵字之間的比較次數(shù)是? ?? (C)A: 1 B: 2 C: 3 D: 4
2.最小堆[0,3,2,5,7,4,6,8],在刪除堆頂元素0之后，其結(jié)果是? ??()
A: [3 ， 2 ， 5 ， 7 ， 4 ， 6 ， 8] B: [2 ， 3 ， 5 ， 7 ， 4 ， 6 ， 8]C: [2 ， 3 ， 4 ， 5 ， 7 ， 8 ， 6] D: [2 ， 3 ， 4 ， 5 ， 6 ， 7 ， 8]
?6.PriorityQueue常用接口介紹
6.1?PriorityQueue的特點(diǎn)
（1）首先最重要的先明白priorityQueue建堆是小根堆
public static void main(String[] args) {
//默認(rèn)是小根堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(45);
priorityQueue.offer(12);
priorityQueue.offer(55);
priorityQueue.offer(66);
System.out.println(priorityQueue.peek());
}
可以看到這里打印的是12所以是priorityQueue是小根堆
如果要建堆為大根堆，那就要寫比較器Comparator了?
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
}（2） 在priorityQueue使用offer添加元素時，一定要明確比較的規(guī)則，然后再添加
如果是直接這樣比較的話，offer不知道以什么規(guī)則比較然后添加，就會報(bào)錯。?
public static void main(String[] args) {
PriorityQueue<Fruit> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(new Fruit() );
priorityQueue.offer(new Fruit() );
}所以這里必須告訴offer以什么方式比較添加，
比如說這里實(shí)現(xiàn)comparable接口
class Fruit implements Comparable<Fruit>{
public int age;
//必須告訴priorityQueue.offer 以什么方式比較添加元素
@Override
public int compareTo(Fruit o) {
return this.age - o.age;
}
}（3）不能插入null對象，否則會拋出NullPointerException異常
（4）可以插入任意多個元素，會自動擴(kuò)容，沒有容量限制
?
?（5）插入和刪除元素的時間復(fù)雜度為O(log n),建棧的時間復(fù)雜度O（n）
6.2?PriorityQueue幾種常見的構(gòu)造方式
（1）PriorityQueue()? ?初始默認(rèn)容量為11
（2）PriorityQueue(int initialCapacity)
（3）PriorityQueue(Collection<? extends E> c)
?
（4）PriorityQueue(int initialCapacity, Collection<? super E> comparator
7.top-k問題
適用情況，在數(shù)據(jù)量比較大時，求數(shù)據(jù)集合中前K個最大的元素或者最小的元素
比如說求很多個元素的前k個最大的元素?
思路1：
（1）將這些元素，全部放進(jìn)大根堆中，堆頂?shù)脑鼐褪亲畲蟮闹?/strong>
（2）然后出k次，就能得到前k個最大的值，并且每出一次都會進(jìn)行向下調(diào)整，變成新的大根堆
public static void topK1(int[] array, int k) {
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for (int i = 0; i < array.length; i++) {
maxPQ.offer(array[i]);
}
for (int i = 0; i < k; i++) {
int val = maxPQ.poll();
System.out.println(val);
}
System.out.println();
}
public static void main(String[] args) {
int[] array = {16,15,22,155,89,12,45};
topK1(array,3);
}?
?缺點(diǎn)：數(shù)字有多少，這個堆就有多大，時間復(fù)雜度是O(n*log n)
?思路2：
（1）求前K個最大的元素，建立大小為K的小根堆
（2）然后用剩下的集合里面的元素輪流和堆頂元素比較，如果剩下集合里面的元素比堆頂?shù)脑卮?，那就替換掉堆頂?shù)脑?/strong>
（3）然后向下調(diào)整，變成新的小根堆，此時這個堆中的元素就是前K個最大元素
差不多和前面一樣的方法，不同的是（1）求前K個最小的元素，要建立大根堆（2）比較的時候誰小，就把小的放在堆頂
?力扣鏈接：? ?面試題 17.14. 最小K個數(shù) - 力扣（LeetCode）
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] ret = new int[k];
if(k == 0) return ret;
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(k,new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for (int i = 0; i < arr.length; i++) {
if(maxPQ.size() < k) {
maxPQ.offer(arr[i]);
}else {
//獲取到堆頂元素
int top = maxPQ.peek();
//找前k個最小的
if(arr[i] < top) {
maxPQ.poll();
maxPQ.offer(arr[i]);
}
}
}
for (int i = 0; i < k; i++) {
ret[i] = maxPQ.poll();
}
return ret;
}
}（1）前面求前K個最大的元素時，建立的小根堆，按照規(guī)則，到最后棧中全部都是前K個最大的元素，然后棧頂就是所要求得的第K大的元素
（2）前面求前K個最小的元素時，建立的大根堆，按照規(guī)則，到最后棧中全部都是前K個最小的元素，然后棧頂就是所要求得的第K小的元素
8.堆排序
?如果是將堆排成一個升序的，那就建立大根堆，操作如下
public void heapSort() {
int end = userSize -1;
while(end > 0) {
swap(elem,0,end);
shiftDown(0,end);
end--;
}
}
如果是將堆排成一個降序的，那就建立小根堆，操作和上面類似文章來源：http://www.zghlxwxcb.cn/news/detail-427760.html
一組記錄排序碼為(5 11 7 2 3 17),則利用堆排序方法建立的初始堆為??(C)A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5)D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5)
文章來源地址http://www.zghlxwxcb.cn/news/detail-427760.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級隊(duì)列【堆】（Heap）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
