堆排序(怎么构造堆,在堆排序过程中的比较方法)

堆排序(如何构造堆,在堆排序过程中的比较方法)
题目:无序序列{59,11,26,34,17,91,25},要用堆排序得到{11,17,25},共执行多少次比较?

我的问题是:如何从无序序列构造堆?
我用的是清华严蔚敏的教材,上面说:'从一个无序序列建堆的过程就是一个反复"筛选"的过程.'
而从书上又可以了解到"筛选"是作用于二叉树的操作,这棵二叉树是从哪来的呢,书上给的例子也是直接就有一棵二叉树,这点我不太理解.如果说这棵二叉树是通过一定的规则构造的,那么我的问题是:如何从一组无序序列构造堆所对应的二叉树呢?

就以上面的无序序列作为例子吧.

[解决办法]
通过建堆算法。
也就是建立你说的“书上给的例子也是直接就有一棵二叉树”的那棵二叉树。这是堆排序的先决条件。只有无序序列已经是堆了，用堆排序算法才可以起到排序的效果。建堆算法应该在前面已经出现了，所以作者才直接给出了无序序列的堆形式（也就是那棵二叉树）。
[解决办法]

C/C++ code

#define PARENT(i)  ((i) / 2)#define LEFT(i)    ((i) * 2)#define RIGHT(i)   ((i) * 2 + 1)#define RELOCAL(i) ((i) - 1)template <class T>void MaxHeapify(T *array,const size_t length,const size_t i){    if (NULL == array || length == 0 || 0 == i || i > length)    {        return;    }    if (LEFT(i) <= length)    {        if(array[RELOCAL(i)] < array[RELOCAL(LEFT(i))])        {            Swap(array[RELOCAL(i)],array[RELOCAL(LEFT(i))]);        }    }    if (RIGHT(i) <= length)    {        if (array[RELOCAL(i)] < array[RELOCAL(RIGHT(i))])        {            Swap(array[RELOCAL(i)],array[RELOCAL(RIGHT(i))]);        }    }    MaxHeapify(array,length,LEFT(i));    MaxHeapify(array,length,RIGHT(i));    return;}template <class T>void BuildMaxHeap(T *array,const size_t length){    if (array == NULL || length <= 1)     {        return;    }    size_t i = length/2;    while (i != 0)    {        MaxHeapify(array,length,i);        --i;    }    return;}template <class T>void HeapSort(T *array,const size_t length){    if (array == NULL || length <= 1)    {        return;    }    BuildMaxHeap(array,length);    size_t  l = length;    while (l != 0)    {        swap(array[0],array[RELOCAL(l)]);        --l;        MaxHeapify(array,l,1);    }    return;}
[解决办法]
debug.h
C/C++ code
class OutOfBounds{};
[解决办法]
建堆思想：
首先将无序序列一次作为一个完全二叉树存储，也就是你上面的例子中59作为根，依次11，26作为孩子节点等等延续。
然后从第n/2个节点开始，一直到第一个节点59，进行堆的调整，这个过程叫建堆。

如果是大根堆，那么第一个元素就是最大的节点，取出最大节点和最后一个节点元素交换，然后堆的大小相应减1，然后从根开始调整堆！！