找出m个数中最小的n个数的算法

核心提示：/ created: 2007/3/18 filename: main.cpp author: Lichuang purpose: 测试模拟堆算法*/#include <algorithm>#include <iostream>#include <time.h>using name

/********************************************************************
　　　 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);

// 用于根据堆的性质调整堆, 将nValue放到位置nHoleIndex, 并且保证堆性质的成立
void　　　 adjust_heap(int *pFirst, int nHoleIndex, int nLen, int nValue);

// 得到一个数组中最小的n个元素
void　　　 get_n_min(int *pArray, int nLen, int n);

void　　　 display_array(int *pArray, int nLength);

int main()
{
　　　 srand(time(NULL));
　　　 int Array[10];
　　　 for(int i = 0; i < 10; ++i)
　　　　　　　 Array[i] = rand();

　　　 get_n_min(Array, 10, 2);

　　　 return 0;
}

void get_n_min(int *pArray, int nLen, int n)
{
　　　 int *pTmp = (int*)malloc(sizeof(int) * n);
　　　 if (NULL == pTmp)
　　　 {
　　　　　　　 perror("malloc error");
　　　　　　　 return;
　　　 }

　　　 int i;
　　　 for (i = 0; i < n; ++i)
　　　　　　　 pTmp[i] = pArray[i];
　　　 make_heap(pTmp, pTmp + n);
　　　 display_array(pTmp, n);

　　　 for (; i < nLen; ++i)
　　　 {
　　　　　　　 if (pArray[i] < pTmp[0])
　　　　　　　　　　　　 adjust_heap(pTmp, 0, n, pArray[i]);
　　　 }

　　　 // 最后对堆进行排序
　　　 sort_heap(pTmp, pTmp + n);

　　　 cout << "the min n elements of the array is:n";

　　　 // 打印堆中的数据
　　　 display_array(pTmp, n);

　　　 free(pTmp);
}

// 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是需要安插进入堆中的值
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　　　 display_array(int *pArray, int nLength)
{
　　　 for (int i = 0; i < nLength; ++i)
　　　　　　　 std::cout << pArray[i] << " ";
　　　 std::cout << std::endl;
}