亲宝软件园·资讯

展开

C语言大顶堆

MT_125 人气:0

堆的实现

1.堆结构

逻辑结构上类似于 一棵 “树”

2.堆的种类

大顶堆结构: 一种特殊的树:其每个子节点均比母节点要小

小顶堆结构: 同理:其每个子节点均比母节点要大

结构图示:

3.大顶堆代码实现

这里实现堆 用循序表的方式

①初始化:

typedef int Heaptype;
 
typedef struct Heap
{
    Heaptype* head;   
    int size;         //记录堆总容量 
    int capacity;     //记录当前数据总个数
}Heap;
 
//堆的初始化
void Heap_Init(Heap* pphead)
{
    assert(pphead);
    pphead->head = NULL;
    pphead->size = 0;
    pphead->capacity = 0;
}

②插入数据:

实现细节:数据在插入的同时,要进行数据结构的调整,使树顶始终保持最大数

如果新插入节点比母节点大的话,要进行交换 ,因此将这个调整结构的环节独立出来

即:“向上调整”。

 向上调整:因为插入数据时:新数据默认储存在顺序表尾,因此其逻辑上是在堆的底部,

所以,当新数据比母节点大时,它将与逻辑上处于其上方的母节点交换,称为

向上调整。

注:向上调整有时不止调整一次 ,还有可能调整多次,直到每个节点都在其相应位置 。

流程图解:

大顶堆插入流程

细节点:因为数据是以顺序表的方式储存,所以子节点的下标与母节点的下标符合

公式:parent = (child - 1)/2 ;(按照此公式带入计算就理解了) 

//向上调整
void adjust_up(Heap* pphead)
{
    int child = pphead->capacity;
    int parent = (child - 1) / 2;
    for (; pphead->head[parent] < pphead->head[child];)//判断是否符合大顶堆
    {
        swap(&(pphead->head[parent]),&(pphead->head[child]));//进行交换
        child = parent;
        parent = (child - 1) / 2;
    }
}
 
//插入数据
void Heap_push(Heap* pphead, Heaptype data)
{
    assert(pphead);
    //判断是否满容量并扩容
    Heap_realloc(pphead);
    pphead->head[pphead->capacity] = data;
    //向上调整
    adjust_up(pphead);
    pphead->capacity++;
}

③删除数据:为了避免因为直接删除头部数据导致整个堆的结构打乱,

这里先将头部数据与尾数据交换,然后将尾部数据删除,接着使用“向下调整”,即:将换上来的顶部数据向下与其子节点比较调整,直至符合大顶堆结构为止。

注:1.大顶堆向下调整时,母节点要与两个子节点中较大的一个交换 ,因此要比较一下。

2.这里下标的计算公式为:左孩子:child = (parent * 2) + 1

右孩子:child = (parent * 2) + 2

3.计算孩子下标时要避免越界,避免将母节点与不属于堆中的数据比较。

//删除数据
void Heap_pop(Heap* pphead)
{
    assert(pphead);
    assert(pphead->capacity > 0);      //防止堆为空
    //将顶部数据与尾部数据交换
    swap(&(pphead->head[0]),&( pphead->head[pphead->capacity-1]));
    pphead->capacity--;
    //向下调整
    adjust_down(pphead,0);
}
 
//向下调整
void Adjust_down(int* a, int size, int parent)
{
    assert(a);
    for (int child = parent * 2 + 1; child <= size; child = parent * 2 + 1)
    {
        //默认用左孩纸与母节点比较,如果右孩纸比左孩纸大且不越界则交换
        if (a[child] > a[child + 1] && child + 1 <= size)
            child = child + 1;
        //比较孩纸和母节点
        if (a[child] < a[parent])
        {
            int temp = a[child];
            a[child] = a[parent];
            a[parent] = temp;
        }
        //向下继续比较
        parent = child;
    }
}

④扩容 || 判空 || 取顶数据 || 销毁堆

//判断是否扩容
void Heap_realloc(Heap* pphead)
{
    assert(pphead);
    if (pphead->size == pphead->capacity)
    {
        Heaptype Newsize = (pphead->size == 0) ? 4 : (pphead->size * 2);
        Heaptype* Newhead = (Heaptype*)realloc(pphead->head,sizeof(Heaptype) * Newsize);
        if (Newhead == NULL)
        {
            perror("realloc");
            exit(-1);
        }
        pphead->head = Newhead;
        pphead->size = Newsize;
    }
}
 
//判断堆是否为空
bool Heap_Empty(Heap* pphead)
{
    if (pphead->capacity)
        return false;
    return true;
}
//取对顶数据
Heaptype Heap_top(Heap* pphead)
{
    return pphead->head[0];
}
//销毁堆
void Heap_Destory(Heap* pphead)
{
    assert(pphead);
    free(pphead->head);
    pphead->head = NULL;
    pphead->size = 0;
    pphead->capacity = 0;
}

加载全部内容

相关教程
猜你喜欢
用户评论