仿STL中的堆算法的一个实现

RT。

堆的性质之类的不再这里阐述，写这个算法只为了更好的理解STL中的堆算法，如果看不懂STL中的算法也可以来参考这里给出的算法，因为是纯C的看起来会省去很多语言方面的细节。

同时里面还有一个STL中对应算法的测试以比较两者的效果。

/********************************************************************    created:    2007/3/18    filename:     main.cpp    author:        Lichuang    purpose:    测试模拟堆算法*********************************************************************/#include <algorithm>#include <iostream>#include <time.h>using namespace std;// push_heap为向堆中添加一个新的元素, 调用这个算法的前提是[First, Last)之间的元素满足堆的条件// 新加入的元素为Lastvoid  push_heap(int* pFirst, int* pLast);// pop_heap为从堆中删除一个元素, 调用这个算法的前提是[First, Last)之间的元素满足堆的条件// 被删除的元素被放置到Last - 1位置,由于这里是max-heap,所以被删除的元素是这个序列中最大的元素void    pop_heap(int* pFirst, int* pLast);// make_heap将序列[First, Last)中的元素按照堆的性质进行重组void    make_heap(int* pFirst, int* pLast);// 对堆进行排序, 调用这个函数可以成功排序的前提是[pFirst, pLast)中的元素符合堆的性质void    sort_heap(int* pFirst, int* pLast);// 判断一个序列[First, Last)是否满足堆的条件,是就返回1,否则返回0char    is_heap(int* pFirst, int* pLast);void    test_heap_algo(int *pArray, int nLength);void    test_heap_algo_in_stl(int *pArray, int nLength);void    display_array(int *pArray, int nLength);int main(){    srand(time(NULL));    int Array[10], Array2[10];    for(int i = 0; i < 10; ++i)        Array[i] = Array2[i] = rand();    test_heap_algo(Array, sizeof(Array) / sizeof(int));    test_heap_algo_in_stl(Array2, sizeof(Array2) / sizeof(int));    return 0;}// 静态函数, 用于根据堆的性质调整堆static void adjust_heap(int *pFirst, int nHoleIndex, int nLen, int nValue);// push_heap为向堆中添加一个新的元素, 调用这个算法的前提是[First, Last)之间的元素满足堆的条件// 新加入的元素为Lastvoid push_heap(int* pFirst, int* pLast){    int nTopIndex, nHoleIndex, nParentIndex;    int nValue;    nTopIndex = 0;    nHoleIndex = (int)(pLast - pFirst - 1);    nParentIndex = (nHoleIndex - 1) / 2;    nValue = *(pLast - 1);    // 如果需要插入的节点值比父节点大, 上溯继续查找    while (nHoleIndex > nTopIndex && pFirst[nParentIndex] < nValue)    {        pFirst[nHoleIndex] = pFirst[nParentIndex];        nHoleIndex = nParentIndex;        nParentIndex = (nHoleIndex - 1) / 2;    }    pFirst[nHoleIndex] = nValue;}// pop_heap为从堆中删除一个元素, 调用这个算法的前提是[First, Last)之间的元素满足堆的条件// 被删除的元素被放置到Last - 1位置,由于这里是max-heap,所以被删除的元素是这个序列中最大的元素void pop_heap(int* pFirst, int* pLast){    int nValue;    nValue = *(pLast - 1);    *(pLast - 1) = *pFirst;    adjust_heap(pFirst, 0, (int)(pLast - pFirst - 1), nValue);}// make_heap将序列[First, Last)中的元素按照堆的性质进行重组void make_heap(int* pFirst, int* pLast){    int nLen, nParentIndex;    nLen = (int)(pLast - pFirst);    nParentIndex = (nLen - 1) / 2;    while (true)     {        // 对父节点进行调整, 把父节点的值调整到合适的位置        adjust_heap(pFirst, nParentIndex, nLen, pFirst[nParentIndex]);        if (0 == nParentIndex)             return;        nParentIndex--;    }}// 对堆进行排序, 调用这个函数可以成功排序的前提是[pFirst, pLast)中的元素符合堆的性质void sort_heap(int* pFirst, int* pLast){    // 调用pop_heap函数, 不断的把当前序列中最大的元素放在序列的最后    while(pLast - pFirst > 1)        pop_heap(pFirst, pLast--);}// 判断一个序列[First, Last)是否满足堆的条件,是就返回1,否则返回0char is_heap(int* pFirst, int* pLast){    int nLen, nParentIndex, nChildIndex;    nLen = (int)(pLast - pFirst);    nParentIndex = 0;    for (nChildIndex = 1; nChildIndex < nLen; ++nChildIndex)    {        if (pFirst[nParentIndex] < pFirst[nChildIndex])            return 0;        // 当nChildIndex是偶数时, 那么父节点已经和它的两个子节点进行过比较了        // 将父节点递增1        if ((nChildIndex & 1) == 0)            ++nParentIndex;    }    return 1;}// 一个静态函数仅供adjust_heap调用以证实JJHOU的结论static void push_heap(int *pFirst, int nHoleIndex, int nTopIndex, int nValue){    int nParentIndex;    nParentIndex = (nHoleIndex - 1) / 2;    while (nHoleIndex > nTopIndex && pFirst[nParentIndex] < nValue)    {        pFirst[nHoleIndex] = pFirst[nParentIndex];        nHoleIndex = nParentIndex;        nParentIndex = (nHoleIndex - 1) / 2;    }    pFirst[nHoleIndex] = nValue;}// 对堆进行调整, 其中nHoleIndex是目前堆中有空洞的节点索引, nLen是待调整的序列长度// nValue是需要安插进入堆中的值static void adjust_heap(int *pFirst, int nHoleIndex, int nLen, int nValue){    int nTopIndex, nSecondChildIndex;    nTopIndex = nHoleIndex;    nSecondChildIndex = 2 * nTopIndex + 2;    while (nSecondChildIndex < nLen)    {        if (pFirst[nSecondChildIndex] < pFirst[nSecondChildIndex - 1])            --nSecondChildIndex;        pFirst[nHoleIndex] = pFirst[nSecondChildIndex];        nHoleIndex = nSecondChildIndex;        nSecondChildIndex = 2 * nHoleIndex + 2;    }    if (nSecondChildIndex == nLen)    {        pFirst[nHoleIndex] = pFirst[nSecondChildIndex - 1];        nHoleIndex = nSecondChildIndex - 1;    }    // 以下两个操作在这个函数中的作用相同, 证实了<<STL源码剖析>>中P178中JJHOU所言    //pFirst[nHoleIndex] = nValue;    push_heap(pFirst, nHoleIndex, nTopIndex, nValue);}void    test_heap_algo(int *pArray, int nLength){    std::cout << "\ntest_heap_algo()\n";    make_heap(pArray, pArray + nLength);    display_array(pArray, nLength);    push_heap(pArray, pArray + nLength);    display_array(pArray, nLength);    pop_heap(pArray, pArray + nLength);    display_array(pArray, nLength);    if (is_heap(pArray, pArray + nLength - 1))    {        std::cout << "is heap!\n";    }    else    {        std::cout << "is not heap!\n";    }    make_heap(pArray, pArray + nLength);    display_array(pArray, nLength);    if (is_heap(pArray, pArray + nLength))    {        std::cout << "is heap!\n";    }    else    {        std::cout << "is not heap!\n";    }    sort_heap(pArray, pArray + nLength);    display_array(pArray, nLength);}void    test_heap_algo_in_stl(int *pArray, int nLength){    std::cout << "\ntest_heap_algo_in_stl()\n";    std::make_heap(pArray, pArray + nLength);    display_array(pArray, nLength);    std::push_heap(pArray, pArray + nLength);    display_array(pArray, nLength);    std::pop_heap(pArray, pArray + nLength);    display_array(pArray, nLength);    // 注意is_heap不是STL中支持的算法, 貌似只有SGI的实现才有这个函数!    if (is_heap(pArray, pArray + nLength - 1))    {        std::cout << "is heap!\n";    }    else    {        std::cout << "is not heap!\n";    }    std::make_heap(pArray, pArray + nLength);    display_array(pArray, nLength);    if (is_heap(pArray, pArray + nLength))    {        std::cout << "is heap!\n";    }    else    {        std::cout << "is not heap!\n";    }    std::sort_heap(pArray, pArray + nLength);    display_array(pArray, nLength);}void    display_array(int *pArray, int nLength){    for (int i = 0; i < nLength; ++i)        std::cout << pArray[i] << " ";    std::cout << std::endl;}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， int
， 元素调用
， 堆
， 堆排序
， heap
， 元素
， 序列
， nlen
堆的操作
stl算法、stl算法库、stl排序算法、stl常用算法、stl查找算法，以便于您获取更多的相关知识。