数据结构与算法：二叉树之“堆排序”

目录

一、树概念及结构

二、二叉树树概念及结构

 特殊的二叉树

三、堆的概念及结构

四、堆的创建

1、声明结构体

2、初始化 

3、销毁

4、添加新元素

5、交换元素 

6、向上调整

7、判断堆是否为空

8、移除堆顶元素

9、向下调整

10、获取堆元素个数 

五、使用堆排序

 排降序建小堆

 完整版：

Heap.h声明部分

Heap.c函数部分

text.c使用及测试部分

---

一、树概念及结构

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

• 有一个特殊的结点，称为根结点，根节点没有前驱结点。
• 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1 <= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
• 因此，树是递归定义的
• 注意：树形结构中，子树之间不能有交集，否则就不是树形结构

• 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
• 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点
• 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点
• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
• 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
• 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
• 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
• 森林：由m（m>0）棵互不相交的树的集合称为森林；

二、二叉树树概念及结构

二叉树是一个由n(n>=0)个结点构成的有限集合，其中该集合可以为空，这时称其为空二叉树；或者由一个根结点以及两个互不相交的左子树和右子树组成，且左右子树均为二叉树。在二叉树中，子树被明确区分为左子树和右子树，且它们的顺序不可颠倒。

• 值得注意的是，二叉树的定义具有递归性质，因为二叉树本身可以为空，根结点可以有空的左子树或空的右子树。
• 这使得二叉树与普通树有明显的区别，即使只有一棵子树存在，也需要明确指定它是左子树还是右子树。这是二叉树与树最主要的区别之一。
• 请注意，二叉树不同于一般的树，因为它的子树具有左右之分，并且顺序不能颠倒。因此，“二叉树是结点度为2的树”的说法是不正确的。

二叉树的基本形态包括以下五种：

 特殊的二叉树

当涉及到二叉树的特殊类型时，有两个主要概念需要了解：满二叉树和完全二叉树。

• 满二叉树：满二叉树是一种特殊的二叉树，其特点是每个层级的结点数都达到最大值。具体来说，如果一个二叉树的深度为K，且结点总数为2^K - 1，那么它就是一个满二叉树。满二叉树的每一层都包含最大数量的结点，使得它具有很特殊的结构。
• 完全二叉树：完全二叉树是一种高效的数据结构，与满二叉树相关。一个二叉树如果在深度为K的情况下，其结点都与深度为K的满二叉树中的编号从1到n的结点一一对应，那么它就被称为完全二叉树。需要注意的是，满二叉树是完全二叉树的一个特殊情况。

性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有个结点。
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是。
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0 , 度为2的分支结点个数为 n2 ,则有 n0 ＝n2 ＋1。
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log以2为底，n+1的对数。
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

• 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
• 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
• 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

 

三、堆的概念及结构

堆（Heap）是一种特殊的树状数据结构，通常用于实现优先队列和对数据进行排序。堆的主要特点是它是一棵树，其中每个节点的值满足特定的堆属性。在堆中，通常有两种主要类型：最大堆和最小堆。

• 最大堆（Max Heap）：在最大堆中，每个节点的值都不小于其子节点的值，即根节点的值最大。这意味着最大堆的最大元素总是位于根节点，而子树中的值递减。

• 最小堆（Min Heap）：在最小堆中，每个节点的值都不大于其子节点的值，即根节点的值最小。这意味着最小堆的最小元素总是位于根节点，而子树中的值递增。

堆的常见用途包括：

• 优先队列：堆可以用来实现高效的优先队列，使得可以快速访问和删除具有最高或最低优先级的元素。

• 堆排序：堆排序是一种高效的排序算法，它利用堆的性质来进行排序。它的时间复杂度为O(n log n)。

堆通常是以数组的形式来表示，其中父节点和子节点之间的关系通过数组索引来建立。具体来说，对于一个具有n个元素的堆，节点的索引从1到n编号，其中：

• 父节点的索引为i，则它的左子节点的索引为2i，右子节点的索引为2i + 1。
• 子节点的索引为i，则其父节点的索引为i/2。

这种数组表示方法使得堆的操作更加高效，因为它不需要使用额外的指针来表示树的结构。

四、堆的创建

本次以小堆举例进行讲解 

1、声明结构体

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

• HPDataType 被定义为 int 类型，表示堆中存储的数据类型。
• 创建堆的结构体Heap，定义别名为HP。
• 指针a指向堆的数组
• size为堆的当前大小
• capacity为堆的容量

2、初始化 

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

• assert 判断指针是否合法。
• 指向数组的指针 a 初始化为 NULL。
• size 和 capacity 初始化为0。

3、销毁

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

• assert 判断指针是否合法。
• 释放数组空间，将 a 指针置空，同时将 capacity 和 size 设置为0。

4、添加新元素

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, newCapacity * sizeof(HPDataType));if (tmp==NULL) {perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

• assert 判断指针是否合法。
• 判断当前是否需要扩容，初始堆的容量为0，则为堆开辟四个HPDataType类型大小的空间，如果当前堆的大小size等于容量capacity，则将堆扩容为两倍原来大小的空间。
• 扩容失败，打印错误信息，结束函数
• 将扩容的空间赋值给指针a，更新容量capacity的大小。
• 将要增加的元素插入数组a中，更新size大小。
• 每次在堆中添加新元素时，小堆可能会被破坏，所以我们再添加新元素后，要在AdjustUp函数中判断是否需要进行向上调整。

5、交换元素 

后续函数会经常用到，同一串代码放到函数里供其使用者调用比较好。 

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

6、向上调整

void AdjustUp(HPDataType* a, int child)
{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;}}
}

• 首先通过当前的孩子节点child找到父节点parent。
• 当child大于0时，进行判断当前chilid是否需要调整
• 如果child位置元素小于parent位置元素，则通过Swap进行交换，然后新的孩子节点更新为parent位置，通过孩子节点更新新的父节点位置，然后继续比较和交换，直到不再需要交换为止。
• 如果当前孩子节点不小于当前的父节点，则结束循环，当前节点不需要向上调整。

7、判断堆是否为空

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

8、移除堆顶元素

 一般来说，堆的移除操作通常是移除堆顶元素，这样大堆小堆的性质保持不变，如果移除堆底会破坏堆的性质。

void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

• assert 判断指针是否合法。
• 检查堆是否为空，为空则报错。
• 移除堆顶元素有两种方法，首选第二种方法，不需要重新建堆，节约时间。
• 
• 首先交换堆顶堆尾，然后size减一完成删除，后续不会访问删除位置的元素，所以不释放内存空间也可以。
• 然后进行向下调整。

9、向下调整

向下调整是从第一个节点（父节点）开始向下调整，传入参数命名为parent 

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

• 通过传入参数获取到当前的左子节点的位置。
• 当child位置小于数组元素个数时进行判断。
• 进入循环，首先判断检查右子节点是否存在并且比左子节点的值小，如果是，将 child 更新为右子节点的索引，以确保选择更小的子节点进行比较。
• 比较选定的子节点的值与父节点的值，如果子节点的值小于父节点的值，就交换它们。
• 更新parent为新的子节点位置，更新child为新的左子节点位置，然后继续比较和交换，直到不再需要交换为止。
• 如果当前子节点不小于当前父节点则停止循环。

10、获取堆元素个数 

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

五、使用堆排序

void HeapSort(int* a, int n)
{HP hp;HeapInit(&hp);// 时间复杂度：N*logNfor (int i = 0; i < n; ++i){HeapPush(&hp, a[i]);}// 时间复杂度：N*logNint i = 0;while (!HeapEmpty(&hp)){int top = HeapTop(&hp);a[i++] = top;HeapPop(&hp);}HeapDestroy(&hp);
}

可以使用这种方式，但有诸多弊端： 

1. 要先有一个堆,太麻烦。
2. 空间复杂度+拷贝数据

 排降序建小堆

所以我们要在传入的原数组上排降序，需要使用建小堆的方式向上调整。

void HeapSort(int* a, int n)
{// 建堆--向上调整建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再调整，选出次小的数AdjustDown(a, end, 0);--end;}
}

• 从根节点的子节点开始向上建堆，除了根节点以外，每个节点都进行向上调整。
• 定义堆的最后一个节点end为n-1
• 
• 我们将堆的根节点（也就是最小值）与堆的最后一个元素交换，即将最小值放到排序尾部即为好的部分。接下来，通过调用AdjustDown函数，将堆的大小减一，再次将堆调整为最小堆。
• 重复while循环内部操作，直到整个数组排序完成。每次交换和堆的调整都会将最小的元素添加到已排序的部分，直到整个数组都有序。

HeapSort的时间复杂度为O(nlog(n))，它不需要额外的空间来存储数据，所以是一种原地排序算法。它在最坏情况下的性能仍然是O(nlog(n))，因此相对稳定，适用于大规模数据的排序。 

我们也可以向下建堆：

倒着调整叶子节点不需要处理，从倒树第一个非叶子节点开始，即最后一个节点的父节点开始调整。

void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; --i){	AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再调整，选出次小的数AdjustDown(a, end, 0);--end;}
}

 完整版：

Heap.h声明部分

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void HeapInit(HP* php);
void HeapDestroy(HP* php);void AdjustUp(HPDataType* a, int child);
void HeapPush(HP* php, HPDataType x);
bool HeapEmpty(HP* php);
void AdjustDown(int* a, int n, int parent);
void HeapPop(HP* php);HPDataType HeapTop(HP* php);
int HeapSize(HP* php);

Heap.c函数部分

#include "Heap.h"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 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[child] < a[parent]) {Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}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, newCapacity * sizeof(HPDataType));if (tmp==NULL) {perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}bool HeapEmpty(HP* php)
{assert(php);return php->size==0;
}
void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);parent = child;child = parent * 2 - 1;}else {break;}}
}void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php->a[0];
}int HeapSize(HP* php)
{assert(php);return php->size;
}

text.c使用及测试部分

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"void HeapSort(int* a, int n)
{// 建堆--向上调整建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}// 建堆--向下调整建堆//for (int i = (n - 1 - 1) / 2; i >= 0; --i)//{//	AdjustDown(a, n, i);//}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);// 再调整，选出次小的数AdjustDown(a, end, 0);--end;}		
}int main()
{int a[] = { 7,8,3,5,1,9,5,4 };HeapSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < 8; i++) {printf("%d  ", a[i]);}return 0;
}//---测试堆函数功能---
//int main()
//{
//	HP hp;
//	HeapInit(&hp);
//	int a[] = { 65,100,70,32,50,60 };
//	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
//	{
//		HeapPush(&hp, a[i]);
//	}
//	
//	while (!HeapEmpty(&hp))
//	{
//		int top = HeapTop(&hp);
//		printf("%d\n", top);
//		HeapPop(&hp);
//	}
//
//	return 0;
//}