文章

25

粉丝

364

获赞

8

访问

206.8k

头像
合并果子(C)
P1544 中南大学机试题
发布于2021年1月28日 18:40
阅读数 8.4k

建立小顶堆,每次取出两个合并在放入堆中,直到合并成为一个

#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 ...
登录查看完整内容


登录后发布评论

1 条评论
snake
2024年4月2日 15:46

yes

赞(0)