堆

最新推荐文章于 2022-01-17 09:23:12 发布

菜小白—NLP

最新推荐文章于 2022-01-17 09:23:12 发布

阅读量287

点赞数

分类专栏： ACM

本文链接：https://blog.csdn.net/ACM_hades/article/details/79030388

版权

ACM 专栏收录该内容

22 篇文章

订阅专栏

本文介绍了一种基于数组实现的大顶堆数据结构，并详细解释了如何通过具体算法进行堆的构建、元素的插入（压堆）及删除（弹堆）等核心操作。通过向上调整(up_adjust)和向下调整(down_adjust)确保堆的性质得以维持。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include <iostream>
#include <stdio.h>
#define Max 1000
using namespace std;

//大顶堆
int heap[Max];//堆的存放数组

void down_adjust(int x)//将x向下调节
{
    int temp=heap[x];
    int y=2*x;
    while(y<=heap[0])
    {
        if(y+1<=heap[0]&&heap[y]<heap[y+1])//若有右儿子且右儿子比左儿子大则将y指向右儿子
            y++;//y是用来指向两个儿子最大值的
        if(heap[y]<=temp)
            break;//没顺序颠倒时结束
        heap[y/2]=heap[y];
        y=y*2;//继续向下调节
    }
    heap[y/2]=temp;
}

void up_adjust(int x)//将x向上调节
{
    int temp=heap[x];
    int y=x;
    while(y/2>=1)
    {
        if(heap[y/2]>=temp)//没有顺序颠倒是直接颠倒
            break;
        heap[y]=heap[y/2];
        y=y/2;
    }
    heap[y]=temp;
}

void init()//建堆
{
    for(int i=heap[0]/2; i>=1; i--)
        down_adjust(i);
}

int pop()//弹堆
{
    int temp=heap[1];
    heap[1]=heap[heap[0]];
    heap[0]--;
    down_adjust(1);
    return temp;
}

void push(int x)//将x压入堆内
{
    heap[0]++;
    heap[heap[0]]=x;
    up_adjust(heap[0]);
}