(67)王道数据结构-堆排序

基本概念

堆排序是一种树形选择排序方法，其特点：在排序过程中，将L[1…n]视为一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的元素

若n个关键字序列L[1…n]满足下面某一种性质，则称为堆(Heap)
①若满足: L(i) ≥ L(2i)且L(i)≥L(2i+1) (1 ≤ i ≤ n/2)-大根堆(大顶堆)
②若满足: L(i) ≤ L(2i)且L(i)≤L(2i+1) (1 ≤ i ≤ n/2)-小根堆(小顶堆)

显然，在大根堆中，最大元素存放在根结点中，且对其任一非根结点，它的值小于等于其双亲结点值。小根堆的定义刚好相反，根结点是最小元素。

堆经常被用来实现优先级队列，优先级队列在操作系统的作业调度和其他领域有广泛的应用

代码逻辑

建立堆栈

1.编号≤n/2的所有结点依次下坠调整(自低向上处理各分支节点)
2.小元素层逐层下坠(与关键字更大的孩子交换)

进行排序

1.将堆顶元素加入有序字队列(堆顶元素与堆低元素交换)
2.堆低元素换到堆顶后，需要进行下坠调整，恢复大根堆的特性
3.上述过程重复n-1趟

具体实现

//建立大根堆
void BuildMaxHeap(ElemType A[], int len) {
    for(int i=len/2; i>0; i--) { //从i=[n/2]~1,反复调整堆
        AdjustDown(A,i,len); //从后往前调整所有非终端结点
    }  
}

//将以k为根的子树调整为大根堆
void AdjustDown(ElemType A[], int k, int len) {
    A[0] = A[k]; //A[0]暂存子树的根结点
    for(i = 2*k; i <= len; i *= 2) { //沿key较大的子结点向下筛选
        if(i < len && A[i] < A[i+1]) {
            i++; //取key较大的子结点的下标
        }
        if(A[0] >= A[i]) {
            break; //筛选结束
        } else {
            A[k]=A[i]; //将A[i]调整到双亲结点上
            k=i; //修改k值，以便继续向下筛选
        }
    }
    A[k]=A[0]; //被筛选结点的值放入最终位置
}

//堆排序的完整逻辑
void HeapSort(ElemType A[], int len) {
    BuildMaxHeap(A, len); //初始建堆
    for(i=len; i>1; i--) { //n-1趟的交换和建堆过程
        Swap(A[i],A[1]); //输出堆顶元素(和堆底元素交换)
        AdjustDown(A,1,i-1); //整理，把剩余的i-1个元素整理成堆
    }
}

性能分析

时间复杂度

建堆时间为O(n)，之后有n-1次向下调整操作，每次调整的时间复杂度为O(h)，排堆的时间复杂度为O(nlog2n)故在最好、最坏和平均情况下，堆排序的时间复杂度为O(nlog2n)

空间复杂度

仅使用了常数个辅助单元，所以空间复杂度为O(1)

稳定性

进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序方法

插入删除

插入操作

1.新元素放到表尾(堆底)
2.根据大/小堆栈的要求，新元素不断“上升”，直到无法继续上升为止

//向上调整堆
void AdjustUp(ElemType A[], int k) {
    //参数k为向上调整的结点，也为堆的元素个数
    A[0]=A[k];
    int i=k/2; //若结点值大于双亲结点，则将双亲结点向下调，并继续向上比较
    while(i>0&&A[i]<A[0]) { //循环跳出条件
        A[k]=A[i]; //双亲结点下调
        k=i; 
        i=k/2; //继续向上比较
    }
    A[k]=A[0]; //复制到最终位置
}

完整代码

typedef int E;
typedef struct MinHeap {
    E * arr;
    int size;
    int capacity;
} * Heap;

_Bool initHeap(Heap heap){
    heap->size = 0;
    heap->capacity = 10;
    heap->arr = malloc(sizeof (E) * heap->capacity);
    return heap->arr != NULL;
}

_Bool insert(Heap heap, E element){
    if(heap->size == heap->capacity) return 0;
    int index = ++heap->size;
    while (index > 1 && element < heap->arr[index / 2]) {
        heap->arr[index] = heap->arr[index / 2];
        index /= 2;
    }
    heap->arr[index] = element;
    return 1;
}

E delete(Heap heap){
    E max = heap->arr[1], e = heap->arr[heap->size--];
    int index = 1;
    while (index * 2 <= heap->size) {
        int child = index * 2;
        if(child < heap->size && heap->arr[child] > heap->arr[child + 1])
            child += 1;
        if(e <= heap->arr[child]) break;
        else heap->arr[index] = heap->arr[child];
        index = child;
    }
    heap->arr[index] = e;
    return max;
}

int main(){
    int arr[] = {3, 5, 7, 2, 9, 0, 6, 1, 8, 4};

    struct MinHeap heap;    //先创建堆
    initHeap(&heap);
    for (int i = 0; i < 10; ++i)
        insert(&heap, arr[i]);   //直接把乱序的数组元素挨个插入
    for (int i = 0; i < 10; ++i)
        arr[i] = delete(&heap);    //然后再一个一个拿出来，就是按顺序的了

    for (int i = 0; i < 10; ++i)
        printf("%d ", arr[i]);
}