Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級(jí)隊(duì)列(堆)圖文詳解
一、堆的概念
堆的定義：n個(gè)元素的序列{k1 , k2 , … , kn}稱之為堆，當(dāng)且僅當(dāng)滿足以下條件時(shí)：
（1）ki >= k2i 且 ki >= k(2i+1) ——大根堆
（2） ki <= k2i 且 ki <= k(2i+1) ——小根堆
簡(jiǎn)單來(lái)說(shuō)：
堆是具有以下性質(zhì)的完全二叉樹(shù)：
（1）每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值，稱為大根堆（如左下圖）；
或者：
（1）每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值，稱為小根堆（如右下圖）。
我們使用數(shù)組保存二叉樹(shù)結(jié)構(gòu)，即是將二叉樹(shù)用層序遍歷方式放入數(shù)組中，如上圖。
堆的元素下標(biāo)存在以下關(guān)系：
1.假如已知雙親（parent）的下標(biāo)，則
左孩子（left）下標(biāo) = 2parent + 1；
右孩子（right）下標(biāo) = 2parent +2；
2.已知孩子（child）（不區(qū)分左右）下標(biāo)，則：
雙親（parent）下標(biāo) = （child - 1）/ 2 ;
小結(jié)：
- 堆邏輯上是一棵完全二叉樹(shù)；
- 堆物理上保存在數(shù)組中；
- 滿足任意結(jié)點(diǎn)的值都大于其子樹(shù)中結(jié)點(diǎn)的值，叫做大堆，或者大根堆，或者最大堆；反之，則是小堆，或者小根堆，或者最小堆；
- 堆的基本作用是，快速找集合中的最值。
二、向下調(diào)整
1.建初堆
設(shè)有一個(gè)無(wú)序序列 {2,5,7,8,4,6,3,0,9,1 }，下面通過(guò)圖解來(lái)建初始堆。
這里有一個(gè)前提：這棵二叉樹(shù)的左右子樹(shù)都必須是一個(gè)堆，才能進(jìn)行調(diào)整。
下面是用到的數(shù)據(jù)的一些說(shuō)明：
- array 代表存儲(chǔ)堆的數(shù)組
- size 代表數(shù)組中被視為堆數(shù)據(jù)的個(gè)數(shù)
- index 代表要調(diào)整位置的下標(biāo)
- left 代表 index 左孩子下標(biāo)
- right 代表 index 右孩子下標(biāo)
- min 代表 index 的最小值孩子的下標(biāo)
過(guò)程文字描述如下：
1.index 如果已經(jīng)是葉子結(jié)點(diǎn)，則整個(gè)調(diào)整過(guò)程結(jié)束：
（1）判斷 index 位置有沒(méi)有孩子；
（2） 因?yàn)槎咽峭耆鏄?shù)，沒(méi)有左孩子就一定沒(méi)有右孩子，所以判斷是否有左孩子；
（3） 因?yàn)槎训拇鎯?chǔ)結(jié)構(gòu)是數(shù)組，所以判斷是否有左孩子即判斷左孩子下標(biāo)是否越界，即 left >= size 越界。
2.確定 left 或 right，誰(shuí)是 index 的最小孩子 min：
（1） 如果右孩子不存在，則 min = left；
（2）否則，比較 array[left] 和 array[right] 值得大小，選擇小的為 min；
（3）比較 array[index] 的值 和 array[min] 的值，如果 array[index] <= array[min]，則滿足堆的性質(zhì)，調(diào)整結(jié)束。
3.否則，交換 array[index] 和 array[min] 的值；
4.然后因?yàn)?min 位置的堆的性質(zhì)可能被破壞，所以把 min 視作 index，向下重復(fù)以上過(guò)程。
通過(guò)上面的操作描述，我們寫(xiě)出以下代碼：
public static void shiftDown(int[] array, int size, int index){
int left = 2*index +1;
while(left < size){
int min = left;
int right = 2*index +2;
if(right<size){
if(array[right] < array[left]){
min = right;
}
}
if(array[index] <= array[min]){
break;
}
int tmp = array[index];
array[index] = array[min];
array[min] = tmp;
index = min;
left = 2*index +1;
}
}
時(shí)間復(fù)雜度為 O(log(n))。
2.建堆
下面我們給出一個(gè)數(shù)組，這個(gè)數(shù)組邏輯上可以看做一顆完全二叉樹(shù)，但是還不是一個(gè)堆，現(xiàn)在我們通過(guò)算法，把它構(gòu)建成一個(gè)堆。根節(jié)點(diǎn)左右子樹(shù)不是堆，我們?cè)趺凑{(diào)整呢？這里我們從倒數(shù)的第一個(gè)非葉子節(jié)點(diǎn)的子樹(shù)開(kāi)始調(diào)整，一直調(diào)整到根節(jié)點(diǎn)的樹(shù)，就可以調(diào)整成堆。
時(shí)間復(fù)雜度分析：
粗略估算，可以認(rèn)為是在循環(huán)中執(zhí)行向下調(diào)整，為 O(n * log(n))，（了解）實(shí)際上是 O(n)。
//建堆代碼
public void createHeap(int[] array) {
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
//根據(jù)代碼 顯示的時(shí)間復(fù)雜度 看起來(lái) 應(yīng)該是O(n*logn) 但是 實(shí)際上是O(n)
for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
//調(diào)整
shiftDown(parent,usedSize);
}
}
三、優(yōu)先級(jí)隊(duì)列
1.什么是優(yōu)先隊(duì)列？
根據(jù)百科解釋：
普通的隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，元素在隊(duì)列尾追加，而從隊(duì)列頭刪除。在優(yōu)先隊(duì)列中，元素被賦予優(yōu)先級(jí)。當(dāng)訪問(wèn)元素時(shí)，具有最高優(yōu)先級(jí)的元素最先刪除。優(yōu)先隊(duì)列具有最高級(jí)先出（first in, largest out）的行為特征。通常采用堆數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。
所以我們?cè)谶@里實(shí)現(xiàn)優(yōu)先隊(duì)列的內(nèi)部原理是堆，也就是說(shuō)采用堆來(lái)構(gòu)建。
2.入隊(duì)列
過(guò)程（以大堆為例）：
- 首先按尾插方式放入數(shù)組；
- 比較其和其雙親的值的大小，如果雙親的值大，則滿足堆的性質(zhì)，插入結(jié)束；
- 否則，交換其和雙親位置的值，重新進(jìn)行 2、3 步驟；
- 直到根結(jié)點(diǎn)。
下面圖解：
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
3.出隊(duì)列
為了防止破壞堆的結(jié)構(gòu)，刪除時(shí)并不是直接將堆頂元素刪除，而是用數(shù)組的最后一個(gè)元素替換堆頂元素，然后通過(guò)向 下調(diào)整方式重新調(diào)整成堆。
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
public void offer(int val) {
if(isFull()) {
//擴(kuò)容
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++] = val;
//注意這里傳入的是usedSize-1
shiftUp(usedSize-1);
}
4.返回隊(duì)首元素
直接返回堆頂元素
public int peek() {
if(isEmpty()) {
throw new RuntimeException("優(yōu)先級(jí)隊(duì)列為空！");
}
return elem[0];
}
public boolean isEmpty() {
return usedSize == 0;
}
整體的代碼：
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap() {
this.elem = new int[10];
}
/**
* 向下調(diào)整函數(shù)的實(shí)現(xiàn)
* @param parent 每棵樹(shù)的根節(jié)點(diǎn)
* @param len 每棵樹(shù)的調(diào)整的結(jié)束位置 10
*/
public void shiftDown(int parent,int len) {
int child = 2*parent+1;
//1、最起碼 是有左孩子的，至少有1個(gè)孩子
while (child < len) {
if(child+1 < len && elem[child] < elem[child+1]) {
child++;//保證當(dāng)前左右孩子最大值的下標(biāo)
}
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
public void createHeap(int[] array) {
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
//根據(jù)代碼 顯示的時(shí)間復(fù)雜度 看起來(lái) 應(yīng)該是O(n*logn) 但是 實(shí)際上是O(n)
for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
//調(diào)整
shiftDown(parent,usedSize);
}
}
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
public void offer(int val) {
if(isFull()) {
//擴(kuò)容
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++] = val;
//注意這里傳入的是usedSize-1
shiftUp(usedSize-1);
}
public boolean isFull() {
return usedSize == elem.length;
}
public int poll() {
if(isEmpty()) {
throw new RuntimeException("優(yōu)先級(jí)隊(duì)列為空！");
}
int tmp = elem[0];
elem[0] = elem[usedSize-1];
elem[usedSize-1] = tmp;
usedSize--;
shiftDown(0,usedSize);
return tmp;
}
public int peek() {
if(isEmpty()) {
throw new RuntimeException("優(yōu)先級(jí)隊(duì)列為空！");
}
return elem[0];
}
public boolean isEmpty() {
return usedSize == 0;
}
public void heapSort() {
int end = this.usedSize-1;
while (end > 0) {
int tmp = elem[0];
elem[0] = elem[end];
elem[end] = tmp;
shiftDown(0,end);
end--;
}
}
}
5.堆的其他TopK問(wèn)題
什么是TopK問(wèn)題？
從arr[1, n]這n個(gè)數(shù)中，找出最大的k個(gè)數(shù)，這就是經(jīng)典的TopK問(wèn)題。
解決這類問(wèn)題，我們往往會(huì)有以下幾種思路：
- 對(duì)整體進(jìn)行排序，輸出前10個(gè)最大的元素。
- 用上面剛剛講的堆。
- 也是用堆，不過(guò)這比第二個(gè)思路更巧妙。
我們直接講思路三：
- 先用前k個(gè)元素生成一個(gè)小頂堆，這個(gè)小頂堆用于存儲(chǔ)，當(dāng)前最大的k個(gè)元素。
- 接著，從第k+1個(gè)元素開(kāi)始掃描，和堆頂（堆中最小的元素）比較，如果被掃描的元素大于堆頂，則替換堆頂?shù)脑?，并調(diào)整堆，以保證堆內(nèi)的k個(gè)元素，總是當(dāng)前最大的k個(gè)元素。
- 直到，掃描完所有n-k個(gè)元素，最終堆中的k個(gè)元素，就是所要求的TopK。
以這個(gè)數(shù)組{12，15，21，41，30}為例，找到前3個(gè)最大的元素。
那如果是將一組進(jìn)行從小到大排序，我們?cè)摬捎么蟾堰€是小根堆？
答案是：大根堆！
步驟如下：
- 將這組數(shù)據(jù)調(diào)整為大根堆調(diào)整為大根堆；
- 0下標(biāo)和最后1個(gè)未排序的元素進(jìn)行交換即可；
- 重復(fù)1、2，直到結(jié)束。
總結(jié)：
如果求前K個(gè)最大的元素，要建一個(gè)小根堆。如果求前K個(gè)最小的元素，要建一個(gè)大根堆。第K大的元素。建一個(gè)小堆，堆頂元素就是第K大的元素。第K小的元素。建一個(gè)大堆，堆頂元素就是第K小的元素。
public void heapSort() {
int end = this.usedSize-1;
while (end > 0) {
int tmp = elem[0];
elem[0] = elem[end];
elem[end] = tmp;
shiftDown(0,end);
end--;
}
}
public void shiftDown(int parent,int len) {
int child = 2*parent+1;
//1、最起碼 是有左孩子的，至少有1個(gè)孩子
while (child < len) {
if(child+1 < len && elem[child] < elem[child+1]) {
child++;//保證當(dāng)前左右孩子最大值的下標(biāo)
}
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
總結(jié)
來(lái)來(lái)回回，這篇文章寫(xiě)了2-3天了，以前寫(xiě)文章總是蜻蜓點(diǎn)水，不到水深，導(dǎo)致自己對(duì)很多的知識(shí)也沒(méi)有多深理解，僅僅是為了寫(xiě)文章而寫(xiě)文章。希望有改變，從這篇文章開(kāi)始吧！
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級(jí)隊(duì)列(堆)的文章就介紹到這了,更多相關(guān)Java優(yōu)先級(jí)隊(duì)列(堆)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之二叉堆
- Java深入了解數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級(jí)隊(duì)列(堆)
- 深入了解Java數(shù)據(jù)結(jié)構(gòu)和算法之堆
- Java數(shù)據(jù)結(jié)構(gòu)中堆的向下和向上調(diào)整解析
- Java 數(shù)據(jù)結(jié)構(gòu)之堆的概念與應(yīng)用
- java數(shù)據(jù)結(jié)構(gòu)-堆實(shí)現(xiàn)優(yōu)先隊(duì)列
- java 數(shù)據(jù)結(jié)構(gòu)之堆排序（HeapSort）詳解及實(shí)例
- Java?超詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)中的堆的應(yīng)用
相關(guān)文章
這篇文章主要介紹了Java 中 Map 集合的三種遍歷方式,每種遍歷方式結(jié)合示例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-12-12
Windows10系統(tǒng)下JDK1.8的下載安裝及環(huán)境變量配置的教程
這篇文章主要介紹了Windows10系統(tǒng)下JDK1.8的下載安裝及環(huán)境變量配置的教程,本文圖文并茂給大家介紹的非常詳細(xì)，對(duì)大家的工作或?qū)W習(xí)具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-03-03
Java之通過(guò)OutputStream寫(xiě)入文件與文件復(fù)制問(wèn)題
這篇文章主要介紹了Java之通過(guò)OutputStream寫(xiě)入文件與文件復(fù)制問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-04-04
Spring集成webSocket頁(yè)面訪問(wèn)404問(wèn)題的解決方法
這篇文章主要介紹了Spring集成webSocket頁(yè)面訪問(wèn)404問(wèn)題的解決方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-12-12
java動(dòng)態(tài)線程池的簡(jiǎn)單實(shí)現(xiàn)思路
本文主要介紹了java?動(dòng)態(tài)線程池的簡(jiǎn)單實(shí)現(xiàn)思路，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06
SpringMVC是一種基于Java，實(shí)現(xiàn)了Web MVC設(shè)計(jì)模式，請(qǐng)求驅(qū)動(dòng)類型的輕量級(jí)Web框架，即使用了MVC架構(gòu)模式的思想，將Web層進(jìn)行職責(zé)解耦，這篇文章主要介紹了SpringMvc定制化原理2022-10-10
微服務(wù)之間如何通過(guò)feign調(diào)用接口上傳文件
這篇文章主要介紹了微服務(wù)之間如何通過(guò)feign調(diào)用接口上傳文件的操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-06-06
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)登錄注冊(cè)界面，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
java快速解析路徑中的參數(shù)(&與=拼接的參數(shù))
這篇文章主要介紹了java快速解析路徑中的參數(shù)(&與=拼接的參數(shù)),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2024-02-02
詳解Elasticsearch如何實(shí)現(xiàn)簡(jiǎn)單的腳本排序
Elasticsearch?是位于?Elastic?Stack?核心的分布式搜索和分析引擎，可以為所有類型的數(shù)據(jù)提供近乎實(shí)時(shí)的搜索和分析。本文主要介紹了Elasticsearch如何實(shí)現(xiàn)簡(jiǎn)單的腳本排序，感興趣的可以了解一下2023-01-01