当前位置：首页 > news >正文

堆的简单介绍

news 2025/7/6 6:09:23

首先介绍一下完全二叉树的概念：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。（也就是深度为K的二叉树前K-1层是满二叉树，第K层时不是满二叉树但是叶子节点从左往右依次有序排列）

堆的概念：

堆的存储方式是使用数组，类似于顺序表。如下图所示：可以得出一些关系，

1. 父亲节点的下标==孩子节点的下标-1/2，如0=（1-1）/2（0的左孩子）；0=（2-1）/2（0的右孩子）；

2. 左孩子节点的下标==父亲的下标*2+1。如1=0*2+1；右孩子的下标等于左孩子的下标+1

下面开始讲解堆的实现

堆的实现，Heap.c文件：

前面说到堆的底层实际就是数组，类似于顺序表，所以同样是利用结构体定义一个堆结构。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>typedef int HPDataType;typedef struct Heap
{HPDataType* _data;int _size;int _capacity;
}Heap;// 堆的构建（初始化）
void HeapInit(Heap* php, HPDataType* arr, int num);// 堆的销毁
void HeapDestroy(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);// 堆顶的删除
void HeapPop(Heap* php);// 堆顶数据
HPDataType HeapTop(Heap* php);// 堆的向下调整
void AdjustDown(HPDataType* _data, int num, int root);// 传址--交换两个数
void Swap(HPDataType* a, HPDataType* b);

堆的实现文件：Heap.c文件

首先讲清楚向下调整代码，很重要：

现在我们给出一个数组（int arr[] = {27,15,19,18,28,34,65,49,25,37};），逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

如下图所示：

代码：

#define _CRT_SECURE_NO_WARNINGS 
#include "Heap.h"// 打印堆
void HeapPrint(Heap* php)
{for (int i = 0;i < php->_size;i++){printf("%d ", php->_data[i]);}printf("\n");
}// 传址--交换两个数
void Swap(HPDataType* a, HPDataType* b)
{HPDataType temp = *a;*a = *b;*b = temp;
}// 小堆的向下调整，前提：左右子树都是小堆，即所有父亲小于左右孩子
// 大堆的向下调整，前提：左右子树都是大堆，即所有父亲大于左右孩子
void AdjustDown(HPDataType* _data, int num, int root)
{int parent = root;int child = parent * 2 + 1; // 左孩子while (child < num)   {// 找出左右孩子中小的那一个；//if (child + 1 < num && _data[child + 1] > _data[child]) // 注意越界访问(建大堆)if (child+1 < num && _data[child + 1] < _data[child]) // 注意越界访问，child+1是右孩子，完全二叉树最后的一个父亲节点他可能没有右孩子为避免非法访问，必须加入这个条件{++child;}// 如果小的那个孩子小于父亲则交换//if (_data[child] > _data[parent]) // 建大堆if (_data[child] < _data[parent]){Swap(&_data[child], &_data[parent]);parent = child;            // 交换之后把孩子节点（它又是它的孩子的父亲）的位置给给父亲child = parent * 2 + 1;    // 重新计算孩子的孩子节点的下标}else // 父亲小于孩子就跳出循环{break;}}
}// 堆的构建（初始化）
void HeapInit(Heap* php, HPDataType* arr, int num)
{assert(php);// 将传入的数组（不是堆的数组）拷贝到我们的数组内// 申请空间HPDataType* temp = (HPDataType*)malloc(sizeof(HPDataType) * num);if (temp == NULL){perror("malloc fali");exit(-1);}php->_data = temp;// 使用memcpy函数拷贝，第一个参数是目标空间起始地址，第二个是数据源的地址，第三个是一次拷贝多少个字节的内容memcpy(php->_data, arr, sizeof(HPDataType) * num);php->_size = num;php->_capacity = num;// 构建堆 (从最后一个叶子节点的父亲开始调整逐步往上调整子树成为小堆，// i=0时根节点的左右字数已经是小堆，此时将根节点调整至满足小堆即可)// for (int i = num;i >= 0;i--) 从最后一个节点开始比较也行只是叶子节点没有孩子没必要调整for (int i = (num - 1 - 1) / 2;i >= 0;i--)  // num-1是数组的最后一个下标，然后套到求父亲节点的公式{AdjustDown(php->_data, php->_size, i);}
}

注意：最开始给的数组未必左右子树都是堆，所以从最后一个叶子节点的父亲开始向下调整，如下图所示，根节点15的左右子树都不是堆；所以要从下标4的位置开始调整，4-3-2-1-0就调整完毕。这里展示的除了0下标和4下标不是堆，其他1-2-3下标都是小堆。

堆的插入、销毁、删除堆顶数据，获得堆顶数据：（向上调整刚好也可以参考上图，插入元素10）

// 向上调整
void AdjustUp(HPDataType* _data, int num, int child)
{int parent = (child - 1) / 2;// 孩子和父亲比较大小while (child > 0){if (_data[child] < _data[parent]){Swap(&_data[child], &_data[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}// 堆的销毁
void HeapDestroy(Heap* php)
{assert(php);free(php->_data);php->_data = NULL;php->_size = php->_capacity = 0;
}
// 堆的插入
void HeapPush(Heap* php, HPDataType x)
{assert(php);// 插入数据要检查空间是否足够if (php->_size == php->_capacity){php->_capacity *= 2;   // 2倍数扩容HPDataType* temp = (HPDataType*)realloc(php->_data, sizeof(HPDataType) * php->_capacity);if (temp == NULL){perror("realloc fail");exit(-1);}php->_data = temp;}php->_data[php->_size] = x;php->_size++;// 向上调整，将插入的数据和它的父亲以及父亲的父亲……作比较AdjustUp(php->_data, php->_size, php->_size - 1);
}// 堆顶的删除
void HeapPop(Heap* php)
{assert(php);assert(php->_size > 0);// 让堆顶的数据和最后一个数据交换，然后size-1，然后在向下调整重新构建堆Swap(&php->_data[0], &php->_data[php->_size - 1]);php->_size--;AdjustDown(php->_data, php->_size, 0);// 此时左右子树都是堆，只需要从0的位置向下调整即可
}// 堆顶数据
HPDataType HeapTop(Heap* php)
{assert(php);assert(php->_size > 0);return php->_data[0]; // 直接返回堆顶的数据即可
}

建堆的测试文件：test.c：

#define _CRT_SECURE_NO_WARNINGS 
#include "Heap.h"// 数据降序：排小堆
// 数据升序：排大堆
// 堆排序
void Heapsort(HPDataType* a, int n)
{for (int i = (n - 1 - 1) / 2;i >= 0;i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){// 小堆后就选好了最小的放在第一个位置，将它和最后一个位置换掉，然后对前n-1个数据再排小堆Swap(&a[0], &a[end]);// 选次小的……AdjustDown(a, end, 0);--end;}
}int main()
{int arr[] = { 27,15,19,18,28,34,65,49,25,37 };Heap hp;HeapInit(&hp, arr, sizeof(arr) / sizeof(int));HeapPrint(&hp);HeapPush(&hp, 13);HeapPrint(&hp);HeapDestroy(&hp);//Heapsort(arr, sizeof(arr) / sizeof(int));return 0;
}

结论：本文介绍了完全二叉树和堆的概念及其实现。完全二叉树是效率很高的数据结构，其每个节点都与满二叉树对应。堆使用数组存储，实现父子节点间的下标关系。文章详细讲解了堆的实现过程，包括初始化、插入、删除、调整等核心操作，重点分析了向下调整算法（要求左右子树已满足堆性质）和向上调整算法（用于插入操作）。同时提供了堆排序的实现思路，通过不断调整堆结构实现数据有序排列。代码示例展示了堆的各种操作及测试流程，包括堆的构建、插入元素、删除堆顶等。

查看全文

http://www.lryc.cn/news/580306.html