經典算法學習——堆排序

經典算法學習——堆排序

堆排序是相對其他排序稍微麻煩的排序，是一種利用堆的性質進行的選擇排序。堆其實是一棵完全二叉樹，只要任何一個非葉節點的關鍵字不大於或者不小於其左右孩子節點，就可以形成堆。堆分為大頂堆和小頂堆。由上述性質可知大頂堆的堆頂的關鍵字是所有關鍵字中最大的，小頂堆的堆頂的關鍵字是所有關鍵字中最小的。堆排序同快速排序一樣都是不穩定排序。示例代碼上傳至：https://github.com/chenyufeng1991/HeapSort

堆排序的思想：利用大頂堆（小頂堆） 堆頂記錄的是最大關鍵字（最小關鍵字）這一特性，使得每次從無序中選擇最大記錄（最小記錄）變得簡單。注意：大頂堆構造的是遞增序列，小頂堆構造的是遞減序列。

（1）將初始待排序關鍵字序列（R0,R1....Rn-1），構建成大頂堆，此堆為初始的無序區；

（2）將堆頂元素R[0]與最後一個元素R[n-1]交換，此時得到新的無序區(R0,R1....Rn-2)和新的有序區（Rn-1），且滿足R[0,1...n-2]<=R[n-1];

（3）由於交換後新的堆頂R[0]可能違反堆的性質，因此需要對當前無序區(R0,R1...Rn-2)調整為新堆，然後再次將R[0]與無序區最後一個元素交換，得到新的無序區(R0,R1...Rn-3)和新的有序區(Rn-2,Rn-1).不斷重復此過程知道有序區的元素個數為n-1,則整個排序過程完成。

操作過程如下：

（1）初始化堆：將[0...n-1]構造為堆；

（2）將當前無序區的堆頂元素R[0]同該區間的最後一個記錄交換，然後將新的無序區調整為新的堆；

因此對於堆排序，最重要的兩個操作就是構造初始堆和調整堆，其實構造初始堆也是調整堆的過程，只不過構造初始堆是對所有的非葉節點都進行調整。

實例代碼如下：

//
//  main.c
//  Train
//
//  Created by chenyufeng on 16/1/30.
//  Copyright © 2016年 chenyufengweb. All rights reserved.
//

#include 

void BuildHeap(int *a,int size);
void swap(int *a,int *b);
void HeapSort(int *a,int size);
void HeapAdjust(int *a,int i,int size);

int main(int argc,const char *argv[]){

    int a[] = {3,25,9,30,2};
    HeapSort(a, 5);
    for (int i = 0; i < 5; i++) {
        printf("%d ",a[i]);
    }

    return 0;
}

//建立堆
void BuildHeap(int *a,int size){

    for (int i = size - 1; i >= 0; i--) {
        HeapAdjust(a, i, size);
    }

}

//交換兩個數
void swap(int *a,int *b){

    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

//堆排序
void HeapSort(int *a,int size){

    BuildHeap(a, size);
    for (int i = size - 1; i >= 0; i--) {
        //交換堆頂和最後一個元素，即每次將剩余元素中的最大者放到後面；
        swap(&a[0], &a[i+1]);
        //重新調整堆為大頂堆；
        HeapAdjust(a, 0, i );
    }
}

//調整堆
void HeapAdjust(int *a,int i,int size){

    int lchild = 2 * i;//左孩子節點；
    int rchild = 2 * i + 1;//右孩子節點；
    int max = i;

    if (i <= size) {
        if (lchild <= size && a[lchild] > a[max]) {
            max = lchild;
        }

        if (rchild <= size && a[rchild] > a[max]) {
            max = rchild;
        }

        if (i != max) {
            swap(&a[i], &a[max]);
            //避免調整之後以max為父節點的子樹不是堆；
            HeapAdjust(a, max, size);
        }
    }
}