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

堆排序(如何构造堆,在堆排序过程中的比较方法)
题目:无序序列{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，然后从根开始调整堆！！

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

相关推荐