資料結構演算法 - 優先順序佇列和堆排序
摘要：
佇列是一種特徵為FIFO的資料結構，每次都是從隊首彈出。優先佇列與其不同的是，它不遵循先進先出的規則，而是根據佇列中元素的優先權，優先權最大的先被取出。今天我們來讀讀原始碼層的優先順序佇列，到底是怎麼實現的，在這之前我們不妨思考一下。如果要我們自己去實現，我們怎麼去實現一個優先順序佇列？
...
佇列是一種特徵為FIFO的資料結構，每次都是從隊首彈出。優先佇列與其不同的是，它不遵循先進先出的規則，而是根據佇列中元素的優先權，優先權最大的先被取出。今天我們來讀讀原始碼層的優先順序佇列，到底是怎麼實現的，在這之前我們不妨思考一下。如果要我們自己去實現，我們怎麼去實現一個優先順序佇列？
儲存結構分為陣列和連結串列，假設我們用普通的陣列去實現，我們要麼入佇列的時候找到其合適的位置，讓優先順序最高的排在陣列的最前面。要麼每次出佇列的時候遍歷整個陣列，選出優先順序最高的出佇列。不管怎樣時間複雜度都是 O(n) , 那麼有沒有一種更好的方法？答案都是採用二叉堆。
template<class E>
class PriorityQueue {
int count;// 陣列的大小，不夠要擴容
int index = 0;// 當前資料的角標位置
E *array = NULL;// 資料陣列
private:
// 往上調整為大根堆
void shiftUp(int index) {
if (index > 1 && array[index] > array[index / 2]) {
swap(array[index], array[index / 2]);
shiftUp(index / 2);
}
}
// 往下調整為大根堆
void shiftDown(int k) {
while (k * 2 <= index) {// 到底的情況
// 最大指向左孩子
int max = 2 * k;
// 有右孩子且右孩子大於左孩子
if (max + 1 <= index && array[max + 1] > array[max]) {
max = max+1;
}
// 最大的是自己
if(array[k] > array[max]){
break;
}
// 交換，最大的網上冒
swap(array[k],array[max]);
k = max;
}
}
public:
PriorityQueue(int count) {
this->count = count;
array = new E[count];
}
bool isEmpty() {
return index == 0;
}
E pop() {
E max = array[1];
// 最後兩個
array[1] = array[index];
index--;
shiftDown(1);
return max;
}
void push(E e) {
array[index + 1] = e;
index++;
// 不斷的調整堆
shiftUp(index);
}
};
當我們不斷往優先順序佇列中取資料是，會發現我們的資料是從大到小排列的，那是因為當資料插入和移除時，我們都會在內部維持一個最大堆，因此優先順序佇列就可以延伸到堆排序了。在沒有了解過優先順序佇列之前，我們往往比較難以理解堆排序（我知道大家都會寫），但當我們瞭解了優先順序佇列之後，就會發現堆排序原來如此。
/**
* 調整大根堆
*/
void adjustHeap(int arr[], int k, int n) {
while (k * 2 + 1 < n) {// 到底的情況
// 最大指向左孩子
int max = 2 * k + 1;
// 有右孩子且右孩子大於左孩子
if (max + 1 < n && arr[max + 1] > arr[max]) {
max = max + 1;
}
// 最大的是自己
if (arr[k] > arr[max]) {
break;
}
// 交換，最大的網上冒
swap(arr[k], arr[max]);
k = max;
}
}
void headSort(int arr[], int len) {
// 1. 從最後一個不是葉子節點的節點，開始調整為大根堆
for (int i = len / 2 - 1; i >= 0; --i) {
adjustHeap(arr, i, len);
}
// 2. 第一個與最後一個進行交換，然後再調整為大根堆，但是不考慮最後一個了
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
adjustHeap(arr, 0, i);// 對第 0 個位置進行調整
}
}
視訊連結:ofollow,noindex">https://pan.baidu.com/s/1qdCz_n01FkKLO0UWpNEN9A
視訊密碼:rktg