C语言大顶堆

时间:2022-09-28 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;
}

加载全部内容