算法踩坑3-堆排序

背景

接上面两篇文章
算法踩坑-快速排序
 算法踩坑2-插入排序

来继续聊聊最近我写的一些算法的小例程，这次要聊的是堆排序，是一个时间复杂度为NLogN的算法。

主要从以下几方面来说的：

堆排序思想
堆排序实现
堆排序优化

堆排序思想

堆排序是基于优先队列的最大堆或者是最小堆实现的，每次删除最大堆的顶部元素，然后通过LogN的时间来恢复最大堆的属性，循环这个步骤，最终得到一个有序的序列来达到排序的目的。

堆排序实现

堆的初始化

PriorityQueue PQ_Initialize(int MaxElements) {
    PriorityQueue H = NULL;
    if (MaxElements < MinPQSize) {
        err(1, "队列长度小于最小值10");
    }
    H = malloc(sizeof(struct HeapStruct));
    if (NULL == H) {
        err(1, "Out of space");
    }
    H->Elements = malloc((MaxElements + 1) * sizeof(ElementType));
    if (NULL == H->Elements) {
        err(1, "Out of space");
    }
    H->Capacity = MaxElements;
    H->Size = 0;
    H->Elements[0] = MinData;
    return H;
}

堆的插入

void PQ_InsertToMinQueue(ElementType x,PriorityQueue H) {
    if (PQ_IsFull(H)) {
        err(1, "队列满，不可插入数据");
    }
    // 最小堆，上虑操作
    int i;
    for (i = ++H->Size; H->Elements[i/2] > x; i /= 2) {
        H->Elements[i] = H->Elements[i/2];
    }
    H->Elements[i] = x;
}

堆的删除

ElementType PQ_DeleteMin(PriorityQueue H) {
    if (PQ_IsEmpty(H)) {
        err(1, "Empty");
    }

    ElementType MinElem = H->Elements[1];
    
    // 最小堆，最后一个元素放在顶部，下虑操作
    ElementType lastElement = H->Elements[H->Size--];
    
    int i;
    int child;
    for (i = 1; i * 2<=H->Size; i=child) {
        // 找到孩子节点中小的往上移动
        child = i * 2;
        if (child+1 <= H->Size && H->Elements[child+1] < H->Elements[child] ) {
            child += 1;
        }
        if (child <= H->Size && H->Elements[child] < lastElement) {
            H->Elements[i] = H->Elements[child];
        } else {
            break;
        }
    }
    
    // 放到指定位置
    H->Elements[i] = lastElement;
    
    // 最小元素放在最后，
    // 使用堆排序的时候不用增加额外的空间保存排序后的数据，排序后的数据是倒叙的
    H->Elements[H->Size+1] = MinElem;
    
    return MinElem;
}

堆排序优化

使用一般的方式进行堆排序，需要额外的增加O(N)的内存开销，在删除顶部元素，并且把最后一个元素归为的时候，最后一个位置刚好是空出来的，所以可以把删除的元素放入最后的位置就不需要增加O(N)的内存开销，达到了空间优化的目的。


    // 放到指定位置
    H->Elements[i] = lastElement;

    // 最小元素放在最后，
    // 使用堆排序的时候不用增加额外的空间保存排序后的数据，排序后的数据是倒叙的
    H->Elements[H->Size+1] = MinElem;

One More Thing

噢！我是算法，点我