初阶数据结构之---二叉树的顺序结构-堆

引言

今天要讲���堆，不是操作系统虚拟进程地址空间中（malloc，realloc等开空间的位置）的那个堆，而是数据结构中的堆，它们虽然名字相同，却是截然不同的两个概念。堆的底层其实是完全二叉树，如果你问我，完全二叉树是什么。好吧，那我先从树开始讲起，开始我们今天的内容。

树是什么？

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有一个特殊的结点，称为根结点，根节点没有前驱结点
• 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1_capacity) {int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("realloc fail:");exit(1);}hp->_a = tmp;hp->_capacity = newcapacity;}hp->_a[hp->_size] = x;hp->_size++; //向上调整算法 AdjustUp(hp->_a, hp->_size - 1);}

  在这里，将新插入的10这个元素往上调整的过程，我们称之为向上调整，涉及到一个算法，那就是向上调整算法，现在我们来实现一份。

  向上调整算法

  在比较交换元素的过程中，我们提供一个比较函数以便交换元素

  //交换void my_swap(HPDataType* a, HPDataType* b){int tmp = *a;*a = *b;*b = tmp;}

   以下就是对向上调整的实现

  //向上调整void AdjustUp(HPDataType* a, int child){assert(a);int parent = (child - 1) / 2;    //如果孩子为0则比较结束while (child > 0) {if (a[parent] > a[child]) {my_swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else break;}}

  1. 找相比较的父子结点：根据堆中父子结点位置规则，先找到需要比较检查调整的父子结点
  2. 比较父子结点大小：如果建立小堆，且子节点小于父节点，交换父子结点数据；如果此时子节点大于父节点，跳出循环
  3. 更新父子结点：将父节点的位置赋给child，同时更新parent
  4. 检查是否退出循环：如果child==0时，跳出循环

  堆的创建

  下面我们给出一个数组的元素，建成一个堆。在刚刚讲完堆的插入和向上调整过后，其实创建堆就显得格外容易了。我们只需要从数组中取出元素，然后依次插入到堆中便可以完成堆的创建，以下是实现代码：

  // 堆的构建void HeapCreate(Heap* hp, HPDataType* a, int n){assert(hp);    //初始化堆时，别忘记初始化以下hp中的元素hp->_a = NULL;hp->_capacity = hp->_size = 0;for (int i = 0; i _a, hp->_size - 1);}}

  堆的删除

  堆的删除，通常意义上是删除堆顶的元素。如果建的是小堆，那么堆顶的元素就是堆中最小的数；如果建的是大堆，那么堆顶就是堆中最大的元素。

  想要删除堆顶元素，不能通过整体向前移动后面的堆元素的方式来删除元素，因为这样会打乱元素之间的父子关系，打乱了父子关系，整个堆就很有可能不符合“父亲一定小于等于（或大于等于）孩子”这一规则了。

  真正的实现方式是，将堆顶元素和堆底元素互换位置，将size - 1，再将此时堆顶的元素进行向下调整。

  过程见下图：

  // 堆的删除void HeapPop(Heap* hp){assert(hp);assert(hp->_size != 0);my_swap(&hp->_a[0], &hp->_a[hp->_size - 1]);hp->_size--;    //向下调整AdjustDown(hp->_a, hp->_size, 0);}

  既然讲到了向下调整，其实就又涉及到了向下调整算法。

  向下调整算法

  向下调整，顾名思义就是将元素往下调，先给大家展示调整代码，再来解析过程

  //向下调整void AdjustDown(HPDataType* a, int n, int parent){assert(a);int child = parent * 2 + 1;while (child  a[child]) {my_swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else break;}}

  1. 找相比较的父子结点：根据堆中父子结点位置规则，先找到需要比较检查调整的父子结点，这里先预设左孩子比右孩子小，当发现右孩子更小时，child + 1，在比较左右孩子之前，还需要考虑到child + 1不会导致越界
  2. 比较父子结点：父节点大于子结点时（此时建立的是小堆），交换父子结点数据；如果父节点小于字结点，跳出循环
  3. 更新父子结点：将child赋给parent，计算新的child，进入新一轮循环
  4. 判断循环结束：当孩子跃出数据存储范围时，循环结束

  取堆顶的数据

  这里没什么好说，堆的数组中第一个元素就是堆顶的数据

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

  堆数据的个数和堆的判空

  这里直接用堆中的size元素就OK

  // 堆的数据个数int HeapSize(Heap* hp){assert(hp);return hp->_size;}// 堆的判空int 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;}

  到这里堆的实现基本上就结束了

  体验一下手写的堆

  #include"heap.h"int main(){Heap hp;int arr[] = { 5,4,3,2,1 };HeapCreate(&hp, arr, sizeof(arr) / sizeof(int));printf("%d\n\n", HeapSize(&hp));while (!HeapEmpty(&hp)) {printf("%d\n", HeapTop(&hp));HeapPop(&hp);}HeapDestory(&hp);return 0;}

  结语

  今天的内容到这里就结束了，本篇博客带大家认识了一下树和堆，但这里只是带大家稍微看了看堆的实现。关于堆的内容其实还有很多，topk问题，堆排序，优先级队列中会更深入的带领大家去了解和使用堆，在下一篇数据结构中，会更深入的挖掘一些堆的应用，并计算一下其时间复杂度，让大家体会到堆的魅力。如果还想了解更多有趣的内容，还请多多支持博主，比心♥