Max Heap 排序法

轉錄自 From Gossip@caterpillar
http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/HeapSort.htm

說明
選擇排序法的概念簡單，每次從未排序部份選一最小值，插入已排序部份的後端，其時間主要花費於在整個未排序部份尋找最小值，如果能讓搜尋最小值的方式加快，選擇排序法的速率也就可以加快，Heap排序法讓搜尋的路徑由樹根至最後一個樹葉，而不是整個未排序部份，因而稱之為改良的選擇排序法。

解法
Heap排序法使用Heap Tree（堆積樹），樹是一種資料結構，而堆積樹是一個二元樹，也就是每一個父節點最多只有兩個子節點（關於樹的詳細定義還請見資料結構書籍），堆積樹的父節點若小於子節點，則稱之為最小堆積（Min Heap），父節點若大於子節點，則稱之為最大堆積（Max Heap），而同一層的子節點則無需理會其大小關係。

可以使用一維陣列來儲存堆積樹的所有元素與其順序，為了計算方便，使用的起始索引是1而不是0，索引1是樹根位置，如果左子節點儲存在陣列中的索引為s，則其父節點的索引為s/2，而右子節點為s+1。

由於使用一維陣列來儲存堆積樹，每一次將樹葉與樹根交換的動作就是將最小值放至後端的陣列，所以最後陣列就是變為已排序的狀態。

其實堆積在調整的過程中，就是一個選擇的行為，每次將最小值選至樹根，而選擇的路徑並不是所有的元素，而是由樹根至樹葉的路徑，因而可以加快選擇的過程，所以Heap排序法才會被稱之為改良的選擇排序法。

【C Language】

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;} 

void createheap(int[]);
void heapsort(int[]);

int main(void) {
    int number[MAX+1] = {-1};
    int i, num;

    srand(time(NULL));

    printf("排序前：");
    for(i = 1; i <= MAX; i++) {
        number[i] = rand() % 100;
        printf("%d ", number[i]);
    }

    printf("\n建立堆積樹：");
    createheap(number);
    for(i = 1; i <= MAX; i++)
        printf("%d ", number[i]);
    printf("\n");

    heapsort(number);

    printf("\n");

    return 0;
}

void createheap(int number[]) {
    int i, s, p;
    int heap[MAX+1] = {-1};

    for(i = 1; i <= MAX; i++) {
        heap[i] = number[i];
        s = i;
        p = i / 2;
        while(s >= 2 && heap[p] > heap[s]) {
            SWAP(heap[p], heap[s]);
            s = p;
            p = s / 2;
        }
    }

    for(i = 1; i <= MAX; i++)
        number[i] = heap[i];

}

void heapsort(int number[]) {
    int i, m, p, s;

    m = MAX;
    while(m > 1) {
        SWAP(number[1], number[m]);
        m--;

        p = 1;
        s = 2 * p;

        while(s <= m) {
            if(s < m && number[s+1] < number[s])
                s++;
            if(number[p] <= number[s])
                break;
            SWAP(number[p], number[s]);
            p = s;
            s = 2 * p;
        }

        printf("\n排序中：");
        for(i = MAX; i > 0; i--)
            printf("%d ", number[i]);
    }
}

【Java】

public class HeapSort {
    public static void sort(int[] number) {
        int[] tmp = new int[number.length + 1];
        for(int i = 1; i < tmp.length; i++) {
            tmp[i] = number[i-1];
        }

        createHeap(tmp);

        int m = number.length;
        while(m > 1) {
            swap(tmp, 1, m);
            m--;

            int p = 1;
            int s = 2 * p;

            while(s <= m) {
                if(s < m && tmp[s+1] < tmp[s])
                    s++;
                if(tmp[p] <= tmp[s])
                    break;
                swap(tmp, p, s);
                p = s;
                s = 2 * p;
            }
        }
        for(int i = 0; i < number.length; i++) {
            number[i] = tmp[i+1];
        }
    }

    private static void createHeap(int[] tmp) {
        int[] heap = new int[tmp.length];

        for(int i = 0; i < heap.length; i++)
            heap[i] = -1;

        for(int i = 1; i < heap.length; i++) {
            heap[i] = tmp[i];
            int s = i;
            int p = i / 2;
            while(s >= 2 && heap[p] > heap[s]) {
                swap(heap, p, s);
                s = p;
                p = s / 2;
            }
        }

        for(int i = 1; i < tmp.length; i++)
            tmp[i] = heap[i];

    }

    private static void swap(int[] number, int i, int j) {
        int t;
        t = number[i];
        number[i] = number[j];
        number[j] = t;
    }
}