什么是堆？

維基百科中對(duì)堆的定義如下：

「堆是計(jì)算機(jī)科學(xué)中的一種特別的完全二叉樹。若是滿足以下特性，即可稱為堆：“給定堆中任意節(jié)點(diǎn)P和C，若P是C的父節(jié)點(diǎn)，那么P的值會(huì)小于等于（或大于等于）C的值”。若父節(jié)點(diǎn)的值恒小于等于子節(jié)點(diǎn)的值，此堆稱為小頂堆（min heap）；反之，若父節(jié)點(diǎn)的值恒大于等于子節(jié)點(diǎn)的值，此堆稱為大頂堆（max heap）?！?/p>

堆中元素的性質(zhì)

由于堆本質(zhì)上是一棵完全二叉樹，通常是采用數(shù)組作為其存儲(chǔ)結(jié)構(gòu)，以數(shù)組作為其存儲(chǔ)結(jié)構(gòu)的好處是，我們可以通過下標(biāo)索引的方式去訪問節(jié)點(diǎn)的父節(jié)點(diǎn)和孩子節(jié)點(diǎn)。

• 對(duì)于堆中任意一個(gè)節(jié)點(diǎn) i 有：

  • i的父節(jié)點(diǎn)：parent( i ) = floor( (i - 1) / 2 )

  • i的左孩子：left( i ) = 2 * i + 1

  • i的右孩子：right( i ) = 2 * i + 2

• 對(duì)于一個(gè)完全二叉樹，我們還可以輕易的找到其最后一個(gè)葉子節(jié)點(diǎn)：

  最后一個(gè)葉子節(jié)點(diǎn)的下標(biāo)：floor( ( j - 1 ) / 2 )，其中j是堆中最后一個(gè)元素的下標(biāo)。

堆的操作

創(chuàng)建堆

• 若要向一個(gè)空的數(shù)組中插入元素來創(chuàng)建堆，首先需將待插入的元素安置在數(shù)組的最后一位，再使用shiftup()調(diào)整其位置，(以大頂堆為例)若其父節(jié)點(diǎn)元素值大于帶插入的元素，那么就將其與它的父節(jié)點(diǎn)交換

#define MAXN 1000
 int heap[MAXN], size = 0;
 void shiftup(int start){
     int i = start;
     while(i >= 0 && heap[i] > heap[(i-1)/2]){
         swap(heap[(i-1)/2], heap[i]);
         i = (i-1)/2;
    }
 }
 void insert(int x){ //向堆中插入元素
     heap[size] = x;
     shiftup(size);
     size++;
 }

• 另一種常見的創(chuàng)建堆的方式是將一個(gè)數(shù)組堆化(heapify)，從堆的最后一個(gè)非葉子節(jié)點(diǎn)開始，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行shiftdown操作。

void shiftdown(int* arr, int start, int length){
    int i = start, j = 2 * i + 1;
    while(j < length){
        if(j + 1 < length && arr[j + 1] > arr[j])j++;
        if(arr[i] > arr[j])break;
        swap(arr[j], arr[i]);
        i = j;
        j = 2 * j + 1;
    }
}
 void heapify(int* arr, int length){
     /**
      將一個(gè)給定的數(shù)組arr轉(zhuǎn)化為大頂堆
      時(shí)間復(fù)雜度：O(n)
      */
     int i = (length - 2) / 2;
     while(i >= 0)shiftdown(arr, i--, length);
 }

刪除堆頂元素

將堆頂元素用堆的最后一個(gè)元素替代，再使用shiftdown操作

void pop(){
   if(size == 0)return;
   heap[0] = heap[size - 1];
   shiftdown(0);
 }

返回堆頂元素

int top(){
   if(size == 0){
     printf("Empty Heap!\n");
     return -1;
  }return heap[0];
 }

STL優(yōu)先隊(duì)列

與通常的隊(duì)列不同，優(yōu)先隊(duì)列中的元素被賦予優(yōu)先級(jí)，當(dāng)訪問隊(duì)列中的元素時(shí)，優(yōu)先級(jí)更高的元素先被訪問。通常采用堆數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)優(yōu)先隊(duì)列。幸運(yùn)的是，在STL中已經(jīng)有了實(shí)現(xiàn)好的優(yōu)先隊(duì)列模版，直接調(diào)用就可以啦～

 #include <functional> //包含greater和less兩個(gè)優(yōu)先級(jí)函數(shù)
 #include <queue> //priority_queue的頭文件
 
 /*大頂堆*/
 priority_queue<int, vector<int>, less<int>>pq_max;
 /*小頂堆*/
 priority_queue<int, vector<int>, greater<int>>pq_min;
 
 /*優(yōu)先隊(duì)列的操作*/
 pq.push();  //向隊(duì)列中插入一個(gè)元素
 pq.pop();  //刪除堆頂?shù)脑? pq.top();  //返回堆頂元素
 pq.size();  //返回隊(duì)列中的元素個(gè)數(shù)
 pq.empty();  //判斷隊(duì)列是否為空

分別向上述兩個(gè)優(yōu)先隊(duì)列中插入元素，并依次彈出元素查看，效果如下：

插入序列：4 5 3 2 98 32 19 25
 /*pq_max*/
 98 32 25 19 5 4 3 2
 /*pq_min*/
 2 3 4 5 19 25 32 98