大佬们点点关注，点点赞？！

前言

在上篇博客中我们已经介绍了树和二叉树的相关概念，相信大家都已经清楚了树和二叉树的基本思想，下面我们就来着重看看二叉树堆的实现。

在看堆的实现，我们先看看二叉树的顺序存储

一  二叉树的顺序存储

二叉树的顺序存储就是以顺序表来实现的，也就是把二叉树装进数组中去实现，其中坐标代表着各个结点的位置，这里我们用到一个二叉树的性质，也就是上篇博客的性质4。如果我们存的二叉树的的结构不是完全二叉树或者是满二叉树，那么就会有空间的浪费。

那就会有人问了，为啥空的地方不存储呢， 这也是我们的性质4的原因，因为我们在存的时候，需要找的孩子结点，或者父亲结点，他们的下标很重要

比如知道父亲坐标找孩子：leftchild=parent*2+1，rightchild=parent*2+2;

知道孩子坐标找父亲：parent=(leftchild-1)/2; 这里不需要判断是左孩子还是右孩子，因为这里是向下取整（因为int型向下取整的特点），所以得到的结果都是一样的。

所以如果用顺序存储最好是完全二叉树比较好，这样避免了空间的浪费，在操作中用数组存储的也就只有完全二叉树，这也从而让堆实现起来！

二  堆的概念

这里的堆和操作系统里面的堆是两个东西，一个是数据结构，一个是管理系统的一块分区，这里要区分开来

现在有一段数据，然后我们把这些数据按完全二叉树的形式存储到我们的数组中，如果这组数组拆分成二叉树，符合父亲结点大于孩子结点的我们称之为大堆，反之称为小堆。

三  堆的性质

1.堆的某个结点值总是不大于或者不小于其父亲结点的

2.堆总是完全二叉树

3.堆中的结点如果没有左孩子，那么肯定没有右孩子

4.堆不一定有序

四  堆的实现

4.1 结构体的创建

首先堆是用顺序结构实现的，所以我们用的结构也就是和顺序表的形式是一样的

typedef int HeapDataType;
typedef struct Heap
{HeapDataType * a;int size;//当前大小int capacity;//容量
}Heap;//这里和顺序表一样

4.2  堆的初始化和销毁

这里的初始化也可以直接给空间，看个人的喜好

void HeapIint(Heap* hp)
{assert(hp);//断言，因为hp不可能为空hp->a = NULL;hp->size = 0;hp->capacity = 0;
}

void HeapDestory(Heap* hp)
{assert(hp);free(hp->a);hp->a = NULL;hp->size = 0;hp->capacity = 0;
}

4.3  堆的插入

堆的插入，也就是在最后面插入一个数据，这个数据插入以后，这个堆就不是堆了，因为如果是小堆，我们插入的数据比根节点还小，那么这就不符合堆的性质，所以我们需要向上调整这个算法

向上调整的算法思路就是 把这个插入的数据和他这条路径上的所有数进行比较，如果小那么就交换，最终把破坏的结构恢复过来，也就是8，16，12这条路径，其他的没影响

向上调整需要用到父亲结点，也就是我们插入的是孩子，所以我们需要用孩子的坐标算出父亲的坐标

void HeapPush(Heap* hp, HeapDataType x)
{assert(hp);if (hp->size == hp->capacity)//开辟空间{int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;//HeapDataType* tmp = (HeapDataType*)realloc(hp->a, sizeof(HeapDataType) * newcapacity);if (tmp == NULL){perror("malloc fail");return;}hp->a = tmp;hp->capacity = newcapacity;}hp->a[hp->size] = x;//放入数据hp->size++;AdjustUp(hp->a, hp->size - 1);//向上调整//这里的参数一个是数组，一个是插入数据的坐标
}

4.4  向上调整算法 

void AdjustUp(HeapDataType* a, int child)
{int parent = (child - 1) / 2;while (child>0)//当孩子在第一个位置的时候也就没必要比较了所以是>0{if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//交换函数，进行交换child = parent;//换位置，继续比较parent = (child - 1) / 2;}else{break;//如果符合堆的性质，那么不玩了，直接退出来就行}}
}

这里while的条件判断可能有的人会用parent>=0去比较，这虽然可以，但是纯属巧合，具有风险，这里还是推荐使用上面的条件判断

这里函数的参数没用传堆的结构，只是传了一个数组的结构，这是因为这个的算法应用面比较广，所以不能限制死了

4.5  交换函数

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

4.6  堆的删除 

这里堆的删除如果是删最后一个元素那么就会变的毫无价值，所以我们删除第一个元素！！

如果我们删除第一个元素，那么我们的堆也就被破坏了，有两种方法，第一种也就是挪动覆盖，和数组一样，但是这样第二个元素就变成了根结点，那么他的兄弟就变成了他的儿子？！然后我们再重新建堆，因为他们的关系全乱了，所以只能这样，建堆也就是上面的操作想想都复杂。

假如之前的堆是这样的，那么调整挪动后就变成这样了

很明显这已经是发生了很大的改变。

第二种方法就是向下调整，也就是不删除第一个元素，先把他和最后一个元素交换，把最后一个元素删除，然后再让第一个元素向下调整比较，比他小的就交换（因为是小堆），最后形成的结构还是小堆，同时也成功把第一个元素删除了

void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));Swap(&hp->a[0], hp->a[hp->size - 1]);//交换，然后删除最后一个元素hp->size--;AdjustDown(a, hp->size, 0);
}

 4.7  向下调整算法

这里的我们得到的是父亲结点，需要算出孩子结点，所以我们传参的时候传父亲的下标，同时由于在比较过程中需要有一个跳出循环的条件，所以我们需要把n传进去

void AdjustDown(HeapDataType* a, int n, int parent)
{int child = parent*2+1;while (child<n)//如果孩子都大于等于n了，说明比较已经到最后了，也没必要比了，再比就越界了{if (child + 1 < n && a[child + 1] < a[child])//这里需要算出哪个孩子比较小（小堆）//child+1就是右孩子//同时右孩子可能不存在，所以要有前面的判断条件{child++;}if (a[child] < a[parent])//下面的就和向上调整的算法差不多了{Swap(&a[parent], &a[child]);parent = child;child = parent*2+1;}else{break;}}
}

有了上面的操作，那么下面的操作也就变得比较简单了

4.8  取堆顶元素 

HeapDataType HeapTop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));return hp->a[0];
}

4.9  堆的数据判空

bool HeapEmpty(Heap* hp)
{assert(hp);return hp->size == 0;
}

4.10  堆的测试

 

int main()
{Heap hp;HeapIint(&hp);int a[] = { 12 ,15, 16, 30, 45, 25, 8 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(&hp, a[i]);//把数据一个个插入进去，最终形成堆}while (!HeapEmpty(&hp)){int top = HeapTop(&hp);//取出第一个元素cout << top << " ";//打印HeapPop(&hp);//然后删除第一个元素，但是后面还是保持堆，因为采取了向下调整去维护}HeapDestory(&hp);return 0;
}

打印结果： 8 12 15 16 25 30 45

但是我们的本意是堆排序，并不是把这堆数据打印出来，所以我们可以这样

int main()
{Heap hp;HeapIint(&hp);int a[] = { 12 ,15, 16, 30, 45, 25, 8 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(&hp, a[i]);}int i = 0;while (!HeapEmpty(&hp)){a[i++] = HeapTop(&hp);//把取出来的数据放进数组里面去HeapPop(&hp);}HeapDestory(&hp);for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){cout << a[i] << " ";}return 0;
}

 但是我们又会发现这样是不是太麻烦了每次都要建一个堆，才能排序

那我们就有了下面的方法

五  堆排序

5.1  向上调整建堆

假设给定一个数组，那么我们从第二个元素开始，依次去比较，比如先给第一个元素，那么这肯定是个堆。然后给第二个元素，和第一个元素比较，比较完以后，那么这个还是一个堆，然后依次放入元素，最后就形成了堆，并且还是在数组里面的

	for (int i = 1; i < n; i++)//第一个元素不用比较，所以从第二个元素开始{AdjustUp(a, i);}

5.2  向下调整建堆

向下调整建堆我们需要从最后一个父亲结点开始， 因为最后的元素肯定都是叶结点，开始的时候他们不用去比较。比较完以后，那么当前的子树就是一个堆，那么继续往向上一个结点去向下调整，最后只剩根结点，然后进行一次向下调整即可

for (int i = (n - 1 - 1) / 2; i >= 0; i--)//从最后一个父亲结点开始{AdjustDown(a, n, i);}

可能图画的比较抽象，但是画的没错！

既然有两种方法那可能有一个快一个慢，这里可以直接得出向下调整比较快时间复杂度为O(N),向上调整是N*O(logN);至于具体的解释这里就不说明了，自己也可以感觉一下，假如叶子结点有N个，那么向上调整会比向下调整的要多

5.3  排序 

建完堆以后我们就要开始排序了，排序用向下调整算法，因为向下调整可以选出最大的和最小的数，因为他可以跟他的左右孩子比较，向上调整就不具备这样的优势

	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是一直在变动的，因为排好的元素不需要进行比较了end--;}for (int i = 0; i < n; i++)cout << a[i] << " ";
}

如果是升序：建大堆

如果是降序：建小堆

因为后面的排序会把第一个元素放到后面，所以排完以后，就会变成有序的序列 

 

5.3  topK问题

如果我们要求从一个数组中选出前k个最大的数或者最小的数，那么我们的思路是直接建立一个大堆然后依次pop9次就行，因为最后一个不用pop，直接拿出来就行，每次pop,都是最大的数所以能够完成，虽然这行得通，但是如果是几亿的数，这种方法也会很慢

所以有了下面的改进

我们可以先建立一个k个数的小堆，然后与后面N-k个元素进行比较，不满足就替换堆顶元素，然后先下调整，这里调整的范围是K，不是N,所有比较大的数会在这个小堆的底部，最后形成一个k个数最大的小堆

	for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, k, i);//建小堆}for (int i = k; i < n; i++){if (a[i] > a[0])//选出k个最大的数{a[0] = a[i];AdjustDown(a, k, 0);}}for (int i = 0; i < k; i++)cout << a[i] << " ";
}

以上便是堆排序的全内容 希望大家喜欢，都看到这里了