algorithm ch6 heapsort

堆排序利用的是堆这种数据结构来对进行排序，（二叉）堆可以被视为一棵完全的二叉树，树的每个节点与数组中存放该节点的值得那个元素对应。这里使用最大堆进行排序算法设计，最大堆就是parent(i) > leftchild(i) 且parent(i) > rightchild(i)，首先利用迭代法进行建堆。

int left(int index)

{

    return index*+;

}

int right(int index)

{

    return index*+;

}

下面是建堆的函数：

void MaxHeapify(int *a, int node, int iHeapSize)

{

    int iIndexL = left(node);

    int iIndexR = right(node);

    int iLargest = node;

    if(iIndexL < iHeapSize && a[iIndexL] > a[node])

    {

        iLargest = iIndexL;

    }

    else

        iLargest = node;

    if(iIndexR < iHeapSize && a[iIndexR] > a[iLargest])

    {

        iLargest = iIndexR;

    }

    if(iLargest != node)

    {

        swap(a[iLargest], a[node]);

        MaxHeapify(a, iLargest, iHeapSize);

    }

}

void BuildHeap(int *a, int &iHeapSize)

{

    int iSize = iHeapSize;

    for(int iLoop = iSize/-; iLoop != ; --iLoop)

    {

        MaxHeapify(a, iLoop, iHeapSize);

    }

}

以上代码可以建立一个最大堆,在子数组中A[n/2+1 .. n]中的元素都是树的叶子节点，可以看作是只含一个元素的堆，因此只需用BuilHeap对树中的其他节点调用MaxHeapify
来建立最大堆。

接着就是排序，因为最大元素在A[1](为了避免节点计算麻烦，序号从1开始)，可以通过将它与A[n]交换。调用MaxHeapify(a, 1, iHeapSize)来保持最大堆性质，然后重复这个过程，堆的大小由n-1一直降到1.排序部分如下：

void HeapSort(int *a, int heapSize)

{

    if(a == NULL)

    {

        return;

    }

    BuildHeap(a, heapSize);

    for(int i=heapSize-; i>=; i--)

    {

        swap(a, a+i);

        --heapSize;

        MaxHeapify(a, , heapSize);

    }

}

巴特西

algorithm ch6 heapsort

最新文章

热门文章