Articles

堆排序(Heap Sort)

堆排序相比插入排序、选择排序、冒泡排序来说要复杂一些。Introduction to Algorithms第6章介绍了堆排序,The Algorithm Design Manual第4.3节介绍了堆排序。这两本书在介绍该算法时,又是分别从两个不同角度介绍的。

Introduction to Algorithms首先介绍如何基于一个已有的数组构造一个大根堆(max heap)或小根堆(min heap),然后再介绍如何使用这个堆进一步将其元素排序。讲完了堆排序,再介绍优先队列(priority queue)。而The Algorithm Design Manual这本书则是先介绍如何通过插入元素,将一个数组转换为堆,然后如何从这个堆中有序的将元素抽取出来并重新保存到数组中。这本书说堆排序算法是in-place排序,可是按照这本书中的做法,其空间复杂度应该是O(n),它将所有元素都临时拷贝了一份,因此并不是in-place的。可是,在这之后该书又提到了一种快速构造堆的方法。该方法正是Introduction to Algorithms这本书一上来就介绍的对的构造方法。所以,似乎这次又是Introduction to Algorithms这本书讲的好一些。

下面是我实现的堆排序的C++代码。

template
class Heap
{
public:
    Heap(T a[], int size)
    : _a(a)
    , _size(size)
    {
    }

public:
    void Sort()
    {
        BuildMaxHeap();
        for (int i = _size - 1; i >= 0; i--)
        {
            swap(_a[0], _a[i]);
            _size--;
            MaxHeapify(0);
        }
    }

private:
    int Left(int node)
    {
        return 2 * node + 1;
    }

    int Right(int node)
    {
        return 2 * (node + 1);
    }

    int Parent(int node)
    {
        return (node - 1) / 2;
    }

    void MaxHeapify(int node)
    {
        int maxNode = node;

        int leftNode = Left(node);
        if ((leftNode < _size) && (_a[leftNode] > _a[maxNode]))
            maxNode = leftNode;

        int rightNode = Right(node);
        if ((rightNode < _size) && (_a[rightNode] > _a[maxNode]))
            maxNode = rightNode;

        if (maxNode != node)
        {
            swap(_a[maxNode], _a[node]);
            MaxHeapify(maxNode);
        }
    }

    void BuildMaxHeap()
    {
        for (int i = (_size - 1) / 2; i >= 0; i--)
            MaxHeapify(i);
    }

private:
    T *_a;
    int _size;
};

上面的代码与这两本书中的代码不同之一是,书中为了计算方便,将数组的索引从1开始,而我仍然是从0开始。关于这一算法,我还有一个疑惑之处:每次排序完堆的大小就是0了,似乎会影响后续的插入等其它需要知道堆大小的操作。

堆排序算法的时间复杂度是\( O(nlgn) \)。有趣的是,构造堆的时间复杂度大致估计是\( O(nlgn) \),但实际上,越往根节点走虽然树越深,但是节点却越少;越往子节点走,节点数量虽然多,但是数缺非常浅。所以,构造堆的时间复杂度其实只有\(O(n)\)。