数据结构——堆-阿里云开发者社区

一、概念

1.定义

堆：堆在逻辑结构上可以看作一棵完全二叉树，并且任意结点比它的左、右孩子大（小），称为大（小）堆，或者大（小）根堆；根节点称为堆顶；每条路径一定是升序或者降序。

逻辑结构与存储结构：

2.堆的实现思路

2.1堆的创建

在给定的一个数组，在逻辑上看作一棵完全二叉树，我们可以通过从根结点开始向下调整算法把它调整成为一个堆，但利用向下调整算法有一个前提，那就是左右子树必须是一个堆，才能利用此算法进行调整。

结合二叉树的性质，我们可以通过从二叉树的倒数第一个非叶子结点的子树开始调整，一直调整到根结点的树，这样就可以把完全二叉树调整为一个堆了

2.2堆的插入

结合堆的创建与调整思想，堆的插入可以通过插入到数组的末尾，即完全二叉树的末尾，然后采用向上调整算法，直至完全二叉树满足堆的定义。

2.3堆的删除

删除堆是删除堆顶的数据，但我们若直接删除堆顶，那么堆就缺失了堆顶，完全二叉树没有了根结点，即该结构不再满足堆的定义。

正确的删除方法是，将堆顶元素与最后一个元素进行对换，然后删除最后一个元素，这样就完成了堆的删除操作，但是对换之后，堆顶可能不再满足堆的特性，此时还需要对堆顶进行向下调整，直至恢复成堆。

二、结构体定义

typedef int HPDataType;
typedef int (*PFUNC)(HPDataType left, HPDataType right);
typedef struct Heap
{
  HPDataType* array;
  int size;//有效元素个数
  int capacity;//容量
  PFUNC pCompare;//大根堆or小根堆 回调函数
}Heap;

这里为了方便我们建立不同的堆，在结构体中增加了一个回调函数，具体实现原理在后续代码中。

三、接口实现

void HeapCreate(Heap* hp, HPDataType* array, int length, PFUNC pCompare);// 堆的构建
int Min(HPDataType right, HPDataType left);//创小根堆回调函数
int Max(HPDataType right, HPDataType left);//创大根堆回调函数
void AdjustDown_Heap(Heap* hp, int parent);//堆调整函数
void Swap(HPDataType* parent, HPDataType* child);//将结点与较大或较小的孩子进行交换
void HeapCheckCapacity(Heap* hp); //判满 & 扩容
int HeapEmpty(Heap* hp);// 堆的判空
void HeapPush(Heap* hp, HPDataType x);// 堆的插入
void HeapErase(Heap* hp);// 堆的删除
HPDataType HeapTop(Heap* hp);// 取堆顶的数据
int HeapSize(Heap* hp);// 堆的数据个数
void HeapDestroy(Heap* hp);// 堆的销毁
void print_Heap(Heap* hp);//打印函数
void Test_Heap();//测试函数

1.堆的构建

void HeapCreate(Heap* hp, HPDataType* array, int length, PFUNC pCompare) {// 堆的构建
  assert(hp);
  hp->array = (HPDataType*)malloc(sizeof(HPDataType) * length);
  if (hp->array == NULL) {//申请失败
  assert(0);
  return;
  }
  hp->capacity = length;
  memcpy(hp->array, array, sizeof(HPDataType) * length);//将数组内元素拷贝到堆中
  hp->size = length;
  hp->pCompare = pCompare;
  for (int root = ((hp->size - 1) - 1) / 2; root >= 0; root--) {//对堆进行调整
  AdjustDown_Heap(hp, root);//堆调整函数
  }
}

结合完全二叉树的特性，最后一个结点的双亲即倒数第一个非叶子结点；结点n的双亲结点等于(n-1)/2，因为size为堆的大小，所以其最后一个叶子结点的下标为size-1，所以代码中有两个减一操作。

然后通过向下调整算法从倒数第一个非叶子结点往回调整。

1.1向下调整函数

void AdjustDown_Heap(Heap* hp,int parent) {//堆调整函数
  int child = parent * 2 + 1;//parent可能只有左没有右，所以标记左孩子
  int size = hp->size;
  while (child < size) {
  if (child + 1 < size && hp->pCompare(hp->array[child + 1], hp->array[child])) {//找parent较小的孩子
    child += 1;
  }
  //检测当前结点即孩子是否满足堆的特性
  if (hp->pCompare(hp->array[child], hp->array[parent])) {//较小（较大）孩子比结点小（大），交换两个结点
    Swap(&hp->array[parent], &hp->array[child]);
    parent = child;//交换后子树可能不满足小（大）堆，继续往下标记判断
    child = parent * 2 + 1;
  }
  else {//当前结点满足堆特性，不需要继续向下调整
    return;
  }
  }
}

因为，双亲结点可能没有有孩子，所以我们标记双亲结点的左孩子，通过找出并标记较小（创小堆Min）或较大（创大堆Max）的孩子，再与根结点进行比较，判断当前结点是否需要调整。

2.堆的判满与扩容

void HeapCheckCapacity(Heap* hp) {//判满&扩容
  assert(hp);
  if (hp->size == hp->capacity) {
  int newCapacity = hp->capacity * 2;//扩大为原容量两倍
  HPDataType* temp = (HPDataType*)malloc(sizeof(HPDataType) * newCapacity);
  if (temp == NULL) {//申请失败
    assert(0);
    return;
  }
  memcpy(temp, hp->array, sizeof(HPDataType) * hp->size);//将数据拷贝到新空间中
  free(hp->array);
  hp->array = temp;
  hp->capacity = newCapacity;
  }
}

3.堆的插入

void HeapPush(Heap* hp, HPDataType x) {// 堆的插入
  assert(hp);
  HeapCheckCapacity(hp);//判满&自动扩容
  hp->array[hp->size] = x;//插入到堆的末尾
  hp->size++;
  AdjustUp_Heap(hp, hp->size - 1);//插入后需向上调整
}

将元素插入到末尾，采用向上调整算法进行调整至堆。

3.1向上调整函数

void AdjustUp_Heap(Heap* hp, int child) {//向上调整函数
  int parent = (child - 1) / 2;//标记该结点的双亲结点
  while (child) {
  if (hp->pCompare(hp->array[child], hp->array[parent])) {//该结点比双亲结点小（大）
    Swap(&hp->array[parent], &hp->array[child]);//较小的往上交换
    child = parent;//标记双亲结点为新的child结点，继续向上调整
    parent = (child - 1) / 2;
  }
  else {//该节点满足堆的特性，不需要进行调整
    return;
  }
  }
}

原理与向下调整算法相同。

4.堆的判空

int HeapEmpty(Heap* hp) {// 堆的判空
  assert(hp);
  return hp->size == 0;//空返回1，非空返回0
}

5.堆的删除

void HeapErase(Heap* hp) {// 堆的删除(删除堆顶）
  assert(hp);
  if (HeapEmpty(hp)) {//判空
  return;
  }
  Swap(&hp->array[0], &hp->array[hp->size - 1]);//先交换堆顶与堆尾元素
  hp->size--;//堆内有效元素个数减一
  AdjustDown_Heap(hp, 0);//堆顶向下调整
}

（1）交换堆顶与末尾元素；（2）删除末尾元素；（3）堆根结点进行向下调整。

6.取堆顶元素

HPDataType HeapTop(Heap* hp) {// 取堆顶的数据
  assert(hp);
  return hp->array[0];
}

7.返回堆有效元素个数

int HeapSize(Heap* hp) {// 堆的数据个数
  assert(hp);
  return hp->size;
}

8.堆销毁

void HeapDestroy(Heap* hp) {// 堆的销毁
  assert(hp);
  if (hp->array) {
  free(hp->array);
  hp->array = NULL;
  hp->capacity = 0;
  hp->size = 0;
  }
}

（1）释放数组空间；（2）置零容量与有效元素个数。

四、接口测试

1.测试函数

void Test_Heap() {
  int array[] = { 49, 27, 37, 65, 28, 34, 25, 15, 18, 19 };
  Heap hp;
  HeapCreate(&hp, array, sizeof(array) / sizeof(array[0]), Max);//创建小根堆
  print_Heap(&hp);
  printf("top = %d\n", HeapTop(&hp));
  printf("size = %d\n", HeapSize(&hp));
  HeapPush(&hp, 10);//插入10
  printf("top = %d\n", HeapTop(&hp));
  printf("size = %d\n", HeapSize(&hp));
  HeapErase(&hp);
  printf("top = %d\n", HeapTop(&hp));
  printf("size = %d\n", HeapSize(&hp));
  print_Heap(&hp);
  HeapDestroy(&hp);//销毁
}

2.测试结果

2.1建大堆：

2.2建小堆（实参Max改为Min)

五、完整代码

#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include<string.h>
typedef int HPDataType;
typedef int (*PFUNC)(HPDataType left, HPDataType right);
typedef struct Heap
{
  HPDataType* array;
  int size;//有效元素个数
  int capacity;//容量
  PFUNC pCompare;//大根堆or小根堆 回调函数
}Heap;
void HeapCreate(Heap* hp, HPDataType* array, int length, PFUNC pCompare);// 堆的构建
int Min(HPDataType right, HPDataType left);//创小根堆回调函数
int Max(HPDataType right, HPDataType left);//创大根堆回调函数
void AdjustDown_Heap(Heap* hp, int parent);//堆调整函数
void Swap(HPDataType* parent, HPDataType* child);//将结点与较大或较小的孩子进行交换
void HeapCheckCapacity(Heap* hp); //判满 & 扩容
int HeapEmpty(Heap* hp);// 堆的判空
void HeapPush(Heap* hp, HPDataType x);// 堆的插入
void HeapErase(Heap* hp);// 堆的删除
HPDataType HeapTop(Heap* hp);// 取堆顶的数据
int HeapSize(Heap* hp);// 堆的数据个数
void HeapDestroy(Heap* hp);// 堆的销毁
void print_Heap(Heap* hp);//打印函数
void Test_Heap();//测试函数
int main() {
  Test_Heap();
  return 0;
}
void print_Heap(Heap* hp) {//打印函数
  printf("-----------------------------\n");
  for (int i = 0; i < hp->size; i++) {
  printf("%d ", hp->array[i]);
  }
  printf("\n-----------------------------\n");
}
void Test_Heap() {
  int array[] = { 49, 27, 37, 65, 28, 34, 25, 15, 18, 19 };
  Heap hp;
  HeapCreate(&hp, array, sizeof(array) / sizeof(array[0]), Min);//创建小根堆
  print_Heap(&hp);
  printf("top = %d\n", HeapTop(&hp));
  printf("size = %d\n", HeapSize(&hp));
  HeapPush(&hp, 10);//插入10
  printf("top = %d\n", HeapTop(&hp));
  printf("size = %d\n", HeapSize(&hp));
  HeapErase(&hp);
  printf("top = %d\n", HeapTop(&hp));
  printf("size = %d\n", HeapSize(&hp));
  print_Heap(&hp);
  HeapDestroy(&hp);//销毁
}
void Swap(HPDataType* parent, HPDataType* child) {//将结点与较大或较小的孩子进行交换
  HPDataType temp = *parent;
  *parent = *child;
  *child = temp;
}
int Min(HPDataType right, HPDataType left) {//创小根堆回调函数
  return right < left;
}
int Max(HPDataType right, HPDataType left) {//创大根堆回调函数
  return right > left;
}
void HeapCreate(Heap* hp, HPDataType* array, int length, PFUNC pCompare) {// 堆的构建
  assert(hp);
  hp->array = (HPDataType*)malloc(sizeof(HPDataType) * length);
  if (hp->array == NULL) {//申请失败
  assert(0);
  return;
  }
  hp->capacity = length;
  memcpy(hp->array, array, sizeof(HPDataType) * length);//将数组内元素拷贝到堆中
  hp->size = length;
  hp->pCompare = pCompare;
  for (int root = ((hp->size - 1) - 1) / 2; root >= 0; root--) {//对堆进行调整
  AdjustDown_Heap(hp, root);//堆调整函数
  }
}
void AdjustDown_Heap(Heap* hp,int parent) {//堆向下调整函数
  int child = parent * 2 + 1;//parent可能只有左没有右，所以标记左孩子
  int size = hp->size;
  while (child < size) {
  if (child + 1 < size && hp->pCompare(hp->array[child + 1], hp->array[child])) {//找parent较小的孩子
    child += 1;
  }
  //检测当前结点即孩子是否满足堆的特性
  if (hp->pCompare(hp->array[child], hp->array[parent])) {//较小（较大）孩子比结点小（大），交换两个结点
    Swap(&hp->array[parent], &hp->array[child]);
    parent = child;//交换后子树可能不满足小（大）堆，继续往下标记判断
    child = parent * 2 + 1;
  }
  else {//当前结点满足堆特性，不需要继续向下调整
    return;
  }
  }
}
void AdjustUp_Heap(Heap* hp, int child) {//向上调整函数
  int parent = (child - 1) / 2;//标记该结点的双亲结点
  while (child) {
  if (hp->pCompare(hp->array[child], hp->array[parent])) {//该结点比双亲结点小（大）
    Swap(&hp->array[parent], &hp->array[child]);//较小的往上交换
    child = parent;//标记双亲结点为新的child结点，继续向上调整
    parent = (child - 1) / 2;
  }
  else {//该节点满足堆的特性，不需要进行调整
    return;
  }
  }
}
void HeapCheckCapacity(Heap* hp) {//判满&扩容
  assert(hp);
  if (hp->size == hp->capacity) {
  int newCapacity = hp->capacity * 2;//扩大为原容量两倍
  HPDataType* temp = (HPDataType*)malloc(sizeof(HPDataType) * newCapacity);
  if (temp == NULL) {//申请失败
    assert(0);
    return;
  }
  memcpy(temp, hp->array, sizeof(HPDataType) * hp->size);//将数据拷贝到新空间中
  free(hp->array);
  hp->array = temp;
  hp->capacity = newCapacity;
  }
}
void HeapPush(Heap* hp, HPDataType x) {// 堆的插入
  assert(hp);
  HeapCheckCapacity(hp);//判满&自动扩容
  hp->array[hp->size] = x;//插入到堆的末尾
  hp->size++;
  AdjustUp_Heap(hp, hp->size - 1);//插入后需向上调整
}
void HeapErase(Heap* hp) {// 堆的删除(删除堆顶）
  assert(hp);
  if (HeapEmpty(hp)) {//判空
  return;
  }
  Swap(&hp->array[0], &hp->array[hp->size - 1]);//先交换堆顶与堆尾元素
  hp->size--;//堆内有效元素个数减一
  AdjustDown_Heap(hp, 0);//堆顶向下调整
}
HPDataType HeapTop(Heap* hp) {// 取堆顶的数据
  assert(hp);
  return hp->array[0];
}
int HeapSize(Heap* hp) {// 堆的数据个数
  assert(hp);
  return hp->size;
}
int HeapEmpty(Heap* hp) {// 堆的判空
  assert(hp);
  return hp->size == 0;//空返回1，非空返回0
}
void HeapDestroy(Heap* hp) {// 堆的销毁
  assert(hp);
  if (hp->array) {
  free(hp->array);
  hp->array = NULL;
  hp->capacity = 0;
  hp->size = 0;
  }
}

数据结构——堆

一、概念

1.定义

2.堆的实现思路

二、结构体定义

三、接口实现

1.堆的构建

1.1向下调整函数

2.堆的判满与扩容

3.堆的插入

4.堆的判空

5.堆的删除

6.取堆顶元素

7.返回堆有效元素个数

8.堆销毁

四、接口测试

1.测试函数

2.测试结果

五、完整代码

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构——堆

一、概念

1.定义

2.堆的实现思路

二、结构体定义

三、接口实现

1.堆的构建

1.1向下调整函数

2.堆的判满与扩容

3.堆的插入

4.堆的判空

5.堆的删除

6.取堆顶元素

7.返回堆有效元素个数

8.堆销毁

四、接口测试

1.测试函数

2.测试结果

五、完整代码

热门文章

最新文章

相关课程

相关电子书