Etherland

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://iwinux.blogbus.com/logs/3128144.html

//hsort.c
//算法来自《算法导论》

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef unsigned long int ULong;

ULong heapSize = 0;

ULong Parent(ULong index) {

    //因为C语言的数组起始下标为0
    //所以和《算法导论》中的代码有点不同
    //index >> 1 == i / 2;
    return (index % 2) ? (index >> 1) : ((index >> 1) - 1);

}

ULong Left(ULong index) {
    
    //index << 1 == index * 2;
    return ((index << 1) + 1);

}

ULong Right(ULong index) {

    return ((index << 1) + 2);

}

void swap(char * a, char * b) {
    
    char tmp = *a;
    *a = *b;
    *b = tmp;

}

//array[index] 与其左右子树进行递归对比
//用最大值替换array[index]
void maxHeapify(char * array, ULong index) {

    ULong largest = 0;
    ULong left = Left(index);
    ULong right = Right(index);

    if ((left <= heapSize) && (array[left] > array[index]))
        largest = left;
    else
        largest = index;

    if ((right <= heapSize) && (array[right] > array[largest]))
        largest = right;

    if (largest != index) {

        swap(&array[index], &array[largest]);
        maxHeapify(array, largest);

    }

}

//初始化堆，将数组中的每一个元素置放到适当的位置
//完成之后，堆顶的元素为数组的最大值
void buildMaxHeap(char * array, ULong length) {

    int i;
    heapSize = length;

    for (i = (length >> 1); i >= 0; i--)
        maxHeapify(array, i);

}

int heapSort(char * array, ULong length) {

    int i;

    buildMaxHeap(array, (length - 1));

    //堆顶元素（即数组的最大值）被置换到数组的尾部
    //然后从堆中移除该元素
    //然后重建堆
    for (i = (length - 1); i >= 1; i--) {
        swap(&array[0], &array[i]);
        heapSize--;
        maxHeapify(array, 0);
    }

}