仿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)之间的元素满意堆的条件
// 新插手的元素为Last
void 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,不然返回0
char 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)之间的元素满意堆的条件
// 新插手的元素为Last
void 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,不然返回0
char 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;
}
