4.堆的实现

4.1堆的结构

由于堆分为大堆和小堆，这里小编给大家展示的的是大堆的实现思路（小堆的实现思路与大堆一致大家可以在理解的基础上根据自己的需要更改）。

由于堆是一棵完全二叉树，所以在存储堆时，我们采用的是顺序存储的方式，所以我们所采用的堆的结构是

typedef int HPDataType;
typedef struct Heap
{
  HPDataType* _a;
  int _size;
  int _capacity;
}Heap;

这里我们和之前采取利用顺序表存储的结构一致，这里我们用_size存储有效数据的个数，_capacity存储顺序表的容量大小，给出一个指针以便我们之后对数组进行动态开展。

4.2 堆的构建

void HeapCreate(Heap* hp)
{
  assert(hp);
  hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
  if (hp->_a == NULL)
  {
  perror("malloc fail");
  return;
  }
  hp->_size = 0;
  hp->_capacity = 4;
}

这里堆的构建，实际上也是对堆进行一个初始化操作，这里我们申请一个初始容量为4的一个数组大小，由于初始化过程中我们并没有在顺序表中存储元素，所以我们需要将_size赋值为0，_capacity赋初始值为4。

4.3 堆的插入

在介绍大堆插入前我需要给大家先讲解一下堆的向上调整算法，这里我们先给出代码然后给大家细细讲解

首先对于堆的向上调整算法我们这里有个前提就是我们这里的结构就是我们之前的结构就是一个堆的结构

原理：堆新增一个数后，要让其继续为堆需要，应将新增数据和该祖先节点进行不断比较，为了保证堆的存在，我们需要适当的将其的位置进行互换

void Adjustup(HPDataType*a,int child)
{
  int parent = (child - 1) / 2;
  while (child > 0)
  {
  if (a[child] > a[parent])
  {
    swop(&a[child], &a[parent]);
    child = parent;
    parent = (child - 1) / 2;
  }
  else
  {
    break;
  }
  }
}

这里还有一个我们需要使用到的交换函数

void swop(HPDataType* p, HPDataType* q)
{
  HPDataType temp;
  temp = *p;
  *p = *q;
  *q = temp;
}

首先我给大家介绍一下原理，这里首先我给大家一个大堆结构

这里80表示的是我们要新插入的节点，利用向上调整第一次我们得到的结果是

那么最后我们得到的是：

根据每一次的调整我们都可以发现这个我们新添加的数如果大于他的父节点就需要和父节点交换位置，直到该符合了堆的定义。

那么这里的代码表示的是

那么对于插入操作我想大家也基本明白了一个大概，这里我们直接看代码

void HeapPush(Heap* hp, HPDataType x)
{
  assert(hp);
  if (hp->_capacity == hp->_size)
  {
  HPDataType* temp = (HPDataType*)realloc(hp->_a,sizeof(HPDataType) * (hp->_capacity) * 2);
  if (temp == NULL)
  {
    perror("realloc fail");
    return;
  }
  hp->_a = temp;
  hp->_capacity =hp->_capacity*2;
  }
  hp->_a[hp->_size] = x;
  hp->_size++;
  Adjustup(hp->_a, hp->_size - 1);
}

和之前的老套路，当顺序表已经满的时候我们需要进行增容操作，然后我们直接将新插入的值放置在_size所表示的位置处即可，新增后也需要我们对_size进行++操作，这里由于数组是从0开始计数的，所以我们新插入的数也在数组中的位置也就是_size-1处。

4.4 堆的删除

对于堆的删除，我们就要使用到向下调整算法，那什么是向下调整算法呢？我们下面看定义

对于向下调整算法这里我们也有一个大前提就是：左右子树必须是一个堆，才能调整。

原理是：从堆顶开始，如果堆顶元素小于或大于（大于或者大于由大堆小堆决定）该孩子，让堆顶和它最大（最小）的孩子互换，一直重复该操作，直到该全部符合了堆的这个结构。

这里我们先看代码

void Adjustdown(HPDataType* a, int size)
{
  int parent=0;
  int child = 2 * parent + 1;
  while (child < size)
  {
  if (child+1<size&&a[child] < a[child+1])
  {
    child++;
  }
  if (a[parent] < a[child])
  {
    swop(&a[parent], &a[child]);
    parent = child;
    child = 2 * parent + 1;
  }
  else
  {
    break;
  }
  }
}

这里我给大家举个例子说明一下

首先堆顶元素的为5，小于该子节点，那么在该左右孩子中我们发现70这个节点是最大的那么，我们就让70这个节点和我们的5进行互换，得到的是：

这里我们继续看到5这个节点，这里和该左右孩子进行比价，发现5是小于该左右孩子的，那么就让5和它最大的孩子进行互换，该最大的孩子节点是30，那么我们得到的是：

这里就可以发现我们得到了一个完整的堆结构。

这里给大家详细解释一下向下调整算法的代码

那么向下调整算法和我们的删除操作又有着什么关系呢？首先我们要判断堆的删除的意义，如果我们只是单纯的删除最后一个元素我们可以发现我们的删除是不具备任何意义的，但是如果我们删除的是堆顶元素，我们就可以让第二大的元素排列到堆顶，那么这和现实意义的排序的一个物品是一样的意思。

那我们这里进行删除操作是，首先我们将堆顶元素和堆的最后一个元素进行互换，然后将堆的最后一个元素进行删除操作，然后利用堆的向下调整算法，将现在这个状态的数据恢复堆这个数据结构的定义即可。

那么下面我们看代码

void HeapPop(Heap* hp)
{
  assert(hp);
  swop(&hp->_a[0], &hp->_a[hp->_size - 1]);
  hp->_size--;
  Adjustdown(hp->_a, hp->_size);
}

首先我们先更换堆顶和堆最后一个元素的值，然后_size--删除最后一个元素，然后我们通过向下调整算法就恢复了我们堆的结构，然后就完成了我们的删除操作。

4.5 取堆顶的数据

HPDataType HeapTop(Heap* hp)
{
  assert(hp);
  return hp->_a[0];
}

4.6 堆的数据个数

int HeapSize(Heap* hp)
{
  assert(hp);
  return hp->_size;
}

4.7 堆的判空

bool HeapEmpty(Heap* hp)
{
  assert(hp);
  return hp->_size == 0;
}

4.8 堆的销毁

void HeapDestory(Heap* hp)
{
  assert(hp);
  free(hp->_a);
  hp->_a = NULL;
  hp->_capacity = 0;
  hp->_size = 0;
}

5. 堆的实现测试

#include"Heap.h"
void text1()
{
  Heap hp;
  HeapCreate(&hp);
  HeapPush(&hp, 1);
  HeapPush(&hp, 2);
  HeapPush(&hp, 134);
  HeapPush(&hp, 123);
  HeapPush(&hp, 12);
  HeapPush(&hp, 14);
  HeapPush(&hp, 23);
  HeapPush(&hp, 21);
  while (!HeapEmpty(&hp))
  {
  printf("%d ", HeapTop(&hp));
  HeapPop(&hp);
  }
  HeapDestory(&hp);
}
int main()
{
  text1();
  return 0;
}

这里大家看输出结果：

这里可以看到我们数据是符合大堆的结构输出的。

总代码：

Heap.h

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* _a;
  int _size;
  int _capacity;
}Heap;
// 大堆的构建
void HeapCreate(Heap* hp);
// 大堆的销毁
void HeapDestory(Heap* hp);
// 大堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 大堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);
Heap.c
#include"Heap.h"
void HeapCreate(Heap* hp)
{
  assert(hp);
  hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
  if (hp->_a == NULL)
  {
  perror("malloc fail");
  return;
  }
  hp->_size = 0;
  hp->_capacity = 4;
}
void swop(HPDataType* p, HPDataType* q)
{
  HPDataType temp;
  temp = *p;
  *p = *q;
  *q = temp;
}
void Adjustup(HPDataType*a,int child)
{
  int parent = (child - 1) / 2;
  while (child > 0)
  {
  if (a[child] > a[parent])
  {
    swop(&a[child], &a[parent]);
    child = parent;
    parent = (child - 1) / 2;
  }
  else
  {
    break;
  }
  }
}
void HeapPush(Heap* hp, HPDataType x)
{
  assert(hp);
  if (hp->_capacity == hp->_size)
  {
  HPDataType* temp = (HPDataType*)realloc(hp->_a,sizeof(HPDataType) * (hp->_capacity) * 2);
  if (temp == NULL)
  {
    perror("realloc fail");
    return;
  }
  hp->_a = temp;
  hp->_capacity =hp->_capacity*2;
  }
  hp->_a[hp->_size] = x;
  hp->_size++;
  Adjustup(hp->_a, hp->_size - 1);
}
void Adjustdown(HPDataType* a, int size)
{
  int parent=0;
  int child = 2 * parent + 1;
  while (child < size)
  {
  if (child+1<size&&a[child] < a[child+1])
  {
    child++;
  }
  if (a[parent] < a[child])
  {
    swop(&a[parent], &a[child]);
    parent = child;
    child = 2 * parent + 1;
  }
  else
  {
    break;
  }
  }
}
void HeapPop(Heap* hp)
{
  assert(hp);
  swop(&hp->_a[0], &hp->_a[hp->_size - 1]);
  hp->_size--;
  Adjustdown(hp->_a, hp->_size);
}
HPDataType HeapTop(Heap* hp)
{
  assert(hp);
  return hp->_a[0];
}
int HeapSize(Heap* hp)
{
  assert(hp);
  return hp->_size;
}
bool HeapEmpty(Heap* hp)
{
  assert(hp);
  return hp->_size == 0;
}
void HeapDestory(Heap* hp)
{
  assert(hp);
  free(hp->_a);
  hp->_a = NULL;
  hp->_capacity = 0;
  hp->_size = 0;
}

数据结构之堆的介绍（二）