堆排序优化思路

Oct 15, 2019 4 min read 研究

堆排序其实是最不好优化的一个，在数据结构都确定的情况下，优化空间太小，除非优化数据结构本身，但那样就不叫做堆排序了。类似堆排序的还有smooth sort和weakheap sort，有兴趣可以自己查找相关资料。

堆排序原理

堆排序其实是选择排序的优化变种，选择排序是把最大或最小的元素放到最边上，然后不断重复以上过程，堆排序也是如此，只不过堆排序通过构建数据结构，让查找最大或最小元素并放到最边上的速度比选择排序快得多。

首先我们先来介绍什么是堆。堆只是个缩写，全名是二叉堆，是一种完全二叉树，它的特点是二叉堆的父节点元素不小于子节点的元素，以下为二叉堆例图

graph TD;
30-->29
30-->28
29-->24
29-->25
28-->26
28-->22
24-->21

根节点是最大值的时候，就叫做最大堆，反之叫做最小堆。之所以使用完全二叉堆，是为了它能直接放到数组里，例如上图放数组里的结果是：

下标	0	1	2	3	4	5	6	7
值	30	29	28	24	25	26	22	21

可以看出，就是按层序遍历的结果。这样表示的好处是，可以通过下标的简单运算得到子节点的下标，我们通过简单找规律就能发现，下标k的子节点是2k+1和2k+2，所以我们能直接在数组里组织一个二叉堆。而且堆的根节点就是最值，找最值的时间复杂度是O(1)

那么假如堆结构已经组织好了，我们接下来看怎么排序，还是以刚刚的数组作为例子，下标0就是最大值，那么我们就把它拿出来，与最右边元素交换，得到

下标	0	1	2	3	4	5	6	7
值	21	29	28	24	25	26	22	30
指针	r	a	b

下标7的是已经排好的，后面不管它。这时候堆的性质破坏了，我们要去修正，指针r的子结点分别是a和b，在r,a,b中找出最大的元素a与r交换，得到

下标	0	1	2	3	4	5	6
值	29	21	28	24	25	26	22
指针		r		a	b

再继续操作

下标	0	1	2	3	4	5	6
值	29	25	28	24	21	26	22
指针					r

这时候，指针r已经没有子结点，这时候堆就修正好了。这个过程由于是从根向叶子的操作，叫做shiftdown，还有一种相反的过程叫做shiftup，就是从叶子向根的方向操作。以上就是一轮完整的操作，包括交换最值，修正堆两步。不断循环以上操作直到所有元素有序即可。

排序方法说完了，我们回头来说怎么构建堆。用shiftup法描述起来比较简单，一开始，只看下标0，那一个元素就肯定是堆。然后添加一个元素在最末，然后shiftup，修改新添加的元素，如此循环。伪代码如下

makeheap(arr, len)
    for i in (1, len)
        shiftup(arr, i)

而使用shiftdown的话，原理一样，只是换一个方向

makeheap(arr, len)
    for i in (len / 2, 1)
        shiftdown(arr, i)

以下为完整动态图演示

堆排序基本实现

以下shiftdown实现的函数名是max_heapify

void max_heapify(sort_element_t arr[], size_t index, size_t length)
{
    size_t child;
    sort_element_t temp = arr[index];
    for (; (child = 2 * index + 1) < length; index = child)
    {
        if (child + 1 < length && arr[child] < arr[child + 1])
            ++child;
        if (temp < arr[child])
            arr[index] = arr[child];
        else
            break;
    }
    arr[index] = temp;
}

void heap_sort(sort_element_t arr[], size_t length)
{
    if (length > 1)
    {
        for (size_t i = length / 2; i-- > 0; )
            max_heapify(arr, i, length);
        for (size_t i = length - 1; i > 0; --i)
        {
            sort_element_swap(&arr[0], &arr[i]);
            max_heapify(arr, 0, i);
        }
    }
}

void heap_sort(sort_element_t* beg, sort_element_t* end)
{
    heap_sort(beg, end - beg);
}