c语言 Heap大根堆的实现

文章列表

c语言 Heap大根堆的实现

堆的简单介绍：

堆是一种特殊的树形数据结构，经常被用来实现优先队列。在实现堆的过程中，可以使用数组实现顺序存储。具体原因如下：

1. 顺序表存储方式简单，易于实现。相比较其他数据结构，如链表等，它不需要频繁地进行内存分配和释放，也不需要复杂的指针操作。

2. 访问数组中的元素是一种很快的操作。由于堆是完全二叉树，因此很容易通过数组下标索引找到任何一个节点的值，其中根节点存储在数组的第一个位置。

3. 堆的操作需要非常高效的访问和修改元素的能力，顺序表天然满足这个需求。在顺序表中插入或删除元素的时间复杂度为O(1)，而其他存储方式就不能做到这一点。

4. 顺序表还可以借助计算机缓存特性，充分发挥局部性原理，提高程序运行效率。

总之，使用顺序表来实现堆的主要原因是其简单性和高效性能。

堆的代码注解：

1：使用顺序表创建一个堆：

2：将堆内成员初始化

3：多次用到的数据交换

4：在堆区push一个值，将数据插入尾，再使用Adjustup将尾数据上调

5：Adjustup函数的实现

6：在大根堆中pop数据

可以先将尾巴的数据与根的数据交换位置，再size--去掉头的元素,最后对根节点进行向下调整

将堆中的根数据删除，顺序表不能直接size--挪动数据，因为挪动数据时会打乱树父子关系

这样，我们就能确保y不但小于等于自己的两个子节点，同时还大于上层的节点。这样不断地交换直至所有数据都插入到原来的二叉堆中，就能确保大根堆的正确性。

并且可以减少因插入元素而造成的数据移动次数，提高效率。

7：ajustdown函数，将数据向下调整结构，使得因为pop而将尾数据调整到合适的子位置

8：判断堆中是否有值，没有值返回true，有值返回false

9：返回根节点的值

10：返回数据的个数

堆的源码展示：

#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>

typedef int HPDataType;

typedef struct heap {
   HPDataType* a;
   int size;
   int capicity;
}HP;

//将堆内成员初始化
void InitHP(HP* php) {
   php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
   if (php->a == NULL)
   {
       perror("malloc failed");
       return;
   }
   php->size = 0;
   php->capicity = 4;
}

//交换数据

void Swap(HPDataType* p1, HPDataType* p2) {
   HPDataType t = *p1;
   *p1 = *p2;
   *p2 = t;
}

//大根堆排序
void Adjustup(HPDataType* a, int child) {
   int parent = (child - 1) / 2;
   while (a[child] > a[parent] && child != 0)
   {
       //交换数组中的值
       Swap(&a[child], &a[parent]);
       //改变下标
       child = parent;
       parent= (parent - 1) / 2;
   }
}

//插入数据
void PushHP(HP* php, HPDataType child) {
assert(php);

   //检查内存空间
   if (php->size == php->capicity)
   {
       HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * 2 * php->capicity);
       if (tmp == NULL)
       {
           perror("realloc failed");
       }
       php->a = tmp;
       php->capicity *= 2;
   }
   //插入数据
   php->a[php->size++] = child;
   //大根堆排序
   Adjustup(php->a, php->size - 1);
}

void AdjustDown(HPDataType* a, int size)
{
   int parent = 0;
   //将leftchild当作较大的child
   int child = parent * 2 + 1;
   while (child<size)
   {
       //当leftchild小于rightchild，child++改为右孩子
       if (child + 1 < size && a[child + 1] > a[child])
       {
           ++child;
       }
       //将child与parent下标的值再arr上互换
       Swap(&a[child], &a[parent]);
       parent = child;
       child = parent * 2 + 1;
   }
}

//判断堆是否为空
bool HeapEmpty(HP* php) {
assert(php);
return php->size == 0;
}

//将堆中的根数据删除，顺序表不能直接size--挪动数据，因为挪动数据时会打乱树父子关系
//可以先将尾巴的数据与根的数据交换位置，再size--去掉头的元素,最后对根节点进行向下调整
void PopHP(HP* php) {
   assert(php);
   assert(!HeapEmpty(php));
   //根尾互换
   Swap(&php->a[0], &php->a[php->size - 1]);
   //尾数据的pop
   php->size--;
   //数据向下调整结构
   AdjustDown(php->a, php->size);
}

//返回根节点的值
HPDataType HeapTop(HP* php){
assert(php);
return php->a[0];
}

//返回数据的个数
int heapsize(HP* php) {
assert(php);
return php->size;
}

c语言 Heap大根堆的实现

相关问题

公告