數據結構中的優先級隊列：特徵、類型和實現

已發表: 2021-05-02

目錄

介紹

數據結構中的優先級隊列是“普通”隊列的擴展。 它是一種包含一組項目的抽像數據類型。 它就像“普通”隊列，只是出隊元素遵循優先級順序。 優先級順序首先使那些具有最高優先級的項目出隊。 本博客將讓您更深入地了解優先級隊列及其在 C 編程語言中的實現。

什麼是優先隊列？

它是一種抽像數據類型，提供了一種維護數據集的方法。 “正常”隊列遵循先進先出的模式。 它以與插入操作時相同的順序使元素出隊。 但是，優先級隊列中的元素順序取決於該隊列中元素的優先級。 優先級隊列將優先級最高的元素移動到優先級隊列的開頭，將最低優先級的元素移動到優先級隊列的後面。

它僅支持那些可比較的元素。 因此，數據結構中的優先級隊列按升序或降序排列元素。

您可以將優先隊列想像為在醫院排隊等候的幾個患者。 在這裡，患者的情況定義了優先順序。 受傷最嚴重的患者將排在隊列中的第一位。

優先隊列的特點是什麼？

如果隊列具有以下特徵，則稱為優先隊列：

  • 每個項目都有一些與之相關的優先級。
  • 具有最高優先級的項目被移到最前面並首先被刪除。
  • 如果兩個元素共享相同的優先級值，則優先級隊列遵循先進先出原則進行隊列操作。

優先隊列有哪些類型？

優先級隊列有兩種類型：

  • 升序優先隊列
  • 降序優先隊列

升序優先隊列

升序優先級隊列將最高優先級賦予該隊列中較低的數字。 例如，優先級隊列中有六個數字，分別是 4、8、12、45、35、20。首先，您將這些數字按升序排列。 新列表如下：4、8、12、20、35、45。在這個列表中，4是最小的數字。 因此，升序優先級隊列將數字 4 視為最高優先級。

4 8 12 20 35 45

在上表中，4 的優先級最高，45 的優先級最低。

降序優先隊列

降序優先級隊列將最高優先級賦予該隊列中的最高編號。 例如，優先級隊列中有六個數字，分別是 4、8、12、45、35、20。首先，您將這些數字按升序排列。 新列表如下：45、35、20、12、8、4。在這個列表中，45是最高的數字。 因此，降序優先級隊列將數字 45 視為最高優先級。

45 35 20 12 8 4

在上表中，4 的優先級最低，45 的優先級最高。

數據結構中優先級隊列的實現

您可以通過以下方式之一實現優先級隊列：

  • 鍊錶
  • 二進制堆
  • 數組
  • 二叉搜索樹

二叉堆是在數據結構中實現優先級隊列最有效的方法。

下表總結了優先級隊列中不同操作的複雜性。

手術無序數組有序數組二叉堆二叉搜索樹
插入0(1) 0(N) 0(log(N)) 0(log(N))
窺視0(N) 0(1) 0(1) 0(1)
刪除0(N) 0(1) 0（日誌（N）） 0(log(N))

二叉堆

二叉堆樹以特定順序組織樹的所有父節點和子節點。 在二叉堆樹中，一個父節點最多可以有 2 個子節點。 父節點的值可以是：

  • 等於或小於子節點的值。
  • 等於或大於子節點的值。

上述過程將二叉堆分為兩種：最大堆和最小堆。

最大堆

最大堆是一個二叉堆，其中父節點的值等於或大於子節點的值。 樹的根節點具有最高值。

在最大堆二叉樹中插入元素

您可以執行以下步驟在數據結構的優先級隊列中插入一個元素/數字。

  1. 該算法從上到下和從左到右掃描樹以找到一個空槽。 然後它將元素插入樹中的最後一個節點。
  2. 插入元素後，二叉樹的順序就被打亂了。 您必須相互交換數據才能對最大堆二叉樹的順序進行排序。 您必須不斷打亂數據，直到樹滿足最大堆屬性。

在最大堆二叉樹中插入元素的算法

如果樹為空且不包含節點，

創建一個新的父節點newElement。

else（父節點已經可用）

將 newElement 插入樹的末尾（即從左到右的樹的最後一個節點。）

最大堆化樹

刪除最大堆二叉樹中的元素

  1. 您可以執行以下步驟來刪除數據結構中優先級隊列中的元素。
  2. 選擇要從二叉樹中刪除的元素。
  3. 通過與最後一個節點數據交換來移動樹末尾的數據。
  4. 刪除二叉樹的最後一個元素。
  5. 刪除元素後，二叉樹的順序就被打亂了。 您必須對順序進行排序以滿足最大堆的屬性。 您必須不斷打亂數據，直到樹滿足最大堆屬性。

刪除最大堆二叉樹中元素的算法

如果 elementUpForDeletion 是 lastNode，

刪除 elementUpForDeletion

否則將 elementUpForDeletion 替換為 lastNode

刪除 elementUpForDeletion

最大堆化樹

在最大堆二叉樹中查找最大或最小元素

在最大堆二叉樹中，查找操作返回樹的父節點（最高元素）。

在最大堆二叉樹中找到最大值或最小值的算法

返回父節點

使用最大堆二叉樹的優先級隊列的程序實現

#include <stdio.h>

int binary_tree = 10;

int max_heap = 0;

常量 int 測試 = 100000;

無效交換（int *x，int *y）{

詮釋一個;

a = *x;

*x=*y;

*y = a;

}

//在最大堆樹中查找父節點的代碼

int findParentNode(int node[], int root) {

if ((root > 1) && (root < binary_tree)) {

返回根/2；

}

返回-1；

}

void max_heapify(int node[], int root) {

int leftNodeRoot = findLeftChild（節點，根）；

int rightNodeRoot = findRightChild（節點，根）；

// 在根、左孩子和右孩子中找到最高的

int最高=根；

if ((leftNodeRoot <= max_heap) && (leftNodeRoot >0)) {

if (node[leftNodeRoot] > node[highest]) {

最高=leftNodeRoot；

}

}

if ((rightNodeRoot <= max_heap) && (rightNodeRoot >0)) {

if (node[rightNodeRoot] > node[highest]) {

最高=右節點根；

}

}

如果（最高！=根）{

交換（&節點[根]，&節點[最高]）；

max_heapify（節點，最高）；

}

}

無效create_max_heap（int節點[]）{

詮釋d;

for(d=max_heap/2; d>=1; d–) {

max_heapify（節點，d）；

}

}

整數最大值（整數節點 []）{

返回節點[1]；

}

int find_max(int node[]) {

int maxNode = 節點[1];

節點[1] = 節點[max_heap];

最大堆–；

最大堆（節點，1）；

返回最大節點；

}

void descend_key(int node[], int node, int key) {

A[根] = 鍵；

max_heapify（節點，根）；

}

void increase_key(int node[], int root, int key) {

節點[根] = 鍵；

while((root>1) && (node[findParentNode(node, root)] < node[root])) {

交換(&node[root], &node[findParentNode(node, root)]);

root = findParentNode（節點，根）；

}

}

無效插入（int節點[]，int鍵）{

最大堆++；

節點[max_heap] = -1*test;

增加鍵（節點，最大堆，鍵）；

}

無效顯示堆（int節點[]）{

詮釋d;

對於（d=1；d<=max_heap；d++）{

printf(“%d\n”,節點[d]);

}

printf(“\n”);

}

int main() {

整數節點[二進制樹]；

插入（節點，10）；

插入（節點，4）；

插入（節點，20）；

插入（節點，50）；

插入（節點，1）；

插入（節點，15）；

顯示堆（節點）；

printf(“%d\n\n”, 最大值(節點));

顯示堆（節點）；

printf(“%d\n”, extract_max(node));

printf(“%d\n”, extract_max(node));

返回0；

}

最小堆

最小堆是一個二叉堆，其中父節點的值等於或小於子節點的值。 樹的根節點具有最低值。

您可以以與最大堆相同的方式實現最小堆，但順序相反。

結論

文章中給出的示例僅用於說明目的。 您可以根據您的要求修改上面給出的語句。 在這篇博客中，我們了解了數據結構中優先級隊列的概念。 你可以試試這個例子來加強你的數據結構知識。

如果您想了解數據科學，請查看 IIIT-B 和 upGrad 的數據科學執行 PG 計劃，該計劃是為在職專業人士創建的，提供 10 多個案例研究和項目、實用的實踐研討會、行業專家的指導、1與行業導師一對一，400 多個小時的學習和頂級公司的工作協助。

從世界頂級大學在線學習數據科學課程。 獲得行政 PG 課程、高級證書課程或碩士課程，以加快您的職業生涯。

優先隊列的應用有哪些？

優先級隊列是一個特殊隊列，其中元素根據其優先級插入。 此功能在實現各種其他數據結構時非常有用。 以下是優先級隊列的一些最流行的應用：
 1. Dijkstra 的 Shortest Path 算法：在 Dijkstra 的 Shortest Path 算法中，當圖以鄰接表的形式存儲時，可以使用優先隊列。
 2. Prim 算法： Prim 算法對節點的值或鍵使用優先級隊列，並在每一步提取這些值中的最小值。
 數據壓縮：霍夫曼代碼使用優先隊列來壓縮數據。
 操作系統：優先級隊列對於負載平衡和中斷處理等各種進程中的操作系統非常有用。

使用數組實現優先級隊列時使用了什麼方法？

使用數組實現優先級隊列的方法很簡單。 創建一個結構來存儲元素的值和優先級，然後創建該結構的數組來存儲元素。 此實現涉及以下操作：
 1. enqueue()——這個函數將元素插入到隊列的末尾。
 2. peek() - 這個函數會遍歷數組，返回優先級最高的元素。 如果找到兩個具有相同優先級的元素，則返回其中值最高的元素。
 3. dequeue() - 此函數將所有元素移動到 peek() 函數返回的元素左側 1 個位置並減小大小。

最大堆和最小堆有什麼區別？

下面說明最大堆和最小堆之間的區別。
 最小堆 -在最小堆中，根節點的鍵必須小於或等於其子節點的鍵。 它使用升序優先級。 具有最小鍵的節點是優先級。 最小的元素在任何其他元素之前彈出。
 最大堆 ​​-在最大堆中，根節點的鍵必須大於或等於其子節點的鍵。 它使用降序優先級。 具有最大鍵的節點是優先級。 最大的元素在任何其他元素之前彈出。