
#pragma once
#include <iostream>
#include <assert.h>
#include <stdlib.h>
using namespace std;
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

2.3向上调整（找祖先）（常用于堆的插入）

在堆的插入中：插入之前先分清楚是什么堆且插入的时候一定是往后插入不可以改变堆的结构。

这个时候数组下标公式的意义就体现出来了这里建立一个小根堆

算法思路：（小堆）

1.先将元素插入到堆的末尾，即最后一个孩子之后

2.插入之后如果堆的性质遭到了破坏，将新插入节点顺着双亲往上调整到合适的位置即可

操作步骤：

a[10]->a[(10-1)/2]->比较->孩子小交换->a[4]->a[(4-1)/2]->比较->孩子小交换->a[1]->a[0]->孩子是小元素交换。

结束条件：

parent>0 继续 <0 终止这样写对吗？？会发生死循环

所以利用孩子来进行循环的判断只要孩子>0 那么就接着循环孩子=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) //循环条件的判断是孩子>0
	{
		if (a[child] < a[parent]) 
		{
			//处理数字值
			swap(&a[child], &a[parent]);
			//将父亲的位置给了孩子 上面的函数只换了大小
			child = parent;
			//再令孩子的值-1/2给了父亲
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
	
}

这是建立小堆的向上调整算法若想建立大堆那么循环中的小于改成大于即可

2.4向下调整（常用于能找到次大或者次小堆的删除算法）

条件：左子树右子树是大堆/小堆

在堆的删除中:父子关系和兄弟关系会混乱那么向下调整就出现了（代价低总不能一个一个遍历）

且只要交换堆顶和堆底的数据 --size 再令大的下来写出循环即为堆的删除算法

算法思路：（小堆）

1.寻找小孩子（用来交换）默认认为小孩子是左孩子

2.根节点左看看右看看找到小孩子并判断与之交换若小的孩子比父亲还小，则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。

结束条件：

在循环中孩子的越界条件中已经恰好书写完毕只要找不到小孩子就算结束


void AdjustDown(HPDataType* a, int n,int parent) {
	// 默认小孩子是左孩子
	int minchild = parent * 2 + 1;
	while (minchild < n) { // 担心越界
		// 默认可能有误 && 担心小孩子+1越界
		if (a[minchild + 1] < a[minchild] && minchild + 1 < n) {
			minchild++;
		}
 
		if (a[minchild] < a[parent]) {
			//更新数值
			swap(&a[minchild], &a[parent]);
			//更新下标
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else {
			break;
		}
	}
	
}

其中若将if的< 改为大于就是建立大堆的方法

3.堆排序（N*logN）--复杂度相当小的排序

首先将数组N个数建成一个堆不利用数据结构堆的插入Push自行实现巧了向/上下调整建堆是可以成功建堆的（模拟插入过程）

3.1向上调整建堆


void Heapsort(int* a, int n) {
	for (int i = 1; i < n; i++) {
		AdjustUp(a, i);
	}
}

3.2向下调整建堆

条件：

这个相比于上一个调整是有前提的必须左右都是小/大堆不能凭空使用若左右子树不是堆最后一行是没必要调整的一个叶子元素本身就是堆那么从倒数第一个非叶子节点进行调整（最后一个节点的父亲利用父子下标公式）当前位置调整好后减减即可到前一个位置

//申明：改图来自博主2021dragon

图1~6的解释：

1->2: 89的小标是9 其父亲的下标为4 即10 那么先判断并调整10和89的位置关系

2->3: 找到之后减减操作就就可以找到左边的节点并判断左节点以下的堆是否需要排序

3->4: 继续减减找到76 同时找到小孩子12 且小孩子12比76要小令76下来

4->5: 继续减减 54的小孩子是10 比较后发现也得下调

5->6: 继续减减 23的小孩子是10 继续令23下调


void Heapsort(int* a, int n) {
	for (int i = ((n-1)-1)/2; i >=0; i--) { // 倒数第一个非子叶 最后一个下标为n-1节点的parent 
		AdjustDown(a,n,i);
	}
}

3.3向上/向下建堆复杂度的讲解：

T（n）就是运行时间：节点个数*最多的向下调整层数每一层的相加就是答案

向下调整的时间复杂度：一个高度为h的树，总深度为 log(N+1)

则需要调整的最坏情况也就这么多

向下建堆的复杂度：由错位相减可得，总复杂度为N

向上建堆的复杂度：也可以使用相同的错位相减，但由于最后一层节点及其多，故将最后一层需要调整的次数得出，大方向也就可以得知：第h层有2^h-1个节点需要调整h-1层那么相乘 T（n）约等于 2^h*(h-1) 则向上调整建堆的复杂度为O（N*logN）

向下调整优势的地方在于：节点越多，需要调整的次数越少；越往上虽然调整的次数变多但是需要调整的节点变少且最后一层的节点不需要调整在一个完全二叉树中 最后一层的节点大概占有一半的节点个数

3.4为什么升序不用小堆？？

1.建立小堆2.成本较高的是无法依次找到较小的数这是难点也是开辟空间成本较高的复杂点

3.5为什么升序使用大堆？？

1.建大堆

2.将第一个数字与最后位置（n-i）交换，并且将最后一个不看作堆

3.向下调整选出次大，后续调整的复杂度只有O（logN）的大小，相当的快

下面是第一次交换的代码：


int i = 0;
	while (i < n) {
		swap(&a[0], &a[n - 1]);
		AdjustDown(a, n - 1, 0);
	}

代码解释：交换第一个数字和最后一个位置的数字，并且调整的时候不再是n 而是n-1 不将最后一个数字看作是堆中的元素了

完整代码：为保持一直循环往复的进行，将i的初始值给1，后续最后一个位置用n-i来提替代


void Heapsort(int* a, int n) {
	for (int i = ((n-1)-1)/2; i >=0; i--) {
		AdjustDown(a,n,i);
	}
	//选择数字
	int i = 1;
	while (i < n) {
		swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 0);
		++i;
	}
}

建立升序和降序的控制点在于 AdjustDown中的if大于小于的朝向

若是大于则为大堆就是升序

若是小于则建立的为小堆则为降序

4.Top-K问题寻找N个数前k个最大的

算法思路：替换-->堆顶元素和后续遍历的N-K个数字替换；筛选-->向下调整

1.堆排序--O（N*logN）

2.堆选数

寻找前k个，虽然无序但本质上也可以理解为降序，那么就是建立小堆

3.用前K个数建立K个数的小堆

4.依次遍历后续N-K个数，比堆顶的数据大，就替换堆顶数据，向下调整进堆，这样就可以保证这K个数是前K个最大的（只要是最大的前K个来了，就会和堆顶替换，同时这个堆中也会向下调整把较大的扔下去，堆顶元素是混子本身，将其替换筛选）


void AdjustDown(HPDataType* a, int n, int parent) {
	// 默认孩子
	int minchild = parent * 2 + 1;
	while (minchild < n) { // 担心越界
		// 默认可能有误 && 担心小孩子+1越界
		if (a[minchild + 1] < a[minchild] && minchild + 1 < n) {
			minchild++;
		}
		if (a[minchild] < a[parent]) {
			//更新数值
			swap(&a[minchild], &a[parent]);
			//更新下标
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else {
			break;
		}
	}
} // 这里是小于 因为要建立小堆
void PrintTopK(HPDataType* a, int n, int k)
{
	// 建k个数小堆
	for (int parent = ((k - 1) - 1) / 2; parent >= 0; --parent) {
		AdjustDown(a, k, parent);
	}
	// 继续读取后N-K
	for (int i = k; i < n; i++) {
		int val = a[i];
			if (val > a[0])
			{
				a[0] = val;
				AdjustDown(a, k, 0);//调整的是堆顶的元素
			}
	}
	for (int i = 0; i < k; ++i)
	{
		printf("%d ", a[i]);
	}
}
 
int main()
{
	int a[] = { 1,5,6,7,8,10,421421414,5 };
	int n = sizeof(a) / sizeof(int);
	int k = 3;
	PrintTopK(a, n, k);
	return 0;
}

5.堆的基本操作（插入删除是重点）

5.1初始化

堆的类型包括存储数据的数组，堆中元素的个数，当前堆的最大容量


typedef int HPDataType;//堆中存储数据的类型
 
typedef struct Heap
{
	HPDataType* a;//用于存储数据的数组
	int size;//记录堆中已有元素个数
	int capacity;//记录堆的容量
}HP;
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

5.2销毁堆


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

5.3打印堆


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

5.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");
			exit(-1);
		}
 
		php->a = tmp;
		php->capacity = newCapacity;
	}
 
	php->a[php->size] = x;
	php->size++;
 
	AdjustUp(php->a, php->size - 1);
}

5.5堆的删除

堆的删除，删除的是堆顶的元素，但是这个删除过程可并不是直接删除堆顶的数据，而是先将堆顶的数据与最后一个结点的位置交换，然后再删除最后一个结点，再对堆进行一次向下调整。

原因：若是直接删除堆顶的数据，那么父子关系就全部打乱了，需要全体重新建堆。若是用上述方法，那么只需要对堆进行一次向下调整即可，因为此时根结点的左右子树都是小堆，我们只需要在根结点处进行一次向下调整


void AdjustDown(HPDataType* a, int n, int parent)
{
	int minChild = parent * 2 + 1;
	while (minChild < n)
	{
		// 找出小的那个孩子
		if (minChild+1 < n && a[minChild + 1] < a[minChild])
		{
			minChild++;
		}
 
		if (a[minChild] < a[parent])
		{
			Swap(&a[minChild], &a[parent]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

5.6获取堆顶元素


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

5.7堆的判空


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

5.8获取堆顶元素


int HeapSize(HP* php)
{
	assert(php);
 
	return php->size;//返回堆中数据个数

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/900782

详详详解堆调整算法及TOP-K 尾附：堆基本实现_最大堆调整过程

1.什么是堆？？

堆就是一种完全二叉树

其中数组下标计算父子关系公式显得尤为重要：

堆的分类

2.向上/下调整算法

2.1算法意义

2.2初始化操作