堆排序

文章中部分内容和思路来自《数据结构、算法与应用 c++语言描述》

接续上一篇文章《堆》:http://blog.****.net/superyang_/article/details/79235370

定义

先用n个元素初始化一个大根/小根堆，然后逐个从堆中提取提取元素并输出。

示意图

假设需要排序的n个元素已构成大根堆，以下图为例：

排序大致过程如下：

代码实现

// 排序后输出

template<typename T>

void MaxHeap<T>::sortPrint()

{

    T *arr = new T[_size];

    int arrSize = _size;

    for (int i = _size - 1; i >= 0; i--)

    {

        T value = top();

        pop();

        arr[i] = value;

    }

    for (int i = 0; i < arrSize; i++)

    {

        qDebug() << arr[i];

    }

    delete []arr;

    arr = NULL;

}

与其他排序的比较

感觉文字定义不太好理解的，可以看看这篇文章http://blog.****.net/u013068377/article/details/39368029