数据结构·二叉树(2)

目录

1 堆的概念

2 堆的实现

2.1 堆的初始化和销毁

2.2 获取堆顶数据和堆的判空

2.3 堆的向上调整算法

2.4 堆的向下调整算法

2.4 堆的插入

2.5 删除堆顶数据

2.6 建堆

3 建堆的时间复杂度

3.1 向上建堆的时间复杂度

3.2向下建堆的时间复杂度

4 堆的排序

---

前言：前面介绍了树以及二叉树及其二叉树的存储方式，本文就介绍基于二叉树模式下的一种结构——堆。

---

1 堆的概念

堆分为大堆和小堆，小堆是指每个父节点的值都小于子节点，大堆是子节点的值都大于父节点，

小堆是这样的，大堆同理就可以了。

堆在逻辑上是完全二叉树结构，实际的物理结构是数组，接下来就进入到重点——堆的实现。

---

2 堆的实现

实现堆的时候，我们不像之前实现顺序表的时候，有增删查改以及指定位置的删除增加等等，因为堆单纯用来存储数据是没有太大的意义的，所以实现的接口也不大一样。

堆同样用结构体定义，一个是数据，一个是空间大小，一个是有效数据个数。

typedef int HDataType;typedef struct Heap
{HDataType* arr;int size;int capacity;
}Heap;//堆的初始化
void HPInit(Heap* php);//建堆
void HPInitArray(Heap* php，HDataType* a, int n);//堆的销毁
void HPDestroy(Heap* php);//堆的插入
void HPPush(Heap* php,HDataType x);//获取堆顶数据
HDataType HPTop(Heap* hp);//堆的删除数据
void HPPop(Heap* php);//堆的判空
bool HPempty(Heap* php);//堆的向上调整算法
void AdjustUp(HDataType* arr,int child);//堆的向下调整算法
void AdjustDown(HDataType* arr,int size ,int parent);

2.1 堆的初始化和销毁

销毁和初始化与之前线性表的初始化基本上就是一样的，不用过多介绍

void HPInit(Heap* php)
{assert(php);php->arr = NULL;php->capacity = php->size = 0;
}

//堆的销毁
void HPDestroy(Heap* php)
{assert(php);free(php->arr);php->arr = NULL;php->capacity = php->size = 0;
}

2.2 获取堆顶数据和堆的判空

获取数据只需要判断堆是不是空的就行，判空只需要检查size的值就可以了。

bool HPempty(Heap* php)
{assert(php);return php->size == 0;
}

//获取堆顶数据
HDataType HPTop(Heap* php)
{assert(php);assert(!HPempty(php));return php->arr[0];
}

因为后面的向上调整和向下调整，我们对于数据的交换用的是很频繁的，所以我们单独创建一个函数用来交换数据：

//交换数据
void Swap(HDataType* px, HDataType* py)
{HDataType tem = *px;*px = *py;*py = tem;
}

2.3 堆的向上调整算法

堆的向上调整算法，即是我们插入数据之后，保持数据的结构依然是堆，所以向上调整就是从最后一个数据入手，往上依次调整，如果堆是小堆，那么就是子节点与父节点比较大小，子节点小于父节点，就交换，大堆同理可得。

那么向上调整，我们知道子节点，如何求的父节点呢？

其实通过节点之间的存储规律，我们可以得到

左子节点 = 父节点 * 2 + 1，右子节点 = 父节点 * 2 + 2；

知道任意子节点我们就可以求父节点，实际操作的时候我们求父节点的时候怎么知道子节点是左还是右呢？

解决方法就是不管三七二十一，父节点 = (子节点 - 1)  / 2，不管多出来的1，因为整型运算，1 / 2 = 0，所以1是被忽略了。

因为调整的次数可能不止一次，可能调整到高度的一半就停止了，或者是调整到了根部，所以我们使用while循环，循环条件就是子节点的下标，因为经历一次调整后，子节点会到父节点上，父节点又到该节点的父节点上，那么判断条件就应该是子节点的下标位置。

//堆的向上调整算法
void AdjustUp(HDataType* arr, int child)
{int parent = (child - 1) / 2;//注意大小堆的写法while (child){if (arr[child] < arr[parent]){Swap(&arr[child],&arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}	
}

2.4 堆的向下调整算法

如果说向上调整算法是从子节点入手，那么向下调整算法就是从父节点入手，父节点和子节点相互比较必然存在一个问题就是，子节点可能只能只有左节点，没有右节点，那我们还要考虑的是两个节点谁小的问题，父节点与两个子节点较小的节点比较，这里可以用到假设法解决。

传进去的参数是数组，堆的有效数据个数，父节点的下标。

这里同样用到while循环，因为是从上往下调整的，所以结束条件应该是child。

为什么是child而不是parent呢？因为调整到最后两层的时候，parent在倒数第二次就不用动了，已经调整结束了，所以向下调整比向上调整有一个明显的优势是在于最后一层不是干涉，时间复杂度会少很多很多，后面再介绍。

假设法找两个子节点中小的那个，为了防止存在越界访问，比如只有一个左孩子，但是child + 1就访问到了右孩子，就越界了，所以child + 1  < size就是为了防止越界访问的。

最后就是进行比较，交换，赋值了。

//堆的向下调整算法
void AdjustDown(HDataType* arr, int size, int parent)
{int child = parent * 2 + 1;//为什么不用child当作循环条件呢？while (child < size){//先找两个孩子中小的那个 假设法if (arr[child + 1] < arr[child] && child + 1 < size){child++;}//交换if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

2.4 堆的插入

 堆的插入很简单的，就跟顺序表的插入一样的， 无非是最后要保持数据依然是堆而已，因为数据是在最后位置插入的，所以可以用向上算法进行调整，前面就是判断空间够不够，不够扩容就行，就没其他要注意的：

//堆的插入
void HPPush(Heap* php, HDataType x) 
{assert(php);//判断空间是否足够if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HDataType* tem = (HDataType*)realloc(php->arr, sizeof(HDataType) * newcapacity);if (tem == NULL){perror("realloc fail");return;}php->arr = tem;php->capacity = newcapacity;}php->arr[php->size++] = x;//插入后依然保持为堆AdjustUp(php->arr,php->size - 1);}

2.5 删除堆顶数据

删除数据都是删除的堆顶数据，那么删除了之后我们该如何保持堆依然是大小堆呢？我们不能直接然后面的数据往前移动一位，这会让堆的数据完全乱套的，结构完全变化了。

前人是思路很是清奇的。我们不妨让第一个数据和末尾的数据进行交换，size--后，堆顶的数据就被删除了，问题是如何保持堆的结构呢？你看，向下调整这不就有大用了，从堆顶一直往下调整呗就，很清奇的这个思路，一下就删除好了。

结合这个思路，如果我们想要找最小，次小的数据是可以模拟这个思路的，后面介绍咯。

当然，没有数据肯定就不能删除了。

//堆的删除数据  删除的是堆顶数据
void HPPop(Heap* php)
{//数据删除之后依然保持为堆assert(php);assert(!HPempty(php));Swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;AdjustDown(php->arr,php->size,0);
}

2.6 建堆

建堆有两个方法，一个是初始化一个堆之后，进行插入数据，调整操作，还有一种就是，初始化的这个过程就进行调整数据，即创建好一个满足堆需求的数组，再拷贝上去就行。

数据给好之后，该赋值的也都要赋值，然后就是调整数据部分，我们可以选择向上调整也可以选择向下调整，至于效率，是向下调整优先的，所以向上调整一般用的是比较少的，后面介绍。

//建堆
void HPInitArray(Heap* php,HDataType* a,int n)
{assert(php);php->arr = (HDataType*)malloc(sizeof(HDataType) * n);if (php->arr == NULL){perror("malloc fail!");return;}memcpy(php->arr, a, sizeof(HDataType) * n);php->capacity = php->size = n;//向上建堆//for (int i = 0; i < n; i++)//{//	AdjustUp(php->arr,i);//}//向下建堆for (int i = (php->size - 1 - 1) / 2; i >= 0; i--){AdjustDown(php->arr, php->size, i);}
}

向下建堆有个要注意的点就是i = php->size - 1 - 1，这是为了防止越界访问，假设堆里面只有9个元素，传进去的i就是4，进入到向下调整之后，child = 9，可是这是size指向的位置，一访问就越界了。

---

3 建堆的时间复杂度

建堆无非就两种方式，向上建堆和向下建堆，两种方式看似相差不大，实际上时间复杂度是相差较大的，这里就来慢慢分析：

计算时间复杂度之前，我们不妨计算一下树的高度与节点个数之间的关系：
二叉树的节点是以二次方递增的，第一层有2^0个节点，第二层有2^1个节点……第h层有2^(h - 1)次方个节点，那么总节点个数N = 2^0 + 2^1 + 2^3 + …… + 2^(h - 1)，这里使用高中的等比求和公式，可以得出，N = 2^h - 1，那么h = log(N + 1)。

3.1 向上建堆的时间复杂度

时间复杂度估算，即是估算每个节点执行多少次操作，第一层的节点，执行调整操作次数至多为0次，第二层1次，第三层2次，第四层3次，第h层 h -1 次。

总的执行次数就是该层的所有节点 * 该层节点执行的至多次数.

F( h ) = 2^0 * 0 + 2 ^ 1 * 1 + 2 ^ 2 * 2 + 2 ^ 3 * 3  + …… +2 ^ (h - 1) * (h - 1)，这里利用高中的错位相减，可以得到F(h) = 2^(h - 2) + 2，那么F(N) = ( N  + 1 ) * (log( N + 1) - 2)  + 2。

所以向上建堆的时间复杂度就是O(N) = N * log(N)。

3.2向下建堆的时间复杂度

同3.1，向下建堆与向上建堆不一样的是向下建堆止步于倒数第二层，这就是为什么向下建堆算法优于向上建堆算法。

节点向下调整至多调整到倒数第二层，所以第一层的节点执行的次数为h - 1，第二层为h - 2，倒数第二层执行的次数为1次，所以:
F(h) = 2^0 * (h - 1) + 2 ^ 1 * (h - 2) + 2 ^ 2 * (h - 3) + …… + 2 ^ (h-1) * 1，结合高中的数学知识可以得到F(h) = 2^h - h - 3，F(N) = (N + 1) - log( N + 1) - 3.

所以向下建堆的时间复杂度就是O(N) = N - log(N)。

这样看来向下建堆的效率远高于向上建堆的效率。

---

4 堆的排序

堆用来存储数据意义不大，排序倒是有点意思，当我们想让一个数组变成升序，我们是大堆还是小堆呢？ 一般来说，小堆就是子节点大于父节点，满足升序，但是实际操作发现哪哪儿都是坑，特别容易改变结构。

面的删除操作有着异曲同工之妙，我们实现升序就选择大堆，讲堆顶数据放在最后,size--就访问不了最大的数据，然后选出第二大的数据，再交换，再size--，再选择第三大的数据，再交换，再size--，重复操作，最后就实现了堆排。

//堆排
void HPsort(HDataType* arr, int size)
{for (int i = (size - 1 - 1); i >= 0 ; i--){AdjustDown(arr,size,i);}int end = size - 1;while (end){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}
}

---

感谢阅读！