什么是優(yōu)先隊列菩混？

我們在前幾篇文章中學習過了“隊列”這種數(shù)據(jù)結構。那么優(yōu)先隊列和普通隊列有什么區(qū)別的呢扁藕？普通隊列的特點是“先進先出”沮峡，優(yōu)先隊列則不一樣，它的入隊順序沒有變化亿柑，但是出隊的順序是根據(jù)優(yōu)先級的高低來決定的邢疙。優(yōu)先級高的優(yōu)先出隊。

本文首發(fā)于心安-XinAnzzZ 的個人博客，轉載請注明出處~

舉個生活中的小栗子秘症。病人去醫(yī)院看病照卦，正常情況下都是需要取號排隊，這是普通隊列乡摹。但是特殊情況下役耕，有一個情況緊急的病人突然來了，這個病人就擁有優(yōu)先權聪廉，他就優(yōu)先出隊瞬痘，這就是優(yōu)先隊列。

再比如說板熊，玩過LOL的同學都知道框全，游戲里面防御塔都有一個自動攻擊功能，小兵排著隊進入防御塔的攻擊范圍干签，這時候大炮車的優(yōu)先級更高（因為系統(tǒng)判定大炮車對于防御塔的威脅更大）津辩，所以防御塔會優(yōu)先攻擊大炮車。而當大炮車陣亡容劳，剩下的全部都是普通小兵喘沿，這時候離得近的優(yōu)先級越高，防御塔優(yōu)先攻擊距離更近的小兵竭贩。

希望通過這兩個小栗子蚜印，各位同學能夠明白優(yōu)先隊列是怎么一回事，從而更好的理解后面的內容留量。

• 各種不同的底層數(shù)據(jù)結構所對應的時間復雜度

我們假設有一個優(yōu)先隊列窄赋，它的優(yōu)先級是元素越大優(yōu)先級越高，也就是每次出隊的是隊列中值最大的元素楼熄。那么如果我們使用普通的線性結構（比如數(shù)組和鏈表）來實現(xiàn)忆绰，那么入隊的操作，直接插入即可孝赫，時間復雜度是O(1)较木，出隊我們需要進行遍歷整個隊列找到最大元素，然后出隊，時間復雜度是O(n)驹吮。而如果使用順序的線性結構（順序線性結構指的是數(shù)據(jù)已經(jīng)有了順序逢并，比如二分搜索樹，中序遍歷就是有序的）弦撩，入隊的時候需要進行遍歷整個隊列來找到合適的位置來插入這個元素，時間復雜度是O(n)，出隊的時候由于有序双戳，所以直接取出，時間復雜度是O(1)糜芳。我們知道飒货，O(n)的時間復雜度是效率比較低的魄衅，所以我們接下來介紹一種入隊和出隊都是O(logn)時間復雜度的數(shù)據(jù)結構--堆。

堆

• 完全二叉樹

有一定基礎的同學對這個概念應該不會陌生塘辅，這里還是貼上完全二叉樹的百度百科晃虫。概念性的東西我不解釋太多，大家自己去體會和理解扣墩。這里我只說自己的理解哲银，也是我認為最簡單的理解。

image

• 二叉堆

二叉堆是特殊的完全二叉樹虏杰。它滿足“堆中任意一個節(jié)點的值都不大于其父親節(jié)點的值”這一特征讥蟆。當然，這個“不大于”是由我們來定義的纺阔，我們也可以定義為“不小于”瘸彤。如果是“不大于”，那么形成的就是“最大堆”笛钝，反之就是“最小堆”质况。下面就是一個最小堆和一個最大堆。注意一個誤區(qū)玻靡，在最大堆當中结榄，堆中任意一個節(jié)點的值都不大于父親節(jié)點的值，是否意味著層次越低的節(jié)點值越大呢囤捻？這是不一定的臼朗。

image

image

• 二叉堆的數(shù)組實現(xiàn)

上面我們說了，二叉堆是一個完全二叉樹，就是一個一個元素從左到右视哑、從上到下依次排列出來的绣否，那也就可以使用數(shù)組的方式來表示二叉堆。用數(shù)組來表示一個二叉堆要解決的問題就是挡毅，我們如何找到一個節(jié)點的左右孩子蒜撮。如果我們使用的是樹的形式來表示的話，我們是可以通過一個“指針”來表示它的左右孩子慷嗜，但是數(shù)組是沒有“指針”的淀弹，應該如何實現(xiàn)呢？仔細觀察一下下圖庆械，我對這個二叉堆從上到下薇溃、從左到右進行了編號，編號就代表了元素在數(shù)組中的索引缭乘，我們可以發(fā)現(xiàn)沐序，節(jié)點編號滿足以下規(guī)律：

parent(i) = (i - 1) / 2 left child(i) = 2 * i + 1 right child(i) = (i + 1) * 2

image

1. 下面我們新建一個工程，創(chuàng)建名為MaxHeap（最大堆）的類在里面加入以下代碼堕绩，這里我們底層依賴ArrayList策幼。

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n49" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> public class MaxHeap<E extends Comparable<E>> {
?
private ArrayList<E> data;
?
/*** 根據(jù)孩子節(jié)點索引獲取父節(jié)點的索引 /
private int getParentIndex(int childIndex) {
if (childIndex == 0) {
throw new IllegalArgumentException("the root node doesn't have parent node !");
}
return (childIndex - 1) / 2;
}
?
/** 根據(jù)父節(jié)點索引獲取左孩子索引 /
private int getLeftChildIndex(int parentIndex) {
if (parentIndex * 2 + 1 > size() - 1) {
throw new IllegalArgumentException("the parent node doesn't have left child node !");
}
return parentIndex * 2 + 1;
}
?
/** 根據(jù)父節(jié)點索引獲取右孩子索引 */
private int getRightChildIndex(int parentIndex) {
if ((parentIndex + 1) * 2 > size() - 1) {
throw new IllegalArgumentException("the parent node doesn't have right child node !");
}
return (parentIndex + 1) * 2;
}
}</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n59" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> public void add(E e) {
data.add(e);
int index = data.size() - 1;
// 如果父節(jié)點的值小于新節(jié)點的值，進行位置互換
while (index > 0 && data.get(getParentIndex(index)).compareTo(e) < 0) {
data.set(index, data.get(getParentIndex(index)));
data.set(getParentIndex(index), e);
index = getParentIndex(index);
}
}</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n66" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> /*** 提取最大值 */
public E extractMax() {
if (data.isEmpty()) {
throw new IllegalArgumentException("The heap is empty !");
}
E result = data.get(0);
E remove = data.remove(size() - 1);
?
if (size() == 0) {
return result;
}
data.set(0, remove);
?
int index = 0;
// 如果說左孩子的索引值小于 size 說明左孩子存在奴紧，當左孩子不存在的時候 循環(huán)終止
while (getLeftChildIndex(index) < size()) {
// 假設左右孩子中左孩子的值較大
int maxIndex = getLeftChildIndex(index);
?
// 如果右孩子存在且有孩子的值大于左孩子特姐，則最大值的索引等于右孩子
if (getRightChildIndex(index) < size()
&& data.get(maxIndex).compareTo(data.get(getRightChildIndex(index))) < 0) {
maxIndex = getRightChildIndex(index);
}
// 如果當前節(jié)點值小于左右孩子節(jié)點中較大的那個值，則進行位置互換黍氮，否則跳出循環(huán)
if (data.get(index).compareTo(data.get(maxIndex)) < 0) {
// 互換位置
E e = data.get(index);
data.set(index, data.get(maxIndex));
data.set(maxIndex, e);
?
index = maxIndex;
} else {
break;
}
}
return result;
}</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n72" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> public interface Queue<E> {
?
/**

• inserts the element into the queue
• @param e the element to add
  /
  void enqueue(E e);
  ?
  /*
• remove the head of this queue
• @return the has been removed element
  /
  E dequeue();
  ?
  /*
• get the head of this queue
• @return the element at front of the queue
  /
  E getFront();
  ?
  /*
• get the queue's size
• @return the queue's size
  /
  int size();
  ?
  /*
• whether is empty or not
• @return {@code true} if the queue is empty
  */
  boolean isEmpty();
  }</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n76" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
?
private MaxHeap<E> maxHeap;
?
public PriorityQueue() {
this.maxHeap = new MaxHeap<>();
}
?
@Override
public void enqueue(E e) {
maxHeap.add(e);
}
?
@Override
public E dequeue() {
return maxHeap.extractMax();
}
?
@Override
public E getFront() {
return maxHeap.getMax();
}
?
@Override
public int size() {
return maxHeap.size();
}
?
@Override
public boolean isEmpty() {
return maxHeap.isEmpty();
}
}</pre>

示例代碼Github

好了唐含，本文就到此為止了。后續(xù)的博文會為大家?guī)鞮eetCode上面的一道題目沫浆，就是使用本文的最大堆來解決的捷枯，到時候可以看一下最大堆的實際應用。 謝謝觀看~~

2. 具體實現(xiàn)

3. 定義隊列接口

以最大堆為底層實現(xiàn)優(yōu)先隊列

以上就是使用數(shù)組來實現(xiàn)一個最大堆的核心代碼专执，下面我們以這個最大堆為基礎實現(xiàn)一個優(yōu)先隊列淮捆。

移除最大元素代碼如下：

image

由于堆的特殊性，所以我們取出元素只會取出堆中的最大元素本股，畢竟人家名字就叫“最大堆”攀痊。由于堆的性質，最大元素其實就是根元素拄显，如果移除根元素蚕苇，那么就不再是一個樹了，解決辦法是移除根元素之后將堆中最后一個元素放到根元素的位置凿叠，但是這樣就不再滿足堆中元素不大于父節(jié)點元素這一性質了。 所以之后一步的操作是用新的根元素和左右孩子中較大的元素進行比較，然后和較大的元素進行互換盒件，直到新的根元素不小于左右孩子為止蹬碧，這樣刪除最大節(jié)點之后的樹就還能滿足堆的性質了。這個過程我們稱為“Sift down”炒刁，即下沉恩沽。 下面使用圖解和代碼來演示如何從取出堆中最大元素。

3. 從堆中移除最大元素

然后我們就可以編寫添加元素的代碼了：

image

一般來講翔始，如果新添加的元素大于其父親節(jié)點罗心，那么將這個元素和其父親節(jié)點進行位置互換，如果仍然大于其父親節(jié)點城瞎，繼續(xù)互換渤闷，直到不大于父節(jié)點為止。 在數(shù)據(jù)結構中脖镀，我們將這個過程稱之為“Sift up”飒箭，翻譯過來就是上浮。下圖展示了“上浮”的過程蜒灰。

通過上面的的概念可以知道弦蹂，向堆中添加一個元素只需要在最后一個元素后面添加一個元素，這個在數(shù)組的操作中是非常簡單的强窖。但是如果添加的元素比父親節(jié)點大凸椿，那么就不再滿足二叉堆的性質，這個問題應該如何解決呢翅溺？

2. 向堆中添加一個元素脑漫。

首先，我們的類中的元素需要具有可比性未巫，所以我們的元素需要是Comparable接口的子類窿撬。成員變量data用來裝載堆中的數(shù)據(jù)，它使用的是ArrayList叙凡。然后根據(jù)上面我們得到的公式劈伴，寫出了“根據(jù)子節(jié)點得到父節(jié)點索引”以及“根據(jù)父節(jié)點得到子節(jié)點”的方法，這三個方法在后面的增刪等操作中尤為重要握爷。