關(guān)于最大堆

什么是最大堆和最小堆濒持？最大（屑）堆是指在樹(shù)中，存在一個(gè)結(jié)點(diǎn)而且該結(jié)點(diǎn)有兒子結(jié)點(diǎn)柑营，該結(jié)點(diǎn)的data域值都不小于（大于）其兒子結(jié)點(diǎn)的data域值屈雄，并且它是一個(gè)完全二叉樹(shù)（不是滿二叉樹(shù)）。注意區(qū)分選擇樹(shù)官套，因?yàn)?strong>選擇樹(shù)（selection tree）概念和最小堆有些類似酒奶，他們都有一個(gè)特點(diǎn)是“樹(shù)中的根結(jié)點(diǎn)都表示樹(shù)中的最小元素結(jié)點(diǎn)”。同理最大堆的根結(jié)點(diǎn)是樹(shù)中元素最大的奶赔。那么來(lái)看具體的看一下它長(zhǎng)什么樣惋嚎？（最小堆這里省略）

圖-1

這里需要注意的是：在多個(gè)子樹(shù)中，并不是說(shuō)其中一個(gè)子樹(shù)的父結(jié)點(diǎn)一定大于另一個(gè)子樹(shù)的兒子結(jié)點(diǎn)纺阔。最大堆是樹(shù)結(jié)構(gòu)，而且一定要是完全二叉樹(shù)修然。

最大堆ADT

那么我們?cè)谧鲎畲蠖训某橄髷?shù)據(jù)類型（ADT）時(shí)就需要考慮三個(gè)操作：
（1）笛钝、創(chuàng)建一個(gè)最大堆；
（2）愕宋、最大堆的插入操作玻靡；
（3）、最大堆的刪除操作中贝；
最大堆ADT如下：

struct Max_Heap {
  object: 由多個(gè)元素組成的完全二叉樹(shù)囤捻，其每個(gè)結(jié)點(diǎn)都不小于該結(jié)點(diǎn)的子結(jié)點(diǎn)關(guān)鍵字值
  functions:
    其中heap∈Max_Heap,n,max_size∈int,Element為堆中的元素類型，item∈ Element
    Max_Heap createHeap(max_size)       := 創(chuàng)建一個(gè)總?cè)萘坎淮笥趍ax_size的空堆
    void max_heap_insert(heap, item ,n) := 插入一個(gè)元素到heap中
    Element max_heap_delete(heap,n)     := if(heap不為空) {return 被刪除的元素 }else{return NULL}
}
///其中:=符號(hào)組讀作“定義為”

最大堆內(nèi)存表現(xiàn)形式

我們只是簡(jiǎn)單的定義了最大堆的ADT邻寿，為了能夠用代碼實(shí)現(xiàn)它就必須要考慮最大堆的內(nèi)存表現(xiàn)形式蝎土。從最大堆的定義中视哑，我們知道不管是對(duì)最大堆做插入還是刪除操作，我們必須要保證插入或者刪除完成之后誊涯，該二叉樹(shù)仍然是一個(gè)完全二叉樹(shù)挡毅。基于此暴构，我們就必須要去操作某一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)跪呈。
??第一種方式，我們使用鏈表的方式來(lái)實(shí)現(xiàn)取逾，那么我們需要添加一個(gè)額外的指針來(lái)指向該結(jié)點(diǎn)的父結(jié)點(diǎn)耗绿。此時(shí)就包括了左子結(jié)點(diǎn)指針、右子結(jié)點(diǎn)指針和父結(jié)點(diǎn)指針砾隅，那么空鏈的數(shù)目有可能是很大的误阻，比如葉子結(jié)點(diǎn)的左右子結(jié)點(diǎn)指針和根結(jié)點(diǎn)的父結(jié)點(diǎn)指針，所以不選擇這種實(shí)現(xiàn)方式（關(guān)于用鏈表實(shí)現(xiàn)一般二叉樹(shù)時(shí)處理左右子結(jié)點(diǎn)指針的問(wèn)題在線索二叉樹(shù)中有提及）琉用。
??第二種方式堕绩，使用數(shù)組實(shí)現(xiàn)，在二叉樹(shù)進(jìn)行遍歷的方法分為：先序遍歷邑时、中序遍歷奴紧、后序遍歷和層序遍歷。我們可以通過(guò)層序遍歷的方式將二叉樹(shù)結(jié)點(diǎn)存儲(chǔ)在數(shù)組中晶丘，由于最大堆是完全二叉樹(shù)不會(huì)存在數(shù)組的空間浪費(fèi)黍氮。那么來(lái)看看層序遍歷是怎么做的？對(duì)下圖的最大堆進(jìn)行層序遍歷：

層序遍歷流程變化

最終我們選擇數(shù)組作為最大堆的內(nèi)存表現(xiàn)形式躬审。

基本定義:

#define MAX_ELEMENTS 20
#define HEAP_FULL(n) (MAX_ELEMENTS - 1 == n)
#define HEAP_EMPTY(n) (!n)
typedef struct {
    int key;
}element;
element heap[MAX_ELEMENTS];

下面來(lái)看看最大堆的插入、刪除和創(chuàng)建這三個(gè)最基本的操作。

最大堆的插入

最大堆的插入操作可以簡(jiǎn)單看成是“結(jié)點(diǎn)上浮”承边。當(dāng)我們?cè)谙蜃畲蠖阎胁迦胍粋€(gè)結(jié)點(diǎn)我們必須滿足完全二叉樹(shù)的標(biāo)準(zhǔn)遭殉，那么被插入結(jié)點(diǎn)的位置的是固定的。而且要滿足父結(jié)點(diǎn)關(guān)鍵字值不小于子結(jié)點(diǎn)關(guān)鍵字值炒刁，那么我們就需要去移動(dòng)父結(jié)點(diǎn)和子結(jié)點(diǎn)的相互位置關(guān)系恩沽。具體的位置變化，可以看看下面我畫(huà)的一個(gè)簡(jiǎn)單的圖翔始。

void insert_max_heap(element item ,int *n){
    if(HEAP_FULL(*n)){
      return;
    }
    int i = ++(*n);
    for(;(i != 1) && (item.key > heap[i/2].key);i = i / 2){/// i ≠ 1是因?yàn)閿?shù)組的第一個(gè)元素并沒(méi)有保存堆結(jié)點(diǎn)
      heap[i] = heap[i/2];/// 這里其實(shí)和遞歸操作類似罗心，就是去找父結(jié)點(diǎn)
    }
    heap[i] = item;
}

最大堆的插入

最大堆的刪除

最大堆的刪除操作飒箭，總是從堆的根結(jié)點(diǎn)刪除元素。同樣根元素被刪除之后為了能夠保證該樹(shù)還是一個(gè)完全二叉樹(shù)蜒灰，我們需要來(lái)移動(dòng)完全二叉樹(shù)的最后一個(gè)結(jié)點(diǎn)弦蹂，讓其繼續(xù)符合完全二叉樹(shù)的定義，從這里可以看作是最大堆最后一個(gè)結(jié)點(diǎn)的下沉（也就是下文提到的結(jié)點(diǎn)1）操作强窖。例如在下面的最大堆中執(zhí)行刪除操作：

• 第一步，我們刪除上圖中的根結(jié)點(diǎn)20咙崎；
• 當(dāng)刪除根結(jié)點(diǎn)20之后明顯不是一個(gè)完全二叉樹(shù)优幸，更確切地說(shuō)被分成了兩棵樹(shù)。
• 我們需要移動(dòng)子樹(shù)的某一個(gè)結(jié)點(diǎn)來(lái)充當(dāng)該樹(shù)的根節(jié)點(diǎn)褪猛，那么在(15,2,14,10,1)這些結(jié)點(diǎn)中移動(dòng)哪一個(gè)呢网杆？顯然是移動(dòng)結(jié)點(diǎn)1，如果移動(dòng)了其他結(jié)點(diǎn)（比如14伊滋，10）就不再是一個(gè)完全二叉樹(shù)了碳却。

對(duì)上面三步圖示如下：

顯然現(xiàn)在看來(lái)該二叉樹(shù)雖然是一個(gè)完全二叉樹(shù)，但是它并不符合最大堆的相關(guān)定義新啼，我們的目的是要在刪除完成之后追城，該完全二叉樹(shù)依然是最大堆刹碾。因此就需要我們來(lái)做一些相關(guān)的操作燥撞！

1）、此時(shí)在結(jié)點(diǎn)（15，2）中選擇較大的一個(gè)和1做比較物舒，即15 > 1的色洞，所以15上浮到之前的20的結(jié)點(diǎn)處。
2）冠胯、同第1步類似火诸，找出（14，10）之間較大的和1做比較荠察，即14>1的置蜀，所以14上浮到原來(lái)15所處的結(jié)點(diǎn)。
3）悉盆、因?yàn)樵瓉?lái)14的結(jié)點(diǎn)是葉子結(jié)點(diǎn)盯荤，所以將1放在原來(lái)14所處的結(jié)點(diǎn)處。

element delete_max_heap(int *n){
  int parent, child;
  element temp, item;
  temp = heap[--*n];
  item = heap[1];
  parent = 1,child=2;
  for(;child <= *n; child = child * 2){
   if( (child < *n) && heap[child].key < heap[child+1].key){/// 這一步是為了看當(dāng)前結(jié)點(diǎn)是左子結(jié)點(diǎn)大還是右子結(jié)點(diǎn)大焕盟，然后選擇較大的那個(gè)子結(jié)點(diǎn)
        child++;
      }
      if(temp.key >= heap[child].key){
        break;
      }
      heap[parent] = heap[child];///這就是上圖中第二步和第三步中黃色部分操作
      parent = child;/// 這其實(shí)就是一個(gè)遞歸操作秋秤，讓parent指向當(dāng)前子樹(shù)的根結(jié)點(diǎn)
   }
  heap[parent] = temp;
  return item;
}

同最大堆的插入操作類似，同樣包含n個(gè)元素的最大堆脚翘，其高度為:log2(n+1)灼卢，其時(shí)間復(fù)雜度為：O(log2(n))。

總結(jié)：由此可以看出来农，在已經(jīng)確定的最大堆中做刪除操作鞋真，被刪除的元素是固定的，需要被移動(dòng)的結(jié)點(diǎn)也是固定的备图，這里我說(shuō)的被移動(dòng)的元素是指最初的移動(dòng)灿巧，即最大堆的最后一個(gè)元素。移動(dòng)方式為從最大的結(jié)點(diǎn)開(kāi)始比較揽涮。

最大堆的創(chuàng)建

為什么要把最大堆的創(chuàng)建放在最后來(lái)講抠藕？因?yàn)樵诙训膭?chuàng)建過(guò)程中，有兩個(gè)方法蒋困。會(huì)分別用到最大堆的插入和最大堆的刪除原理盾似。創(chuàng)建最大堆有兩種方法：
（1）、先創(chuàng)建一個(gè)空堆雪标，然后根據(jù)元素一個(gè)一個(gè)去插入結(jié)點(diǎn)零院。由于插入操作的時(shí)間復(fù)雜度為O(log2(n))，那么n個(gè)元素插入進(jìn)去村刨，總的時(shí)間復(fù)雜度為O(n * log2(n))告抄。
（2）、將這n個(gè)元素先順序放入一個(gè)二叉樹(shù)中形成一個(gè)完全二叉樹(shù)嵌牺，然后來(lái)調(diào)整各個(gè)結(jié)點(diǎn)的位置來(lái)滿足最大堆的特性打洼。
現(xiàn)在我們就來(lái)試一試第二種方法來(lái)創(chuàng)建一個(gè)最大堆：假如我們有12個(gè)元素分別為：

{79,66,43,83,30,87,38,55,91,72,49,9}

將上訴15個(gè)數(shù)字放入一個(gè)二叉樹(shù)中龄糊，確切地說(shuō)是放入一個(gè)完全二叉樹(shù)中，如下：

我們從該完全二叉樹(shù)中的最后一個(gè)非葉子節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹(shù)進(jìn)行調(diào)整，然后依次去找倒數(shù)第二個(gè)倒數(shù)第三個(gè)非葉子節(jié)點(diǎn)...

具體步驟

在做最大堆的創(chuàng)建具體步驟中退敦，我們會(huì)用到最大堆刪除操作中結(jié)點(diǎn)位置互換的原理扭勉，即關(guān)鍵字值較小的結(jié)點(diǎn)會(huì)做下沉操作。

• 1）苛聘、就如同上面所說(shuō)找到二叉樹(shù)中倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)87涂炎，然后看以該非葉子結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹(shù)。查看該子樹(shù)是否滿足最大堆要求设哗，很明顯目前該子樹(shù)滿足最大堆唱捣，所以我們不需要移動(dòng)結(jié)點(diǎn)。該子樹(shù)最大移動(dòng)次數(shù)為1网梢。
  
• 2）震缭、現(xiàn)在來(lái)到結(jié)點(diǎn)30，明顯該子樹(shù)不滿足最大堆战虏。在該結(jié)點(diǎn)的子結(jié)點(diǎn)較大的為72拣宰，所以結(jié)點(diǎn)72和結(jié)點(diǎn)30進(jìn)行位置互換。該子樹(shù)最大移動(dòng)次數(shù)為1烦感。
  
• 3）巡社、同樣對(duì)結(jié)點(diǎn)83做類似的操作。該子樹(shù)最大移動(dòng)次數(shù)為1手趣。
  
• 4）晌该、現(xiàn)在來(lái)到結(jié)點(diǎn)43，該結(jié)點(diǎn)的子結(jié)點(diǎn)有{87,38,9}绿渣，對(duì)該子樹(shù)做同樣操作朝群。由于結(jié)點(diǎn)43可能是其子樹(shù)結(jié)點(diǎn)中最小的，所以該子樹(shù)最大移動(dòng)次數(shù)為2中符。
  
• 5）姜胖、結(jié)點(diǎn)66同樣操作，該子樹(shù)最大移動(dòng)次數(shù)為2淀散。
  
• 6）右莱、最后來(lái)到根結(jié)點(diǎn)79堵第，該二叉樹(shù)最高深度為4，所以該子樹(shù)最大移動(dòng)次數(shù)為3隧出。
  

自此通過(guò)上訴步驟創(chuàng)建的最大堆為:

所以從上面可以看出，該二叉樹(shù)總的需要移動(dòng)結(jié)點(diǎn)次數(shù)最大為：10阀捅。

代碼實(shí)現(xiàn)

  void create_max_heap(void){
        int total = (*heap).key;
        /// 求倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)
        int child = 2,parent = 1;
        for (int node = total/2; node>0; node--) {
            parent = node;
            child = 2*node;
            int max_node = 2*node+1;
            element temp = *(heap+parent);
            for (; child <= total; child *= 2,max_node = 2*parent+1) {
                if (child+1 <= total && (*(heap+child)).key < (*(heap+child+1)).key) {
                    child++;
                }
                if (temp.key > (*(heap+child)).key) {
                    break;
                }
                *(heap+parent) = *(heap+child);
                parent = child;
            }
            *(heap+parent) = temp;
        }
    }

/**
 *
 * @param heap  最大堆胀瞪；
 * @param items 輸入的數(shù)據(jù)源
 * @return 1成功，0失敗
 */
int create_binary_tree(element *heap,int items[MAX_ELEMENTS]){
    int total;
    if (!items) {
        return 0;
    }
    element *temp = heap;
    heap++;
    for (total = 1; *items;total++,(heap)++,items = items + 1) {
        element ele = {*items};
        element temp_key = {total};
        *temp = temp_key;
        *heap = ele;
    }
    return 1;
}
///函數(shù)調(diào)用
int items[MAX_ELEMENTS] = {79,66,43,83,30,87,38,55,91,72,49,9};
element *position = heap;
create_binary_tree(position, items);
for (int i = 0; (*(heap+i)).key > 0; i++) {
  printf("binary tree element is %d\n",(*(heap + i)).key);
}
create_max_heap();
for (int i = 0; (*(heap+i)).key > 0; i++) {
  printf("heap element is %d\n",(*(heap + i)).key);
}

上訴代碼在我機(jī)器上能夠成功的構(gòu)建一個(gè)最大堆饲鄙。由于該完全二叉樹(shù)存在n個(gè)元素凄诞，那么他的高度為:log2(n+1)，這就說(shuō)明代碼中的for循環(huán)會(huì)執(zhí)行O(log2(n))次忍级。因此其我理解的平均運(yùn)行時(shí)間為：O(log2(n))帆谍。而其上界為當(dāng)該二叉樹(shù)為滿二叉樹(shù)時(shí)其時(shí)間復(fù)雜度為O((n)。

堆排序

堆排序要比空間復(fù)雜度為O(n)的歸并排序要慢一些轴咱，但是要比空間復(fù)雜度為O(1)的歸并排序要快汛蝙！
??通過(guò)上面最大堆創(chuàng)建一節(jié)中我們能夠創(chuàng)建一個(gè)最大堆。出于該最大堆太大朴肺，我將其進(jìn)行縮小以便進(jìn)行畫(huà)圖演示窖剑。

• 1）鞍盗、把最大堆根結(jié)點(diǎn)91“刪除”需了，第一次排序圖示：
  
  
  進(jìn)過(guò)這一次排序之后，91就處在最終的正確位置上般甲，所以我們只需要對(duì)余下的最大堆進(jìn)行操作肋乍！這里需要注意一點(diǎn)：

??????注意，關(guān)于對(duì)余下進(jìn)行最大堆操作時(shí)：
并不需要像創(chuàng)建最大堆時(shí)敷存，從倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)開(kāi)始住拭。因?yàn)樵谖覀冎皇菍?duì)第一個(gè)和最后一個(gè)結(jié)點(diǎn)進(jìn)行了交換，所以只有根結(jié)點(diǎn)的順序不滿足最大堆的約束历帚，我們只需要對(duì)第一個(gè)元素進(jìn)行處理即可

• 2）滔岳、繼續(xù)對(duì)結(jié)點(diǎn)87進(jìn)行相同的操作：
  

  
  同樣，87的位置確定挽牢。

• 3）谱煤、現(xiàn)在我們來(lái)確定結(jié)點(diǎn)83的位置：
  

• 4）、經(jīng)過(guò)上訴步驟就不難理解堆排序的原理所在禽拔，最后排序結(jié)果如下：

  
  

經(jīng)過(guò)上訴多個(gè)步驟之后刘离，最終的排序結(jié)果如下：

[38室叉、43、72硫惕、79茧痕、83、87恼除、91]

很明顯這是一個(gè)正確的從小到大的順序踪旷。

編碼實(shí)現(xiàn)

這里需要對(duì)上面的代碼進(jìn)行一些修改！因?yàn)樵谂判蛑谢砘裕覀兊牡?個(gè)元素是不用去放一個(gè)哨兵的令野，我們的元素從原來(lái)的第一個(gè)位置改為從第0個(gè)位置開(kāi)始放置元素。

void __swap(element *lhs,element *rhs){
    element temp = *lhs;
    *lhs = *rhs;
    *rhs = temp;
}

int create_binarytree(element *heap, int items[MAX_SIZE], int n){
    if (n <= 0) return 0;
    for (int i = 0; i < n; i++,heap++) {
        element value = {items[i]};
        *heap = value;
    }
    return 1;
}

void adapt_maxheap(element *heap ,int node ,int n){
    int parent = node - 1 < 0 ? 0 : node - 1;
    int child = 2 * parent + 1;/// 因?yàn)闆](méi)有哨兵徽级，所以在數(shù)組中的關(guān)系由原來(lái)的：parent = 2 * child => parent = 2 * child + 1
    int max_node = max_node = 2*parent+2 < n - 1 ? 2*parent+2 : n - 1;
    element temp = *(heap + parent);
    for (;child <= max_node; parent = child,child = child * 2 + 1,max_node = 2*parent+2 < n - 1 ? 2*parent+2 : n - 1) {
        if ((heap + child)->key <= (heap + child + 1)->key && child + 1 < n) {
            child++;
        }
        if ((heap + child)->key < temp.key) {
            break;
        }
        *(heap + parent) = *(heap + child);
    }
    *(heap + parent) = temp;
}

int create_maxheap(element *heap ,int n){

    for (int node = n/2; node > 0; node--) {
        adapt_maxheap(heap, node, n);
    }
    return 1;
}

void heap_sort(element *heap ,int n){
    ///創(chuàng)建一個(gè)最大堆
    create_maxheap(heap, n);
    ///進(jìn)行排序過(guò)程
    int i = n - 1;
    while (i >= 0) {
        __swap(heap+0, heap + i);/// 將第一個(gè)和最后一個(gè)進(jìn)行交換
        adapt_maxheap(heap, 0, i--);///將總的元素個(gè)數(shù)減一气破，適配成最大堆，這里只需要對(duì)首元素進(jìn)行最大堆的操作
    }
}

調(diào)用：

/// 堆排序
int n = 7;
int items[7] = {87,79,38,83,72,43,91};
element heap[7];
create_binarytree(heap, items, n);
heap_sort(heap, n);///38,43,72,79,83,87,91

在實(shí)現(xiàn)堆排序時(shí)最需要注意的就是當(dāng)沒(méi)有哨兵之后餐抢，父結(jié)點(diǎn)和左右孩子結(jié)點(diǎn)之間的關(guān)系發(fā)生了變化：

parent = 2 * child + 1;///左孩子
parent = 2 * child + 2;///右孩子

關(guān)于對(duì)排序相關(guān)的知識(shí)點(diǎn)已經(jīng)整理完了现使。其時(shí)間復(fù)雜度和歸并排序的時(shí)間時(shí)間復(fù)雜度是一樣的O(N*LogN)。

結(jié)束語(yǔ)

當(dāng)我們?cè)谧龊屯耆鏄?shù)有關(guān)的操作時(shí)旷痕，對(duì)于完全二叉樹(shù)采用順序存儲(chǔ)表示朴下，需要記住對(duì)于任意一個(gè)下標(biāo)為i(1 ≤ i ≤ n)的結(jié)點(diǎn)：父結(jié)點(diǎn)為：i / 2（i ≠ 1），若i = 1苦蒿，則i是根節(jié)點(diǎn)殴胧。左子結(jié)點(diǎn)：2i（2i ≤ n）， 若不滿足則無(wú)左子結(jié)點(diǎn)佩迟。右子結(jié)點(diǎn)：2i + 1(2i + 1 ≤ n)团滥，若不滿足則無(wú)右子結(jié)點(diǎn)。
??關(guān)于最大堆的相關(guān)操作（插入报强、刪除灸姊、創(chuàng)建和排序）已經(jīng)一一學(xué)習(xí)完畢。這些操作中秉溉，刪除力惯、創(chuàng)建和排序思想非常類似，都是操作結(jié)點(diǎn)下沉召嘶。而插入操作相反父晶，類似上浮的操作！