堆排序

算法导论 第六章 堆排序

堆是一个棵完全二叉树，通常用一个数组表示。这样的数组有两个属性：lenght(A)是数组中的元素个数，heap-size(A)是存放在A中的堆的元素个数。

堆排序的时间复杂度为O(nlgn).

给定堆中结点i的下标，其父为i/2,其左孩子为i*2，右孩子为i*2 + 1。

堆分为大根堆和小根堆。小根堆通常在构造优先级队列时使用。

常用的过程有：max-heaplify （堆调整）、build-max-heap （堆构造）、heap-sort （堆排序）。

以下程序根据书中思想而来：

/**
 * Max Heap Sort
 * It is a in-place sort. Its time is O(nlgn).
 * An array A[1...n] has the following features:
 * i is among 1 and n.
 * its parent is i/2 (i >> 1);
 * its left child is i*2 (i << 1);
 * its right child is i*2 + 1 (i << 1 + 1;
 * parent >= {left child, right child}
 * ---------------------------------------------
 */
#include<stdio.h>

void buildmaxheap(int* A, int length);
void maxheap(int* A, int i, int length);
void maxheapsort(int* A, int length);

void buildmaxheap(int* A, int length) {
        int i = 0;
        for (i = length >> 1; i >= 1; i--) {
                maxheap(A, i, length);
        }
}

void maxheap(int* A, int i, int length) {
        int left = i << 1;
        int right = left + 1;
        int largest = i;

        if (left <= length && A[left] > A[largest]) {
                largest = left;
        }

        if (right <= length && A[right] > A[largest]) {
                largest = right;
        }

        if (largest != i) {
                A[0] = A[largest];
                A[largest] = A[i];
                A[i] = A[0];
                maxheap(A, largest, length);
        }
}

void maxheapsort(int* A, int length) {
        int i = length;

        if (A == NULL) return;

        buildmaxheap(A, length);

        // We need n-1 loop to get the other in order.
        for(;i >= 2;i--) {
                A[0] = A[i];
                A[i] = A[1];
                A[1] = A[0];

                maxheap(A, 1, i - 1);
        }
}

int main() {
        int A[] = {0,2,8,7,1,3,5,6,4};
        int len = sizeof(A) / sizeof(int) - 1;
        int i = 1;

        maxheapsort(A, len);

        for (i = 1; i <= len; i++)
                printf("%d,",A[i]);

        printf("\n");
        return 0;
}