【数据结构】结构实现：顺序存储模式实现堆的相关操作

🚩纸上得来终觉浅， 绝知此事要躬行。

🌟主页：June-Frost

🚀专栏：数据结构

🔥该文章着重讲解了使用顺序结构实现堆的插入和删除等操作。

目录：

• 🌍二叉树的顺序结构
• • 🔭 堆
  • 🌏 代码实现
  • • ✉️ 堆的插入
    • ✉️ 堆的删除
    • ✉️ 其他部分
    • ❤️ 结语

      🌍二叉树的顺序结构

       二叉树的顺序存储是指将二叉树中的所有节点按照一定的顺序（一层一层）存储到一个数组中。

      

       我们可以通过数组下标来表示节点之间的父子关系。

      找左孩子节点：leftchild = parent * 2 + 1

      找右孩子节点：rightchild = parent * 2 + 2

      例如，找B的左孩子 : B的下标 * 2 + 1，得到3 ，即为D。

      找父亲节点：parent = （ child -1 ）/ 2

      例如，找G的父母：（G的下标-1）/ 2 得到 2 ，即为C 。

       需要注意的是，二叉树的顺序存储适用于满二叉树或完全二叉树的情况，对于其他类型的二叉树，顺序存储可能会造成空间浪费或访问效率低下的问题。

      例如：

      

       这类二叉树不适合顺序存储，适合链式存储。

      🔭 堆

       数据结构中还衍生出了一个结构 —— 堆 ， 堆是非线性结构，也是一种完全二叉树。堆的两个常见类型是大堆和小堆。在大堆中，父节点的值总是大于或等于其子节点的值；而在小堆中，父节点的值总是小于或等于其子节点的值。堆通常用数组来实现。

       所以，对于任意一个数组是可以看作一颗完全二叉树，但不一定是堆。

      ---

      🌏 代码实现

       这里将实现堆的插入和删除，以小堆为例。

       堆的结构特点是：存储结构——数组，逻辑结构——完全二叉树。所以可以定义结构体为：

      typedef int HPDataType;
      typedef struct Heap
      {
      	HPDataType* a;
      	int size;
      	int capacity;
      }HP;
      

      ✉️ 堆的插入

       插入的需求为：无论如何插入，都必须保持为堆。因为存储结构是数组，所以选择效率更快的尾插，然后再进行调整（插入的数据会影响它的祖先）。

       调整部分有这样的3种场景：

      1. 不会影响祖先

      

      2.影响部分，但不影响到根。

      

      3.影响到全部祖先

      

      注：这种调整是向上调整。时间复杂度为 O(logN)

      💫调整的条件：

      

      📙实现代码：

      //交换数据
      void Swap(HPDataType* p1, HPDataType* p2)
      {
      	HPDataType tmp = *p1;
      	*p1 = *p2;
      	*p2 = tmp;
      }
      //向上调整
      void AdjustUp(HPDataType* a, int child)
      {
      	int parent = (child - 1) / 2;
      	while (child > 0)
      	{
      		if(a[parent] > a[child])
      		{
      			Swap(&a[child], &a[parent]);
      			child = parent;
      			parent = (parent - 1) / 2;
      		}
      		else
      		{
      			break;
      		}
      	}
      }
      //插入数据
      void HeapPush(HP* php, HPDataType x)
      {
      	assert(php);
      	if (php->capacity == php->size)
      	{
      		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
      		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newCapacity);
      		if (tmp == NULL)
      		{
      			perror("realloc fail");
      			exit(-1);
      		}
      		php->a = tmp;
      		php->capacity = newCapacity;
      	}
      	php->a[php->size] = x;
      	php->size++;
          //向上调整
      	AdjustUp(php->a, php->size - 1);
      }
      

      ✉️ 堆的删除

       在堆中，删除栈顶元素才是有意义的，这样经过调整后，根就是次小或次大的值。由于堆的存储结构是数组，尾插尾删的效率很高，所以可以考虑将根和最后一个数组元素交换，然后不断调整。

      ①

      

      这样的操作之后，可以发现一个特性：左右子树依旧是小堆。

      ②

      

      注：这种调整方式为向下调整，时间复杂度为O(logN)。

      💫调整条件：

       当子节点的下标超出数组范围时，说明已经没有子节点了，已经换到了叶子。（针对实现的代码而言，是已经没有了左孩子，因为堆是完全二叉树，自然也就没有右孩子，说明换到了叶子）

      📙实现代码：

      //向下调整
      void AdjustDown(HPDataType* a, int n, int parent)
      {
      	int child = parent * 2 + 1;//假设左孩子最小
      	while (child size > 0);
      	Swap(&php->a[0], &php->a[php->size - 1]);
      	php->size--;
      	AdjustDown(php->a, php->size, 0);
      }
      

      ✉️ 其他部分

      一些简单的接口：

      //初始化
      void HeapInit(HP* php)
      {
      	assert(php);
      	php->a = NULL;
      	php->size = 0;
      	php->capacity = 0;
      }
      //销毁
      void HeapDestroy(HP* php)
      {
      	assert(php);
      	free(php->a);
      	php->a = NULL;
      	php->capacity = php->size = 0;
      }
      //打印元素
      void HeapPrint(HP* php)
      {
      	assert(php);
      	int i = 0;
      	for (i = 0; i size; i++)
      	{
      		printf("%d ", php->a[i]);
      	}
      	printf("\n");
      }
      //取堆顶元素
      HPDataType HeapTop(HP* php)
      {
      	assert(php);
      	assert(php->size > 0);
      	return php->a[0];
      }
      //判空
      bool HeapEmpty(HP* php)
      {
      	assert(php);
      	return php->size == 0;
      }
      

      ---

      ❤️ 结语

       文章到这里就结束了，如果对你有帮助，你的点赞将会是我的最大动力，如果大家有什么问题或者不同的见解，欢迎大家的留言~

手机扫描二维码访问