【数据结构】二叉树的顺序存储结构 —— 堆

创始人

2024-02-04 00:24:16

0次

文章目录

前言
二叉树的顺序存储
堆的概念和结构
堆的实现
- 结构的定义
- 接口总览
- 初始化
- 销毁
- 插入
- 向上调整
- 删除
- 向下调整
- 取堆顶数据
- 计算堆大小
- 判空
- 打印堆
完整代码
- Heap.h
- Heap.c
- test.c
结语

前言

今天，我们开始二叉树的学习。本篇博客的内容为 介绍二叉树的顺序存储和堆的实现。今天的内容相对于之前的数据结构就多了一些 “科技与狠活” 了，不单单是看结构了，难度略微有些上升。所以做好准备，我们这就开始。

二叉树的顺序存储

二叉树的顺序结构存储是使用 数组存储。

一般使用数组只适合表示 完全二叉树，因为完全二叉树最后一层连续且其它层均满，使用顺序存储不存在空间浪费。

二叉树顺序存储在物理上是一个数组，在逻辑上是一棵 二叉树。

我们这篇博客学习的堆就是使用 顺序存储 来实现。

堆的概念和结构

概念：如果有一个关键码的集合 K = {k0 ， k1 ， k2 ， … ， kn-1} ，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >=K2i+2) i = 0 ， 1 ， 2… ，则称为小堆 ( 或大堆) 。（即双亲比孩子的数值小(大)——小(大)堆）将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆分为大堆和小堆：

大堆：树中所有父亲节点数据大于等于孩子节点数据
小堆：树中所有父亲节点数据小于等于孩子节点数据

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值
堆是一棵完全二叉树

说了这么多，其实判断是否为堆最好的方式就是画图，画出堆构成的完全二叉树，看其是否符合性质。

堆的实现

实现堆之前，我们需要了解一下概念：左孩子下标为奇数，右孩子下标为偶数

根据概念推导：

左孩子下标 = 2 * 双亲下标 + 1

右孩子下标 = 2 * 双亲下标 + 2

双亲下标 = (孩子下标 - 1) / 2 —— 这个式子是向下取整的，左右孩子都适用

结构的定义

堆是完全二叉树，其存储结构是顺序存储。那就和顺序表一样，将数据存在数组中，给定size 记录堆中元素个数，capacity 记录堆的最大容量。

typedef int HPDataType;
typedef struct Heap
{HPDataType* a; // 存储数据的空间int size; // 大小int capacity; // 容量
}HP;

本篇博客默认实现的是小堆。

接口总览

void HeapPrint(HP* php); // 打印
void HeapInit(HP* php); // 初始化
void HeapDestroy(HP* php); // 销毁
void HeapPush(HP* php, HPDataType x); // 堆尾插入数据
void HeapPop(HP* php); // 删除堆顶数据
HPDataType HeapTop(HP* php); // 取堆顶数据
int HeapSize(HP* hp); // 计算大小
bool HeapEmpty(HP* hp); // 判空
void AdjustUp(HPDataType* a, int child); // 向上调整
void AdjustDown(HPDataType* a, int n, int parent); // 向下调整

初始化

堆的初始化和顺序表是一样的，因为我们用的就是顺序存储：

void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}

销毁

堆的销毁只要释放空间，然后把 size 和 capacity 置0就可以。

void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

插入

堆的插入就是在 数组尾部 的插入，就是数组的尾插。

堆插入数据只会在尾部，所以无需封装接口用来扩容，直接判断是否要扩容就可以。

堆在插入数据后，需要保持堆的结构，之前是小/大堆，在插入数据后也应该是小/大堆。当插入数据后，如果破坏了结构，就需要 向上调整。

void HeapPush(HP* php, HPDataType x)
{assert(php);// 检查容量if (php->size == php->capacity){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;// 向上调整AdjustUp(php->a, php->size - 1);
}

向上调整

我们默认实现为小堆，于是堆的插入就可能会造成 两种情况：

插入数据大于它的父亲 ，插入后，仍然为小堆，这种情况无需调整：

插入数据小于它的祖先(从根到该节点所经分支上的所有节点，就是它的父亲，爷爷等)，插入后，不为小堆，此时需要将 插入数据需要向上调整，直到它为小堆：

理清了这两个情况，再梳理一下细节：

向上调整，肯定是以 孩子为基准，孩子调整到堆顶就代表着向上调整结束了。如果使用父亲为基准的话，是非正常结束的(孩子调整到0没有结束，而是通过比较值后，break退出的)。

而中间的过程就是判断孩子是否小于父亲，如果小于就交换它们的值，然后将孩子迭代为父亲，再重新计算父亲，继续调整上方；如果孩子大于等于父亲，就退出，无需调整。

通过不断向上调整元素，就可以构建出来小堆。

void Swap(HPDataType* p1, HPDataType* p2)
{assert(p1 && p2);HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)
{assert(a);// 求父亲int parent = (child - 1) / 2;// 默认小堆while (child > 0){// 如果孩子小于父亲，调整if (a[child] < a[parent]){Swap(&a[child], &a[parent]); // 交换child = parent; // 孩子迭代为父亲parent = (child - 1) / 2; // 重新计算父亲}else{break;}}
}

建大堆 只要修改一下条件：

if (a[child]) > a[parent]

删除

堆的删除为删除 堆顶的数据。

对于删除来说，有两个方案：

直接头删
交换堆顶和堆底元素，尾删堆底元素，将堆顶元素 向下调整。(堆底元素就是数组尾部的元素)。

我们先看看 方案一 可不可行：

首先，由于堆是顺序存储的，那么 头删就要挪动数据，时间复杂度就为O(N)。其次，这样会 完全打乱关系。

举个例子，假设 15 和 18 在第二层原本是兄弟，但是由于头删，15到了堆顶，变成了 18 的父亲。关系就乱了，感情也就淡了(doge)。18 表示我拿你当兄弟，你却想当我父亲。但是就这一对的话，还能忍忍，但是全部的父子关系都被破坏了，所以肯定不可行。

所以，方案一就被否决了，那就只能使用 方案二 了：

方案二的话就很好，删除元素前，交换了堆顶和堆底的元素，然后将堆底尾删，尾删的时间复杂度只有O(1)。通过向下调整对堆顶元素下调时，也不会破坏过多的关系。

void HeapPop(HP* php)
{assert(php);assert(php->size > 0); // 堆空不能删// 交换堆顶和最后一个节点的值Swap(&php->a[0], &php->a[php->size - 1]);// 尾删php->size--;AdjustDown(php->a, php->size, 0); // 向下调整
}

向下调整

向下调整的步骤为：

找到左右孩子中的 小孩子。
判断父亲是否大于 小孩子，如果是则交换，不是则退出
交换后将 父亲迭代到大孩子的位置，重新计算孩子。

注意找最大孩子的时候，大孩子必须存在，小心越界。

向下调整的 循环条件 为 孩子下标 < 堆的大小，如果继续调整就越界了。

void Swap(HPDataType* p1, HPDataType* p2)
{assert(p1 && p2);HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(HPDataType* a, int n, int parent)
{// 假设最小孩子int minchild = 2 * parent + 1;while (minchild < n){// 找最小孩子if (minchild + 1 < n && a[minchild + 1] < a[minchild]){minchild++;}// 如果父亲大于孩子，调整if (a[parent] > a[minchild]){Swap(&a[parent], &a[minchild]); // 交换parent = minchild; // 迭代minchild = 2 * parent + 1;}else{break;}}
}

调大堆 只要改变两个条件：

if (minchild + 1 < n && a[minchild + 1] > a[minchild]) // 找大孩子
if (a[parent] < a[minchild]) // 如果父亲小于孩子，则交换

取堆顶数据

若堆非空，则取0下标位置数据：

HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

计算堆大小

这就更简单了，直接返回 size：

int HeapSize(HP* php)
{assert(php);return php->size;
}

判空

只要 size == 0 ，堆就为空：

bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

打印堆

void HeapPrint(HP* php)
{assert(php);for (int i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}

完整代码

Heap.h

#pragma once#include 
#include 
#include 
#include typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;// 堆的构建
void HeapCreate(HP* hp, HPDataType* a, int n);void HeapPrint(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);// 保持他继续是一个堆 O(logN)
void HeapPush(HP* php, HPDataType x);// 删除堆顶的数据，并且保持他继续是一个堆 O(logN)
void HeapPop(HP* php);HPDataType HeapTop(HP* php);int HeapSize(HP* hp);
// 堆的判空
bool HeapEmpty(HP* hp);

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1 #include "Heap.h"void HeapPrint(HP* php)
{assert(php);for (int i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}// 初始化 不开空间
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}// 销毁
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{assert(p1 && p2);HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}// 向上调整
void AdjustUp(HPDataType* a, int child)
{assert(a);// 算父亲int parent = (child - 1) / 2;// 默认小堆while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}// 保持他继续是一个堆 O(logN)
void HeapPush(HP* php, HPDataType x)
{assert(php);// 检查容量if (php->size == php->capacity){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;// 向上调整AdjustUp(php->a, php->size - 1);
}// 向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{// 假设最小孩子int minchild = 2 * parent + 1;while (minchild < n){// 找最小孩子if (minchild + 1 < n && a[minchild + 1] < a[minchild]){minchild++;}if (a[parent] > a[minchild]){Swap(&a[parent], &a[minchild]);parent = minchild;minchild = 2 * parent + 1;}else{break;}}
}// 删除堆顶的数据，并且保持他继续是一个堆 O(logN)
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);// 交换堆顶和最后一个节点的值Swap(&php->a[0], &php->a[php->size - 1]);// 尾删php->size--;AdjustDown(php->a, php->size, 0);
}HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}int HeapSize(HP* php)
{assert(php);return php->size;
}
// 堆的判空
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1 #include "Heap.h"void TestHp1()
{HP hp;HeapInit(&hp);int arr[] = { 27,15,19,18,28,34,65,49,25,37 };int sz = sizeof(arr) / sizeof(arr[0]);for (int i = 0; i < sz; i++){HeapPush(&hp, arr[i]);}HeapPrint(&hp);HeapPop(&hp);HeapPrint(&hp);// 取五个最小数据/*int k = 5;while (k--){printf("%d ", HeapTop(&hp));HeapPop(&hp);}*/HeapDestroy(&hp);
}void TestHp2()
{int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };HP hp;HeapInit(&hp);for (int i = 0; i < sizeof(array) / sizeof(int); ++i){HeapPush(&hp, array[i]);}// 排序while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapDestroy(&hp);
}int main()
{TestHp1();//TestHp2();return 0;
}

结语

到这里，本篇博客就到此结束了。看到这儿，相信大家也对堆有了一定的了解。

今天的内容在二叉树一块还是较简单的。下篇博客我会讲解由堆引申出的两个堆的应用 —— 堆排序和 TopK问题。所以今天的内容还是很重要的，只有看懂下篇博客理解起来才比较清晰。

如果觉得anduin写的还不错的话，还请一键三连！如有错误，还请指正！

我是anduin，一名C语言初学者，我们下期见！

上一篇：LinkedList详解

下一篇：内网渗透中最常见的十种漏洞分析总结