堆排序与程序实现

堆排序（heapsort）的时间复杂度为O(nlgn)，具有空间原址性（任何时候都只需要常数个额外的元素空间存储临时数据）。同时拥有了插入排序和归并排序的优点。

算法：

计算父结点、左右孩子的下标
PARENT(i)
    return [i/2]
LEFT(i)
    return 2i
RIGHT(i)
    return [2i+1]

维护最大堆性质
MAX-HEAPIFY(A,i)
    left = LEFT(i)
    right = RIGHT(i)
    if left <= A.heap_size and A[left] > A[i]
        largest = left
    else 
        largest = i
    if right <= A.heap_size and A[right] > A[largest]
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A,largest)    # 递归调用

建堆
BUILD-MAX-HEAP(A)
    A.heap_size = A.length
    for i = [A.length/2] downto 1
        MAX-HEAPIFY(A,i]

堆排序，将根结点的值（由最大堆性质决定，此值即为堆中最大值）取出，对剩下的数据堆重新维护最大
堆性质，再取出根结点的值，各根结点值从数组尾部倒序放置，如此循环直至结束，则数据从数组头部到
尾部由小到大排列。
HEAPSORT(A)
    BUILD-MAX-HEAP(A)
    for i = A.length downto 2
        exchange A[1] with A[i]
        A.heap_size = A.heap_size - 1
        MAX-HEAPIFY(A,1)

Python 脚本：

# 维护父结点保持大于左右孩子的性质
# a 数组，i 结点
def max_heapify(a, i, heapsize):
    # 左孩子
    left = 2*i + 1
    # 右孩子
    right = left + 1
    #print(i, left, right)
    # 比较左孩子和父结点大小，再用其中较大者与右孩子比较
    if(left < heapsize and a[i] < a[left]):
        largest = left
    else:
        largest = i
    if(right < heapsize and a[largest] < a[right]):
        largest = right
    # 如果最大者不是父结点，将父结点与最大者进行交换
    if(largest != i):
        temp = a[i]
        a[i] = a[largest]
        a[largest] = temp
        # 交换之后有可能违反最大堆性质，递归调用维护性质
        max_heapify(a, largest, heapsize)

# 构建最大堆，通过遍历节点，实现根结点是堆数据中的最大值
def build_max_heap(a):
    heapsize = len(a)    
    i = int(heapsize/2) - 1
    # 从后到前，对结点进行遍历维护
    while(i>=0):
        max_heapify(a, i, heapsize)
        i = i - 1
        #print(a)

# 交换函数
def swap(a, i, j):
    temp = a[i]
    a[i] = a[j]
    a[j] = temp

# 构建最大堆之后，根结点处有最大的数，将最大值与最后的数交换取出，再对剩余的 len-1 数据继续重复此操作
def heap_sort(a):
    build_max_heap(a)
    i = len(a) - 1
    while(i>=1):
        swap(a, 0, i)    # 交换根结点和最后一个数
        max_heapify(a, 0, i)
        i = i - 1
        #print(a)

if __name__ == '__main__':
    a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
    print(a)
    #build_max_heap(a)
    heap_sort(a)
    print(a)

C程序：

#include<stdio.h>

// 维护父结点保持大于左右孩子的性质
// a 数组，i 结点, heapsize 堆大小 
void max_heapify(int a[], int i, int heapsize)
{
    int left, right, largest, temp;
    left = 2*i + 1;     // 左孩子下标索引 
    right = left + 1;   // 右孩子下标索引
    //printf("%d,%d,%d\n",i,left,right);
    // 比较左孩子和父结点大小，再用其中较大者与右孩子比较 
    if(left <= heapsize-1 && a[i] < a[left])
    {
        largest = left;
    }
    else
    {
        largest = i;
    }
    if(right <= heapsize-1 && a[largest] < a[right])
    {
        largest = right;
    }
    // 如果最大者不是父结点，将父结点与最大者进行交换
    if(largest != i)
    {
        temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;
        // 交换之后有可能违反最大堆性质，递归调用维护性质
        max_heapify(a, largest, heapsize);
    }
}

// 构建最大堆，通过遍历节点，实现根结点是堆数据中的最大值
void build_max_heap(int a[], int heapsize)
{
    int i, count = 0;
    // 从后到前，对结点进行遍历维护
    for(i=(int)(heapsize/2) - 1; i>=0; i--)
    {
        max_heapify(a, i, heapsize-count);
        count = count + 1;
    } 
}

// 交换函数
void swap(int a[], int i, int j)
{
    int temp;
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

// 构建最大堆之后，根结点处有最大的数，将最大值与最后的数交换取出，再对剩余的 len-1 数据继续重复此操作
void heap_sort(int a[], int heapsize)
{
    int i;
    build_max_heap(a, heapsize);
    for(i = heapsize - 1; i>=1; i--)
    {
        swap(a, 0, i);    // 交换根结点和最后一个数
        max_heapify(a, 0, i);
    }
}

int main(void)
{
    int a[10] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    int i, heapsize;
    heapsize = sizeof(a)/sizeof(a[0]);
    //printf("%d,%d\n",sizeof(a),sizeof(a[0]));
    //printf("%d\n", heapsize);
    heap_sort(a, heapsize);
    //build_max_heap(a);
    for(i=0; i<10; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

参考《算法导论》