基于数组的堆排序(一)

时间：2010-11-18 来源：xiayongchun

基于数组的堆排序

(一)什么是堆?

这里的堆不是堆栈的堆,而是一种数据结构,可以视为一棵完全二叉树,既然是

完全二叉树,便可以使用数组存储(不浪费存储的空间,否则应该使用链表存储)。

通常所说的堆,指的是二叉堆。

二叉堆：最大堆和最小堆。

最大堆满足对于某个结点i来讲,Ki>=K2i Ki>=K2i+1也就是父亲永远大于

孩子的原则(这样的话树根就是值最大的结点)

数组是基于0开始的，所以对于结点x来讲，对应的数组中的元素的下标表示如下

   #define LEFT(x)    ((x << 1) + 1)
   #define RIGHT(x)   ((x + 1) << 1)
   #define PARENT(x) (((x + 1) >> 1) - 1)

函数一是

void MaxHeapify(int Ary[], int nIndex, int nHeapSize)
{
    int nL = LEFT(nIndex);
    int nR = RIGHT(nIndex);
    int nLargest;

    if (nL <= nHeapSize && Ary[nIndex] < Ary[nL])
    {
        nLargest = nL;
    }
    else
    {
        nLargest = nIndex;
    }

    if (nR <= nHeapSize && Ary[nLargest] < Ary[nR])
    {
        nLargest = nR;
    }
    if (nLargest != nIndex)
    {
        Swap(Ary[nLargest], Ary[nIndex]);
        MaxHeapify(Ary, nLargest, nHeapSize);
    }
}

上述函数的功能是使nIndex下标满足最大堆的要求,自然的想到如果是整个数组都

满足最大堆的要求的话,则有如下的函数产生

void BuildMaxHeap(int Ary[], int nHeapSize)
{
    for (int i = PARENT(nHeapSize); i >= 0; --i)
    {
      MaxHeapify(Ary, i, nHeapSize);
    }
}

如果想要是一个数组按照顺序排序好的话使用下面的函数

void HeapSort(int Ary[], int nCount)
{
int nHeapSize = nCount - 1;
   BuildMaxHeap(Ary, nHeapSize);
   for (int i = nHeapSize; i >= 1; --i)
{
     Swap(Ary[0], Ary[i]);
    --nHeapSize;
     MaxHeapify(Ary, 0, nHeapSize);
   }
}