文章
25
粉丝
364
获赞
8
访问
219.0k
建立小顶堆,每次取出两个合并在放入堆中,直到合并成为一个
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#define max 10001
void BuildHeap(int *h);
void Adjust(int *h, int p);
int GetMin(int *h);
void Add(int *h, int x);
//建立小顶堆
void BuildHeap(int *h)
{
for (int i = h[0] / 2; i > 0; i--)
{
Adjust(h, i);
}
return;
}
//从节点p开始向下调整
void Adjust(int *h, int p)
{
int tmp = h[p], i;
for (i = 2 * p; i <= h[0]; i *= 2)
{
if (i < h[0] && h[i] > h[i + 1]) //选出子节点中的最小者
{
i++;
}
if (tmp > h[i]) //如果两者中的最小者小于tmp,则交换
{
h[i / 2] = h[i];
}
else //否则结束调整
{
break;
}
}
h[i / 2] = tmp;
return;
}
//堆顶数据出堆,并调整小顶堆
int GetMin(int *h)
{
int min = h[1];
h[1] = h[h[0]--]; //将最后一个数据放置堆顶
Adjust(h, 1);
return min;
}
//添加数据入堆
void ...
登录后发布评论