我家自动化

这个屌丝很懒，什么也没留下！

热门标签

二叉树和堆的相关知识点

作者：我家自动化 | 2024-08-07 17:48:28

踩

二叉树和堆的相关知识点

树

树的相关概念

二叉树是一种特殊的树，二叉树依然是树的子集，所以讲二叉树前，我们首先谈谈树。

树：树是一种非线性的数据结构，它是由n（n>=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）棵互不相交的树的集合称为森林；

有时候你可能听过一句话，说：树是递归定义的。该怎么理解呢？我们说递归是用来不断将问题分为若干个更小的问题，直到问题成为不可分割的子问题，对应树这边，就是树可以分为根和若干子树，它的子树又可以再分为根和若干子树，直到一个子树只剩下根，无法再继续分割子树。

树的表示方法

树的结构相对线性表就比较复杂了，所以存储表示起来比较麻烦，树的每个节点既要保存有效数据，也要保存结点和结点之间的关系，那该如何表示一个节点呢？

指定树的度

树中每个根节点的子树数量不固定，指定一个树的度后，比如树的度为6，如下图就是一个节点的表示方法。

当然，因为每个节点不一定都有6个子树，因此这种定义方法虽然没错，但会存在空间浪费的问题。

不指定树的度有两种表示方法

方法一：

此方法本质是手搓一个能够动态开辟内存的顺序表，当前节点有几个子树，则就malloc出几个指向【当前节点的子树根节点】的指针，所以当前方法定义节点无需指定树的度。

上图左边定义了一个指向struct TreeNode*类型数据的指针childArray，意为当前节点有几个子树，则就malloc开辟几个struct TreeNode*的指针的空间，每一个指针都指向当前节点不同子树的根节点，因为这几个指针自身4字节的物理空间是malloc出的连续的物理空间，所以可以将这些指针集合视为一个数组，我们最终是通过指向物理空间中第一个指针的childArray指针管理该数组。

上图右边就是先实现一个顺序表SeqList，然后让它动态开辟内存存储指向【当前节点的子树根节点】的指针。

当前方法的缺点也很明显，就是需要手搓一个顺序表，我们学了C++后，就可以直接使用STL内的容器vector来更好的完成这里节点的定义，如下图所示。

方法二：

通过firstChild1指针往下层遍历，通过pNextBrother指针往同一层的右边遍历。可以看到这种定义节点的方法与之前指定树的度时所定义节点的方法相比，很好的节省了内存。

二叉树

特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1，则它就是满二叉树。（K是从1开始的）

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树（K是从1开始的）。说简单点也就是除了最后一层外，其他每一层都必须是挂满节点的状态，最后一层不要求挂满，但节点必须从左到右是连续的。可以发现如果按这个理论，那满二叉树也是一种特殊的完全二叉树，事实上也的确如此。

二叉树的性质与练习

我们看两个题来运用这些性质。

题1：

n0表示度为0的节点，n1表示度为1的节点，n2表示度为2的节点，上图问题也就是求n0的个数。通过二叉树的性质3能得到n2=n0-1，通过完全二叉树的概念我们能得出最多有一个度为1的节点（也就是说可能有一个、也可能没有，n1要么为1、要么为0），2*n0=2n-n1+1，如果n1为0，则n0算出来为小数，因此n1只能为1，最后n0就等于n了。

题2：

节点范围是怎么算的呢？

假如高度为h，注意h最小为1，因为满二叉树也是特殊的完全二叉树，因此节点总数的最大值是2^h-1，最小值当然是第h层只有1个节点，前面每一层都挂满了节点的时候，2^（h-1）-1表示前h-1层每一层节点相加的总和，1就是第h层节点的总数，因此此时节点数量为2^（h-1）-1+1，也就是2^（h-1）。所以层数为h，h最小为1时，节点数量的范围为【2^（h-1），2^h-1】，有了范围，答案也就好选了，最终选B。

题3：

题解和题1一致，不再赘述。

二叉树的物理存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

当学完二叉树的存储结构后，我们以后就不能一看到二叉树的抽象图，发现节点之间是线连起来的，就认为二叉树的节点都是通过链表连接起来的在物理空间上不连续的空间，而应该知道我们所说的二叉树是指一个个节点在逻辑空间上的结构犹如二叉树、所画的抽象图都是逻辑空间上的样子，在物理空间上节点如何存储是不确定的，比如二叉树的顺序存储方式就是通过一个数组，也就相当于说这个数组本身就是一颗二叉树。

1. 顺序存储

顺序结构存储就是使用数组来存储，一般只有完全二叉树会使用顺序存储的方式，也就是只有完全二叉树适合被数组表示，普通的二叉树是不适合用数组来存储的，因为不是完全二叉树会有空间的浪费，但注意即使不是完全二叉树，也是可以用数组存储的。现实中我们通常把堆(所有堆都是完全二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段，详情请见下文。

在顺序结构存储非完全二叉树时，数组一定要给空节点存空值，不能为了节省空间而只存储非空节点，否则就无法根据数组的物理空间反推二叉树的逻辑空间了。

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

顺序存储的优势：可以通过下标计算父子间的关系，注意下标是从0开始的，如下图所示。有人可能会疑惑，既然我右孩子的下标是通过2*parent+2得到的，那通过右孩子下标计算父亲节点的下标时，应该是(child-2）/2才对啊，为什么下图写的是parent=（child-1）/2呢？这是为了提供一种统一的方式计算父亲节点的下标，即不管左孩子还是右孩子，只要你是孩子节点，那就可以通过（child-1）/2得到父亲节点的下标。首先能发现一个规律，奇数下标永远是左孩子，偶数下标永远是右孩子，如果下标为奇数，也就是左孩子时，本身计算父亲节点下标时就应该是（child-1）/2，而当下标为偶数，也就是右孩子时，比如下标为6，你可以发现(6-2）/2和（6-1）/2的值是相同的，所以为了让【通过左孩子下标计算父亲节点下标的方式】和【通过右孩子下标计算父亲节点下标的方式】统一，就干脆决定，不管是左孩子还是右孩子，都使用parent=（child-1）/2计算自己父亲节点的下标。

2.链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出当前结点左孩子和右孩子链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面学到高阶数据结构如红黑树等会用到三叉链。

问题：为什么要存在链式存储呢？直接用顺序存储不好吗？

答案：前面已经说过了，如果用顺序存储的方式即数组去存储一颗逻辑空间上不为完全二叉树的二叉树，会导致数组中很多空间的浪费，如下图红色箭头指向空间就全是浪费掉了。所以当一颗二叉树不为完全二叉树，有很多空节点时，此时最佳的存储方式应是链式存储，这样如果当前节点没有左孩子或者右孩子，无需为孩子开辟空间创建节点，直接让当前节点对应的指针指向nullptr即可。

二叉树的遍历

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点最多只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

前序、中序以及后序遍历

按照规则，二叉树的遍历有：前序 / 中序 / 后序的递归结构遍历：
1. 前序遍历(Preorder Traversal亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

堆

概念以及性质

堆是一个底层物理结构为一维数组，逻辑结构为完全二叉树的结构。

大根堆和小根堆的示例如下图所示。

堆的基础框架


typedef int HPDataType;
typedef struct heap 
{
	HPDataType* a;
	int size;//表示数组中最后一个有效数据后一个位置的下标
	int capacity;//表示数组中最后一个可存储数据的位置的后一个位置的下标
}HP;
 
void HeapInit(HP* hp); 
void HeapDestory(HP* hp); 
void HeapPush(HP* hp, HPDataType x);
void HeapPop(HP*hp);
HPDataType HeapTop(HP* hp);
bool HeapEmpty(HP*hp);
size_t HeapSize(HP* hp);

加入size和capacity是因为heap这个逻辑空间为完全二叉树的结构底层的物理空间是一个数组，当不断往heap中新插入元素时，如果数组满了则需要扩容。

HeapInit和HeapDestory函数


typedef int HPDataType;
typedef struct heap 
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
 
void HeapInit(HP* hp)
{
	assert(hp != NULL);
	hp->a = NULL;
	hp->size = hp->capacity=0;
}
 
 
void HeapDestory(HP* hp)
{
	assert(hp != NULL);
	free(hp->a);
	hp->a = NULL;
}

HeapPush（下面AdjustUp的代码是以建立小堆为目的去调整节点的）

问题：如上图，假如有一个新节点需要插进堆中，节点的有效数据为8，那应该插在哪呢？这个过程是怎样的呢？

注意在调用HeapPush插入一个新节点时，如果插入前，其他所有节点共同形成的结构就不是一个堆，那么插入新节点后，也不可能形成一个堆，因此调用本接口插入新节点的前提是：在插入新节点前，其他所有节点共同形成的结构已经是一个堆（大根堆或者小根堆）了。

答案：首先要知道在插入节点8前，其他节点形成的逻辑结构就已经是一个小根堆了，为了保证堆的性质【堆总是一棵完全二叉树】不被破坏，因此8在逻辑空间上只能插在如上图中的位置，对于该逻辑空间对应的物理空间来说，因为当前的物理空间底层是一个数组，所以在物理空间上只能插在数组最后一个元素的后一个位置，代码如下所示。


typedef int HPDataType;
typedef struct heap 
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
 
void HeapPush(HP* hp, HPDataType x)
{
	assert(hp != NULL);
	//如果满了就扩容
	if (hp->capacity == hp->size)
	{
		size_t newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
		//当hp->a为NULL时，realloc等价于malloc，当hp->a不为NULL时，扩容后会将原有数据从头到尾拷贝到新分配的内存区域，因此无需memcpy
		HPDataType* temp = (HPDataType*)realloc(hp->a, newcapacity * sizeof(HPDataType));
		if (temp == NULL)
		{
			printf("realloc failure");
			exit(100);
		}
		hp->a = temp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
 
	//未编写完毕
 
}

同时为了保证堆的性质【堆中某个节点的值总是不大于或不小于其父节点的值】不被破坏，8这个节点是需要向上调整的，调整后这颗逻辑结构为完全二叉树的结构才能又成为一个小堆，那么如何向上调整呢？

之前说HeapPush插入新节点的前提是：在插入新节点前，其他所有节点共同形成的结构已经是一个堆（大根堆或者小根堆）了。

实际上从本质来说，不是HeapPush要求有这个前提，而是AdjustUp向上调整需要这个前提，要求被调整的节点在AdjustUp向上调整前，其他所有节点共同形成的结构就已经是一个堆（大根堆或者小根堆）了，否则向上调整这个算法就没有意义，因为即使将新插入的节点向上调整后，所有节点形成的结构依然不是一个堆，反之，如果在调整新插入的节点前，其他所有节点共同形成的结构已经是一个堆（大根堆或者小根堆）了，那么AdjustUp新节点后，所有节点形成的结构一定还是一个堆。

观察上图能够发现，因为在插入节点8前，其余节点形成的结构就已经是一个小根堆了，因此插入8后，节点8不会对兄弟节点造成任何影响，而只会影响它的祖先节点，如上图黄框圈出来的部分。一个节点在向上调整时，最坏的结果是节点移动到堆顶，也有可能移动到中间就停止，这里因为8每一次调整时都小于父亲节点，因此是得一直向上调整的，流程图如下所示。

向上调整最多调整高度次，因此AdjustUp的时间复杂度为O（logN），N表示完全二叉树中的节点总数。

如何用代码体现这一过程呢？HeapPush最终版本的代码如下所示。

注意为什么AdjustUp的第一个参数是HPDataType*即int*，而不是HP*呢？这是为了堆排序做准备，如果参数为HP*，则AdjustUp只能调整堆这种数据结构里自带的malloc出的数组，不能调整普通数组中的数据了。


typedef int HPDataType;
typedef struct heap 
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
 
//建小堆版本的AdjustUp，a表示调整哪个堆，pos表示调整哪个节点
void AdjustUp(HPDataType* a, size_t pos)
{
	//堆在逻辑空间上是一个完全二叉树，而二叉树如果采用顺序存储方式，则可以通过下标计算父子关系
	size_t parent = (pos - 1) / 2;
	while (pos>0)
	{
        //如果pos节点小于父亲节点，就向上调整
		if (a[pos] < a[parent])
		{
			HPDataType temp = a[pos];
			a[pos] = a[parent];
			a[parent] = temp;
			pos = parent;
			parent = (pos - 1) / 2;
		}
        //pos节点大于父亲节点就停止向上调整
		else
			break;
	}
}
 
void HeapPush(HP* hp, HPDataType x)
{
	assert(hp != NULL);
	//如果满了就扩容
	if (hp->capacity == hp->size)
	{
		size_t newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
		//当hp->a为NULL时，realloc等价于malloc，当hp->a不为NULL时，扩容后会将原有数据从头到尾拷贝到新分配的内存区域，因此无需memcpy
		HPDataType* temp = (HPDataType*)realloc(hp->a, newcapacity * sizeof(HPDataType));
		if (temp == NULL)
		{
			printf("realloc failure");
			exit(100);
		}
		hp->a = temp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
 
	//向上调整
	AdjustUp(hp->a, hp->size - 1);
}

测试代码如下

可以发现插入节点8后依然是小堆，代码的运行结果符合预期。


void HeapPrint(HP* h)
{
	assert(h != NULL);
	for (size_t i = 0; i < h->size; i++)
	{
		printf("%d ", h->a[i]);
	}
}
 
 
void main()
{
	int ar[] = { 10,15,56,25,30,70,8 };
	heap h;
	HeapInit(&h);
	int size = sizeof(ar) / sizeof(int);
	for (int i = 0; i < size; i++)
	{
		HeapPush(&h, ar[i]);
	}
	
	HeapPrint(&h);
 
}

有同学可能会有疑惑，前面不是说过调用HeapPush接口的前提是：在插入新节点前，其他所有节点共同形成的结构必须已经是一个堆（大根堆或者小根堆），否则插入后依然无法形成堆吗？测试代码中为什么无脑插入却能形成堆呢？

实际上这里不是无脑插入，因为在最开始时heap中没有元素，而往后每一次插入都是经过了向上调整的，这相当于每次插入前，其他所有节点共同形成的结构已经是一个堆了，所以插入新节点并调整新节点后依然可以形成堆，这也是一种建堆的方法，下文中还会讲解其他建堆的方法，本种不断调用HeapPush去建堆的方法和下文中会讲解的【自上而下的向上调整法】的建堆方式本质是相同的，并且它们的时间复杂度都为O（N*logN），注意时间复杂度中的N表示堆（完全二叉树）中的节点总数。这里分析一下通过不断HeapPush建堆的时间复杂度：有多少个数据就HeapPush多少次，为O（N），HeapPush中可能会AdjustUp向上调整，AdjustUp的时间复杂度为O（logN），所以通过不断HeapPush建堆的时间复杂度为O（N*logN）。

HeapPop（下面AdjustDown的代码以是建立小堆为目的去调整节点的）

HeapPop只能用于删除堆顶的数据，至于为什么不让删除堆中其它位置的节点，笔者认为对于堆这种数据结构来说，删除除堆顶外的其他节点没有什么意义，因为堆顶是极值，其他节点的值啥也不是，如果你想删除任意位置的节点，就不应该用堆这种数据结构去存储数据，而是用链表或者顺序表。

和HeapPush插入节点后要保证节点们形成的结构依然是堆一样，这里删除堆顶的节点后也要保证剩余节点所形成的结构依然是一个堆。

和使用HeapPush有前提一样（本质是使用AdjustUp有前提），使用HeapPop也有前提（本质是使用AdjustDown有前提），要求在删除堆顶元素前，堆顶元素的左子树和右子树就各自已经是一个堆。

假如有一个堆，结构如上图所示，此时要调用HeapPop删除堆顶节点10，那接下来思考一下如何删除10比较好。

可以直接将堆的底层物理存储空间（即数组）中的数据往前挪一次，将10覆盖，然后--size以此删掉10吗？流程图如下所示。

答案：不太合适，首先挪动数据的效率是非常低的，其次挪动数据后会破坏原有的父子关系，导致剩余节点所形成的结构不是一个堆，如上图30比56小，此时就不是一个堆了。

那有人会说，在HeapPop函数中可以有这样的逻辑，将【往前挪动数据后的不符合堆性质】的heap对象A（即下图黄框处所示的数组）中剩余的元素，全部依次HeapPush插到在HeapPop函数中创建的另一个临时heap对象B中，看了上文讲解的HeapPush后我们知道这也是一种建堆的方法，所以此时heap对象B管理的数组是一个真正的堆，然后我们free释放heap对象A管理的数组，并让heap对象A管理heap对象B的数组，临时的heap对象B出了HeapPop的函数作用域后还顺便被销毁了，这样heap对象A不就依然是一个堆了吗？

你的想法是对的，但前面也说过，HeapPop删除堆顶节点通过往前挪动数据这种方法只是不太合适，并没有说他错误，挪动数据的效率已经十分低了，现在还需要将挪动数据后的数组中剩余的元素全部HeapPush到另一个堆中重新形成一个堆，可想而知这效率得低得多么逆天。因此不要用往前挪动数据这样的方法去实现HeapPop。

最合适的实现HeapPop的方法。

首先将【堆顶的数据】和【堆的底层物理存储空间（数组）末尾的数据】交换，然后--size。

流程图如下所示。

代码如下


typedef int HPDataType;
typedef struct heap 
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
 
 
void HeapPop(HP* hp)
{
	assert(hp != NULL);
	assert(hp->size > 0);
	//交换堆顶和数组末尾的数据
	HPDataType temp = hp->a[0];
	(hp->a)[0] = (hp->a)[hp->size - 1];
	(hp->a)[hp->size - 1]=temp;
 
	hp->size--;
    
    //代码未编写完毕
 
}

问题：如上面流程图中70大于15和56，可以发现交换后不满足小堆的性质：父亲节点要小于任意一个孩子节点，因此此时需要向下调整，那么如何向下调整呢？

和使用AdjustUp向上调整法有前提一样，使用AdjustDown向下调整法也是有前提的，要求被调整的节点在调整前，该节点的左子树和右子树就已经是一个堆了，否则向下调整这个算法就没有意义，因为即使向下调整完，节点们形成的结构也不是一个堆，反之，如果正在被调整的节点的左子树和右子树已经是一个堆了，那么AdjustDown后，节点们形成的结构一定是一个堆。

答案：节点70的左子树和右子树都是小堆，只有70为根节点的子树不是小堆，因此只需要将70向下调整即可，流程图如下所示。这里随口一提，如果一个树已经是小堆，那么这个树的任意子树一定也是小堆。比如节点70的左子树是小堆，那么节点70左边的任意一个子树就都是小堆。

AdjustDown最多向下调整高度次，因此时间复杂度为O（logN）。

代码如下所示。

注意为什么AdjustDown第一个参数是HPDataType*即int*，而不是HP*呢？这是为了堆排序做准备，如果参数为HP*，则AdjustDown只能调整堆这种数据结构里自带的malloc出的数组，不能调整普通的数组了。


typedef int HPDataType;
typedef struct heap 
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
 
 
 
//最容易想到，但代码量冗余的建小堆版本的AdjustDonw
 
//a表示在哪个堆里向下调整，pos表示需要向下调整的节点的下标，size表示堆里共有多少个节点，用于判断pos位置节点的孩子节点是否有越界
//void AdjustDown(HPDataType* a, size_t pos,size_t size)
//{
//	//堆在逻辑空间上是一个完全二叉树，而二叉树如果采用顺序存储方式，则可以通过下标计算父子关系
//	size_t leftchild = 2 * pos + 1;
//	size_t rightchild = 2 * pos + 2;
//	size_t minchild;
//	//因为堆是完全二叉树，所以当右孩子存在时，左孩子一定存在
//	if (rightchild < size)
//	{
//		//因为我们建小堆，所以在正在被调整节点的孩子节点中找出更小的那一个孩子，
//		if(a[leftchild] < a[rightchild])
//			minchild = leftchild;
//		else
//			minchild = rightchild;
//	}
//	//当只有左孩子存在时，它就是最小的孩子节点
//	else if(leftchild<size)
//	{
//		minchild = leftchild;
//	}
//	//既没有左孩子也没有右孩子，无需调整
//	else
//	{
//		return;
//	}
//
//	while (minchild<size)
//	{
//		//如果满足条件，则开始交换父子节点
//		if (a[pos] > a[minchild])
//		{
//			HPDataType temp = a[minchild];
//			a[minchild] = a[pos];
//			a[pos] = temp;
//			//交换后还有可能继续向下调整，因此更新新的父子节点的下标
//			//更新父节点下标
//			pos = minchild;
//			//更新孩子节点下标
//			leftchild = 2 * pos + 1;
//		    rightchild = 2 * pos + 2;
//          //再次找出左右孩子中较小的孩子
//			//因为堆是完全二叉树，所以当右孩子存在时，左孩子一定存在
//			if (rightchild < size)
//			{
//				//因为我们建小堆，所以在正在被调整节点的孩子节点中找出更小的那一个孩子，
//				if (a[leftchild] < a[rightchild])
//					minchild = leftchild;
//				else
//					minchild = rightchild;
//			}
//			//当只有左孩子存在时，它就是最小的孩子节点
//			else if (leftchild < size)
//			{
//				minchild = leftchild;
//			}
//			//既没有左孩子也没有右孩子，无需调整
//			else
//			{
//				return;
//			}
//
//		}
//		else
//      //如果父亲节点小于两个孩子节点中较小的孩子节点，则已经是小堆了，无需调整，直接return退出函数即可
//			break;
//	}
//	
//
//}
 
 
//没有之一，AdjustDown的最简洁的仿照源码编写的版本（循环写法）
//建小堆版本的AdjustDonw
//a表示在哪个堆里向下调整，pos表示需要向下调整的节点的下标，size表示堆里共有多少个节点，用于判断pos位置节点的孩子节点是否有越界
void AdjustDown(HPDataType* a, size_t pos,size_t size)
{
	//堆在逻辑空间上是一个完全二叉树，而二叉树如果采用顺序存储方式，则可以通过下标计算父子关系
	//child表示左右孩子中更小的那一个，先默认让左孩子充当child
	size_t child = 2 * pos + 1;
	//如果被调整节点的左孩子存在，则有需要调整的可能，进入循环，若不存在，则不需要向下调整，退出函数
	while (child<size)
	{
		//如果右孩子存在，并且右孩子的值小于左孩子，则让右孩子成为child
		if (child + 1 < size && a[child] > a[child + 1])
			child = child + 1;
		//如果满足条件，则开始交换父子节点
		if (a[pos] > a[child])
		{
			HPDataType temp = a[child];
			a[child] = a[pos];
			a[pos] = temp;
			//交换后还有可能继续向下调整，因此更新新的父子节点的下标
			//更新父节点下标
			pos = child;
			//更新孩子节点下标
			child = 2 * pos + 1;
		}
		else
			//如果父亲节点小于两个孩子节点中较小的孩子节点，则已经是小堆了，无需调整，直接return结束递归
			break;
	}
	
 
}
 
 
//AdjustDown最简洁版本的递归写法
//建小堆版本的AdjustDonw
//a表示在哪个堆里向下调整，pos表示需要向下调整的节点的下标，size表示堆里共有多少个节点，用于判断pos位置节点的孩子节点是否有越界
//void AdjustDown(HPDataType* a, size_t pos, size_t size)
//{
//	//堆在逻辑空间上是一个完全二叉树，而二叉树如果采用顺序存储方式，则可以通过下标计算父子关系
//	//child表示左右孩子中更小的那一个，先默认让左孩子充当child
//	size_t child = 2 * pos + 1;
//	//如果右孩子存在，并且右孩子的值小于左孩子，则让右孩子成为child
//	if (child + 1 < size && a[child] > a[child + 1])
//		child = child + 1;
//
//	//如果更小的孩子child越界，则直接return结束递归
//	if (child >= size)
//		return;
//	//如果满足条件，则开始交换父子节点
//	if (a[pos] > a[child])
//	{
//		HPDataType temp = a[child];
//		a[child] = a[pos];
//		a[pos] = temp;
//		//交换后还有可能继续向下调整，因此更新父亲节点的下标，孩子不用在下面更新，因为进入下一次递归时会更新孩子节点的下标
//		//更新父节点下标
//		pos = child;
//	}
//	else
//		//如果父亲节点小于两个孩子节点中较小的孩子节点，则已经是小堆了，无需调整，直接return结束递归
//		return;
//	AdjustDown(a, pos, size);
//
//}
 
 
void HeapPop(HP* hp)
{
	assert(hp != NULL);
	assert(hp->size > 0);
	//交换堆顶和数组末尾的数据
	HPDataType temp = hp->a[0];
	(hp->a)[0] = (hp->a)[hp->size - 1];
	(hp->a)[hp->size - 1];
 
	hp->size--;
	AdjustDown(hp->a,0,hp->size);
 
}

HeapTop、HeapEmpty和HeapSize

HeapTop就是用于获得位于堆顶的极值（大堆就是最大值，小堆就是最小值）。

HeapEmpty就是用于判断堆是否为空，在逻辑空间上是判断二叉树中是否有节点，在物理存储空间上就是判断实现二叉树的底层数组中是否存在有效数据。

HeapSize就是用于获得堆中有多少节点。


typedef int HPDataType;
typedef struct heap 
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
 
 
HPDataType HeapTop(HP* hp)
{
	assert(hp != NULL);
    assert(hp->size>0);
	return hp->a[0];
}
 
 
bool HeapEmpty(HP* hp)
{
	assert(hp != NULL);
	return hp->size == 0;
}
 
size_t HeapSize(HP* hp)
{
	assert(hp != NULL);
	return hp->size;
}

堆heap的整体代码

heap.h如下所示。


#pragma once
#include<stdio.h>
#include<assert.h>
#include<cstring>
#include<cstdlib>
#include<malloc.h>
 
typedef int HPDataType;
typedef struct heap 
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
 
void HeapInit(HP* hp)
{
	assert(hp != NULL);
	hp->a = NULL;
	hp->size = hp->capacity=0;
}
 
void HeapDestory(HP* hp)
{
	assert(hp != NULL);
	free(hp->a);
	hp->a = NULL;
}
//建立小堆的AdjustUp
//void AdjustUp(HPDataType* a, size_t pos)
//{
//	//堆在逻辑空间上是一个完全二叉树，而二叉树如果采用顺序存储方式，则可以通过下标计算父子关系
//	size_t parent = (pos - 1) / 2;
//	while (pos>0)
//	{
//		if (a[pos] < a[parent])
//		{
//			HPDataType temp = a[pos];
//			a[pos] = a[parent];
//			a[parent] = temp;
//			pos = parent;
//			parent = (pos - 1) / 2;
//		}
//		else
//			break;
//	}
//}
 
//建立大堆的AdjustUP
//a表示调整哪个堆，pos表示调整哪个节点
void AdjustUp(HPDataType* a, size_t pos)
{
	//堆在逻辑空间上是一个完全二叉树，而二叉树如果采用顺序存储方式，则可以通过下标计算父子关系
	size_t parent = (pos - 1) / 2;
	while (pos>0)
	{
		if (a[pos] > a[parent])
		{
			HPDataType temp = a[pos];
			a[pos] = a[parent];
			a[parent] = temp;
			pos = parent;
			parent = (pos - 1) / 2;
		}
		else
			break;
	}
}
void HeapPush(HP* hp, HPDataType x)
{
	assert(hp != NULL);
	//如果满了就扩容
	if (hp->capacity == hp->size)
	{
		size_t newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
		//当hp->a为NULL时，realloc等价于malloc，当hp->a不为NULL时，扩容后会将原有数据从头到尾拷贝到新分配的内存区域，因此无需memcpy
		HPDataType* temp = (HPDataType*)realloc(hp->a, newcapacity * sizeof(HPDataType));
		if (temp == NULL)
		{
			printf("realloc failure");
			exit(100);
		}
		hp->a = temp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
 
	//向上调整
	AdjustUp(hp->a, hp->size - 1);
}
 
 
//a表示在哪个堆里调整，pos表示正在被调整的节点，size表示堆中节点的个数
//void AdjustDown(HPDataType* a, size_t pos,size_t size)
//{
//	//堆在逻辑空间上是一个完全二叉树，而二叉树如果采用顺序存储方式，则可以通过下标计算父子关系
//	size_t leftchild = 2 * pos + 1;
//	size_t rightchild = 2 * pos + 2;
//	size_t minchild;
//	//因为堆是完全二叉树，所以当右孩子存在时，左孩子一定存在
//	if (rightchild < size)
//	{
//		//因为我们建小堆，所以在正在被调整节点的孩子节点中找出更小的那一个孩子，
//		if(a[leftchild] < a[rightchild])
//			minchild = leftchild;
//		else
//			minchild = rightchild;
//	}
//	//当只有左孩子存在时，它就是最小的孩子节点
//	else if(leftchild<size)
//	{
//		minchild = leftchild;
//	}
//	//既没有左孩子也没有右孩子，无需调整
//	else
//	{
//		return;
//	}
//
//	while (minchild<size)
//	{
//		//如果满足条件，则开始交换父子节点
//		if (a[pos] > a[minchild])
//		{
//			HPDataType temp = a[minchild];
//			a[minchild] = a[pos];
//			a[pos] = temp;
//			//交换后还有可能继续向下调整，因此更新新的父子节点的下标
//			//更新父节点下标
//			pos = minchild;
//			//更新孩子节点下标
//			leftchild = 2 * pos + 1;
//		    rightchild = 2 * pos + 2;
//			//因为堆是完全二叉树，所以当右孩子存在时，左孩子一定存在
//			if (rightchild < size)
//			{
//				//因为我们建小堆，所以在正在被调整节点的孩子节点中找出更小的那一个孩子，
//				if (a[leftchild] < a[rightchild])
//					minchild = leftchild;
//				else
//					minchild = rightchild;
//			}
//			//当只有左孩子存在时，它就是最小的孩子节点
//			else if (leftchild < size)
//			{
//				minchild = leftchild;
//			}
//			//既没有左孩子也没有右孩子，无需调整
//			else
//			{
//				return;
//			}
//
//		}
//		else
//			break;
//	}
//	
//
//}
 
//迭代写法
//建立小堆的AdjustDown
a表示在哪个堆里向下调整，pos表示需要向下调整的节点的下标，size表示堆里共有多少个节点，用于判断pos位置节点的孩子节点是否有越界
//void AdjustDown(HPDataType* a, size_t pos,size_t size)
//{
//	//堆在逻辑空间上是一个完全二叉树，而二叉树如果采用顺序存储方式，则可以通过下标计算父子关系
//	//child表示左右孩子中更小的那一个，先默认让左孩子充当child
//	size_t child = 2 * pos + 1;
//	//如果被调整节点的左孩子存在，则有需要调整的可能，进入循环，若不存在，则不需要向下调整，退出函数
//	while (child<size)
//	{
//		//如果右孩子存在，并且右孩子的值小于左孩子，则让右孩子成为child
//		if (child + 1 < size && a[child] > a[child + 1])
//			child = child + 1;
//		//如果满足条件，则开始交换父子节点
//		if (a[pos] > a[child])
//		{
//			HPDataType temp = a[child];
//			a[child] = a[pos];
//			a[pos] = temp;
//			//交换后还有可能继续向下调整，因此更新新的父子节点的下标
//			//更新父节点下标
//			pos = child;
//			//更新孩子节点下标
//			child = 2 * pos + 1;
//		}
//		else
//			//如果父亲节点小于两个孩子节点中较小的孩子节点，则已经是小堆了，无需调整，直接break结束循环
//			break;
//	}
//	
//
//}
 
//递归写法
//建立小堆的AdjustDown
//a表示在哪个堆里向下调整，pos表示需要向下调整的节点的下标，size表示堆里共有多少个节点，用于判断pos位置节点的孩子节点是否有越界
//void AdjustDown(HPDataType* a, size_t pos, size_t size)
//{
//	//堆在逻辑空间上是一个完全二叉树，而二叉树如果采用顺序存储方式，则可以通过下标计算父子关系
//	//child表示左右孩子中更小的那一个，先默认让左孩子充当child
//	size_t child = 2 * pos + 1;
//	//如果右孩子存在，并且右孩子的值小于左孩子，则让右孩子成为child
//	if (child + 1 < size && a[child] > a[child + 1])
//		child = child + 1;
//
//	//如果更小的孩子child越界，则直接return结束递归
//	if (child >= size)
//		return;
//	//如果满足条件，则开始交换父子节点
//	if (a[pos] > a[child])
//	{
//		HPDataType temp = a[child];
//		a[child] = a[pos];
//		a[pos] = temp;
//		//交换后还有可能继续向下调整，因此更新父亲节点的下标，孩子不用在下面更新，因为进入下一次递归时会更新孩子节点的下标
//		//更新父节点下标
//		pos = child;
//	}
//	else
//		//如果父亲节点小于两个孩子节点中较小的孩子节点，则已经是小堆了，无需调整，直接return结束递归
//		return;
//	AdjustDown(a, pos, size);
//
//}
 
 
//迭代写法
// 建立大堆的AdjustDown
//a表示在哪个堆里向下调整，pos表示需要向下调整的节点的下标，size表示堆里共有多少个节点，用于判断pos位置节点的孩子节点是否有越界
void AdjustDown(HPDataType* a, size_t pos,size_t size)
{
	//堆在逻辑空间上是一个完全二叉树，而二叉树如果采用顺序存储方式，则可以通过下标计算父子关系
	//child表示左右孩子中更大的那一个，先默认让左孩子充当child
	size_t child = 2 * pos + 1;
	//如果被调整节点的左孩子存在，则有需要调整的可能，进入循环，若不存在，则不需要向下调整，退出函数
	while (child<size)
	{
		//如果右孩子存在，并且右孩子的值大于左孩子，则让右孩子成为child
		if (child + 1 < size && a[child]<a[child + 1])
			child = child + 1;
		//如果满足条件，则开始交换父子节点
		if (a[pos]<a[child])
		{
			HPDataType temp = a[child];
			a[child] = a[pos];
			a[pos] = temp;
			//交换后还有可能继续向下调整，因此更新新的父子节点的下标
			//更新父节点下标
			pos = child;
			//更新孩子节点下标
			child = 2 * pos + 1;
		}
		else
			//如果父亲节点大于两个孩子节点中较大的孩子节点，则已经是大堆了，无需调整,直接break结束循环
			break;
	}
}
 
 
//递归写法
//建立大堆的AdjustDown
//void AdjustDown(HPDataType* a, size_t pos, size_t size)
//{
//	size_t child = 2 * pos + 1;
//	//if (child + 1 < size && a[child]> a[child + 1])建立小堆，能排升序
//	if (child + 1 < size && a[child] < a[child + 1])//建立大堆，能排降序
//		child = child + 1;
//
//	
//	if (child >= size)
//		return;
//	//if (a[pos] > a[child])//建立小堆，能排升序
//	if (a[pos] < a[child])//建立大堆，能排降序
//	{
//		HPDataType temp = a[child];
//		a[child] = a[pos];
//		a[pos] = temp;
//		pos = child;
//	}
//	else
//		//如果父亲节点小于两个孩子节点中较小的孩子节点，则已经是小堆了，无需调整，直接return结束递归
//		return;
//	AdjustDown(a, pos, size);
//
//}
 
 
 
 
void HeapPop(HP* hp)
{
	assert(hp != NULL);
	assert(hp->size > 0);
	//交换堆顶和数组末尾的数据
	HPDataType temp = hp->a[0];
	(hp->a)[0] = (hp->a)[hp->size - 1];
	(hp->a)[hp->size - 1];
 
	hp->size--;
	AdjustDown(hp->a,0,hp->size);
 
}
 
HPDataType HeapTop(HP* hp)
{
	assert(hp != NULL);
	assert(hp->size > 0);
	return hp->a[0];
}
 
bool HeapEmpty(HP* hp)
{
	assert(hp != NULL);
	return hp->size == 0;
}
 
size_t HeapSize(HP* hp)
{
	assert(hp != NULL);
	return hp->size;
}

阶段性总结（AdjustUp、AdjustDown这俩算法和HeapPush、HeapPop之间的关系）

阶段性总结

AdjustUp、AdjustDown他俩都是既能将数组中的数据调整成大堆，又能将数组中的数据调整成小堆。如果编写的AdjustUp是用于建大堆的版本，则只能通过AdjustUp建大堆，无法建小堆；反之如果编写的AdjustUp是用于建小堆的版本，则只能通过AdjustUp建小堆，无法建大堆。AdjustDown也是如此。

堆这块主要需要明白这些东西：如何编写建大堆版本的AdjustUp、AdjustDown和如何编写建小堆版本的AdjustUp、AdjustDown。如何通过AdjustUp完成建堆。如何通过AdjustDown完成建堆。如何编写堆的插入HeapPush和堆的删除HeapPop，它的逻辑是怎么走的。

AdjustUp、AdjustDown这俩算法和HeapPush、HeapPop之间的关系

可能有时候你会陷入细节的泥潭，搞不清楚这几个货之间的关系。

你可能会认为AdjustUp只服务于HeapPush，AdjustUp只用于在插入节点进堆后对该节点进行AdjustUp向上调整；AdjustDown只服务于HeapPop，AdjustDown只用于在堆顶节点和完全二叉树最后一个叶子节点交换后对该叶子节点进行AdjustDown向下调整。认为没有了HeapPush和HeapPop，那AdjustUp和AdjustDown也不必存在。

如果你这样想，那你一定没有清晰认识到AdjustUp、AdjustDown是用来干嘛的。这两个算法只用于将某个数据进行调整，期望将这个数据调整过后，数据之间的结构能形成一个堆。那既然我算法存在的意义只是为了调整数据，让数据经过调整后，其结构能形成一个堆，那难道我没有HeapPush插入数据，HeapPop删除堆顶也就是数组首元素的数据时，我就不能调整数据了吗？当然不是，所以事实上，AdjustUp、AdjustDown这俩算法是独立存在的，除了在HeapPush和HeapPop中会使用他俩，我们可能会有让一个数组原地变成堆的需求，此时建堆就可以通过这俩算法实现。

注意HeapPush函数内部的确只能通过AdjustUp对新插入节点做调整，不能用AdjustDown向下调整；HeapPop函数内部的确只能通过AdjustDown对【和堆顶元素交换的节点】做调整，不能用AdjustUp向上调整。

堆的应用

排序（如何建立大堆和小堆，如何让一个不是堆的数组原地成为堆，建堆）

可以通过堆进行排序，如下图所示。

代码如下


void main()
{
    int ar[] = {10,9,8,7,6,5,4,3,2,1 };
	heap h;
	HeapInit(&h);
	int size = sizeof(ar) / sizeof(int);
	for (int i = 0; i < size; i++)
	{
		HeapPush(&h, ar[i]);
	}
 
	while (!HeapEmpty(&h))
	{
		printf("%d ", HeapTop(&h));
		HeapPop(&h);
	}
 
    HeapDestory(&h);
 
}

前面也说过，因为我们实现的AdjustDown和AdjustUp都是以建立小堆为基础去调整节点的，所以HeapPush和HeapPop增加数据或删除数据后，AdjustUp和AdjustDown默认是将被破坏的小堆重新调整成一个小堆，因此这里只能排升序。

那我想排降序该怎么办呢？

答案：非常简单，其他所有代码都不用变，只需修改AdjustDown和AdjustUp调整节点的逻辑即可，比如在AdjustDown中，让小的节点往下走，大的节点往上走；又比如在AdjustUp中，让大的节点往上走，小的节点往下走。做到这几点只需将小于号改成大于号，大于号改成小于号即可。

代码如下。


void AdjustUp(HPDataType* a, size_t pos)
{
	//堆在逻辑空间上是一个完全二叉树，而二叉树如果采用顺序存储方式，则可以通过下标计算父子关系
	size_t parent = (pos - 1) / 2;
	while (pos>0)
	{
        //小堆，排升序if (a[pos] < a[parent])
        if (a[pos] > a[parent])//大堆，排降序
		{
			HPDataType temp = a[pos];
			a[pos] = a[parent];
			a[parent] = temp;
			pos = parent;
			parent = (pos - 1) / 2;
		}
		else
			break;
	}
}
 
 
//AdjustDown简洁版本的迭代写法
void AdjustDown(HPDataType* a, size_t pos,size_t size)
{
	size_t child = 2 * pos + 1;
	while (child<size)
	{
		if (child + 1 < size && a[child]<a[child + 1])
			child = child + 1;
		//如果满足条件，则开始交换父子节点
		if (a[pos]<a[child])
		{
			HPDataType temp = a[child];
			a[child] = a[pos];
			a[pos] = temp;
			//交换后还有可能继续向下调整，因此更新新的父子节点的下标
			//更新父节点下标
			pos = child;
			//更新孩子节点下标
			child = 2 * pos + 1;
		}
		else
			//如果父亲节点小于两个孩子节点中较小的孩子节点，则已经是小堆了，无需调整，直接break结束循环
			break;
	}
	
 
}
 
 
//AdjustDown简洁版本的递归写法
/*void AdjustDown(HPDataType* a, size_t pos, size_t size)
{
	size_t child = 2 * pos + 1;
	//if (child + 1 < size && a[child]> a[child + 1])建立小堆，能排升序
	if (child + 1 < size && a[child] < a[child + 1])//建立大堆，能排降序
		child = child + 1;
	
	if (child >= size)
		return;
	//if (a[pos] > a[child])//建立小堆，能排升序
	if (a[pos] < a[child])//建立大堆，能排降序
	{
		HPDataType temp = a[child];
		a[child] = a[pos];
		a[pos] = temp;
		pos = child;
	}
	else
		//如果父亲节点小于两个孩子节点中较小的孩子节点，则已经是小堆了，无需调整，直接return结束递归
		return;
	AdjustDown(a, pos, size);
}*/

将这两个接口的代码稍作修改后，我们实现的AdjustDown和AdjustUp就都是以大堆为基础去调整节点的了，此时就可以支持排降序了，如下图所示。

代码如下。


void main()
{
	
	int ar[] = {2,1,3,4,5,6,8,7,9,10 };
	heap h;
	HeapInit(&h);
	int size = sizeof(ar) / sizeof(int);
	for (int i = 0; i < size; i++)
	{
		HeapPush(&h, ar[i]);
	}
 
	while (!HeapEmpty(&h))
	{
		printf("%d ", HeapTop(&h));
		HeapPop(&h);
	}
 
  	HeapDestory(&h);
 
 
}

走到这里我们就找到了建立大堆和小堆的方法，我们可以对它进行一下总结：一个堆是大堆还是小堆，完全只和AdjustDown和AdjustUp这两个算法有关，完全只看这两个算法是如何实现的，和其他因素没有任何关系。比如说如果AdjustDown和AdjustUp中交换父子节点的逻辑都是服务于建小堆的，则不管是通过【不断HeapPush插入到堆这个数据结构】的方式建堆，还是通过【不断AdjustDown或者AdjustUp】的方式让一个数组原地成为堆，它们都只能建小堆，是无法建大堆的。

我们将上面代码的逻辑封装成下图的函数，一个能完成排序任务的堆排序就出来了。

但你认为下图的写法好吗？

实际是存在很多问题的。其一，这里表面上看只有这几行代码，但不要忘了我们必须得先实现堆这个数据结构，自己编写HeapPush、HeapPop、HeapInit、HeapEmpty等等这些接口，然后才能使用它们。光堆这个数据结构就已经接近200行的代码了，再加上堆排序的代码，就更繁琐了。相比于人家只用50行就能搞定的堆排序，我们就把问题搞复杂了。其二，存在O（N）的空间复杂度，N表示节点个数，在下图的HeapPush中，我们插入节点是malloc开辟了空间的，上图中的数组a里有多少数据，我们HeapPush就得malloc多少个数据，所以是O（N），这就导致数组a只充当了一个存数据的功能，去记录哪些数据需要插入到堆里，这是不好的，因为我们完全可以直接在数组a中堆排序，干嘛去额外开辟空间呢，所以接下来咱们说一说真正的堆排序。

真正的堆排序

错误示例

前面也说过，上图写法存在许多问题，接下来我们对他进行改进。首先我们不必为了堆排序去写一个堆这样的数据结构，因为我们可以直接对上图的数组a进行调整，让a中的数据在逻辑空间上形成一个堆，这样堆顶的数据就是极值，我们每次能拿到极值，就可以进行排序了。可以发现因为不用编写堆这个数据结构，我们也就不必malloc开辟空间，之前所说的空间复杂度O（N）的问题也解决了，可谓一石二鸟。

假设上图数组a中的数据如下图所示，首先，数组a已经是一个完全二叉树了，这是成为堆的条件之一，但数组a目前还不是一个堆，因为其父亲节点不满足总小于或者总大于孩子节点，所以我们要在数组a中对数据进行调整，让a成为一个堆，这里以大堆为例。

因为排序前必须先建堆，所以这里先讲讲如何建堆。

不额外开空间，让一个数组原地成为堆的调整方法或者说建堆方法有两种。

先来看第一种，通过【从堆顶开始，自上而下的AdjustUp向上调整法】建堆。

这里为什么不能从完全二叉树最后一个叶子节点，也就是数组的最后一个元素开始向上调整，非要从堆顶，也就是数组首元素开始向上调整呢？

因为向上调整有一个前提，在被调整节点开始向上调整前，其余所有节点共同形成的结构必须已经是一个堆了，否则向上调整就没有意义，因为即使调整完毕，最后所有节点形成的结构也不是一个堆。

因为需要手写数据结构堆heap，还要为堆malloc开O（N）空间大小的数组去存堆中的节点，所以如上图红框处般不断HeapPush插入节点去建堆这样的方法不可取。但注意虽然这种方法不可取，但我们可以借鉴它的做法，它是将数组a中从第一个数据开始的每一个数据都HeapPush插入到堆里，HeapPush分两步，第一步是插入数据进malloc出的数组，第二步是AdjustUp向上调整数据形成堆，因为从第一次插入开始，每一次插入后都会对插入节点做调整，这相当于每次插入节点前，其他节点共同形成的结构就已经是一个堆了，这就满足了上文中说的HeapPush插入数据的前提（本质是AdjustUp的前提），因此将数组a中每一个数据都HeapPush插进为堆存储数据而maloc出的数组后，这个malloc出的数组天然就成为了一个堆。

现在看看我们有什么，只有一个数组，如下图所示，那如何将数组原地建成一个堆呢？可以发现对比上一段中的不可取的方法，这里天生就完成了数据的插入，因为数据本来就在数组里，不必再插入数据了，所以天生就完成了HeapPush两步中的第一步，所以我们要做的是HeapPush的第二步，也就是AdjustUp向上调整数据形成堆，那从哪个数据开始AdjustUP向上调整呢？上一段中说的不可取的方法它是从第一次插入开始，每一次插入后都会对插入节点做AdjustUp向上调整，我们模拟它的做法，也从第一次插入数据后的位置开始AdjustUp向上调整，即逻辑空间上为堆顶位置，物理空间上为数组首元素的位置开始调整数据，也就是从下图的27开始向上调整AdjustUp，然后让数组中位于27后的元素也从左到右依次向上调整AdjustUp，直到调整完数组中的每一个元素后结束，这就是自上而下的AdjustUp向上调整法。可以发现从本质来说，这种方法就是模拟HeapPush插入数据的过程。这里说一下，该方法实际上也可以从节点15开始调整，不是一定要从27开始，因为27没有父亲节点，无法向上调整，进入AdjustUp后会立刻退出AdjustUp函数，因此我们在下面计算时间复杂度时，会从15开始计算，而不是27。

建堆的代码如下。


void HeapSort(int* a, size_t size)
{
	//建堆方法1：向上调整
	for (size_t i = 0; i < size; i++)
	{
		AdjustUp(a, size);
	}
	
	//排序逻辑未编写
}

测试结果图如下，可以看到成功建立了大堆。至于为什么是大堆，上文中也说过，我们在这里是以大堆为例去让数组原地建堆的，所以将AdjustUp的逻辑修改成了建立大堆。

接下来说说通过【自上而下的向上调整法】建堆的时间复杂度，答案为O(n*log n)，n表示完全二叉树的节点总数，分析如下。

再来看第二种，通过【从第一个非叶子节点开始，自下而上的AdjustDown向下调整法】建堆。

这里为什么不能从第一个节点，也就是堆顶元素或者说数组首元素开始向下调整呢？因为向下调整是有前提的，要求被调整节点的左右子树都是一个堆，否则向下调整就没有意义，因为即使向下调整完毕后，节点之间形成的结构也不是一个堆。

可以看到，这里有一种思想，就是没有条件我就创造条件，既然我从堆顶开始向下调整时，左右子树不是一个堆，那我就先想办法让左右子树都成为一个堆，然后最后来向下调整你这个堆顶的元素。想做到这一点，我们就得先从整个完全二叉树的第一个非叶子节点开始向下调整，也就是下图的28开始，然后18、19...从右到左依次向下调整，直到调整完堆顶元素27后再结束。这里提一嘴，实际上也并非是一定得从第一个非叶子节点如28开始向下调整，也可以是从最后一个叶子节点如37开始从右向左依次向下调整，但这里我们没有这么做，因为叶子节点都没有孩子节点，所以进入AdjustDown函数后就会立刻退出AdjustDown函数，如果叶子节点很多的话，从最后一个叶子节点开始向下调整就会极大的降低排序的性能。

建堆的代码如下。


//a表示排序哪个数组，size表示数组元素的个数
void HeapSort(int* a, size_t size)
{
	
	//建堆方法2：从第一个非叶子节点开始向下调整
	//size-1表示最后一个元素的下标，代表最后一个叶子节点的下标，那么(size-1)-1/2就表示最后一个叶子节点的父亲节点了
	for (int i = (size-1-1)/2; i>=0; i--)
	{
		AdjustDown(a, i,size);
	}
	//排序逻辑未编写
 
}

测试结果如下图，可以看到成功建立了大堆。至于为什么是大堆，上文中也说过，我们在这里是以大堆为例去让数组原地建堆的，所以将AdjustDown的逻辑修改成了建立大堆。

接下来说说通过【自下而上的向下调整法】建堆的时间复杂度，答案为O（N），N表示完全二叉树的节点总数，分析如下。

这里说一下，O（N）是比O（N*logN）更优的，所以【自下而上的向下调整法】的建堆方式是比【自上而下的向上调整法】的建堆方式更优秀的，因此建堆时应尽量使用前者。

走到这里，关于建堆我们就讲解完毕了，所以再回到正题，继续实现正确的堆排序。

这里有一个问题，如果要排升序，我们在建堆时，是建大堆还是小堆呢？有同学可能会被前面不可取的堆排序中使用的方法给误导，比如排升序时，认为应先拿到最小值，再拿次小值，所以建小堆。按照这样的思路，我们先建小堆，如下图所示。

如上图，首先的确是让堆顶元素变成了最小值15，让15排在了数组中第一个位置，但接下来该如何让次小值即红框中数据的最小值18排到数组中第二个位置呢？注意目前18已经在数组第二个位置只是因为数据间的巧合，所以假设18目前不在第二个位置，我们该如何让次小值18排到数组中第二个位置呢？

目前需要将红框中的最小值，也就是18排到数组中第二个位置，但以红框中数据构建的完全二叉树如下图蓝框处所示，它并不是一个小堆，因为28大于了27，因此堆顶元素并不一定是最小值。那该怎么找到最小值呢？

没有什么好的办法，我们只能将上图红框内的数据重新建小堆，以此拿到红框中数据的最小值18。后面在【19，37】这个区间也要以建堆的方法拿到最小值19，然后【25，37】这个区间也如此。说简单点就是在N个数中建小堆拿到堆顶的最小值A，然后排除掉最小值A后继续在N-1个数中建小堆拿到堆顶的最小值B，每次循环都建小堆然后拿到最小值，直到N为0结束。这相当于排序时每将一个数据排到正确的位置，都要经过一次建堆，这样代价就太大了，你想想看，上面也说过，即使是通过更优的【自下而上的向下调整法】去建堆，时间复杂度也是O（N），现在待排序的数据有N个，每将一个数据排序到正确的位置需要建一次小堆，那加起来该堆排序总共的时间复杂度就是O（N^2）了。

这样的效率就太差了，我遍历一遍数组能拿到最小值，时间复杂度为O（N），你建堆拿到最小值，时间复杂度也是O（N），我通过不断遍历去完成排序的总共的时间复杂度也是O（N^2），你堆排序的效率和我无脑遍历数组的排序方式的效率一样了，堆排序还有什么意义，所以说这样设计堆排序不是不可以，但效率太低了，没有用到堆的优势，我们不采用。

所以堆排序排升序时不能像上面一样建小堆，要建立大堆，接下来说说正确的方式。

方式和HeapPop的思路很像，首先建立大堆，建立大堆后，如下图左边所示，我们要把逻辑空间上的堆顶元素（物理空间上的数组首元素）同时也就是最大值，和数组的最后一个元素交换，然后size--，此时28就处于堆顶了，可以发现如下图被黄线圈起来的部分所示，28的左子树和右子树此时依然是一个大堆，满足AdjustDown的前提，所以只需将28向下调整，调整完毕后整颗树又成了一个大堆，这时再将堆顶的最大值与数组的最后一个元素交换，注意因为之前size--了，所以目前数组的最后一个元素为下图蓝框部分的最后一个元素，即15，所以65是不会受到影响的，交换后再次size--，再次将堆顶元素向下调整，直到数组的size为0结束循环。这相当于第一次从N个数中找最大值，找到后放到数组末尾，然后让数组的size减1，然后再到前N-1个数中找最大值，然后再放到数组末尾，再size-1，然后继续循环，直到size为0结束。

可以发现建大堆去排升序和建小堆去排升序的思想是一样的，只不过建小堆去排升序时，排一个数就要建一次堆，而建大堆排升序时，只有排第一个数时，才需要建一次堆，时间复杂度为O（N），后序每排序一个数据只需经过一次向下调整即可，向下调整的时间复杂度为O（logN）【注意这里的所有N都表示堆中节点总数】，有N个待排数据，所以如果排升序时建大堆，堆排序的时间复杂度是O(N)+O(N*logN)，也就是O（N*logN）。

堆排序的最终代码如下。


//迭代写法
// AdjustDown当前是建立大堆的版本
//a表示在哪个堆里向下调整，pos表示需要向下调整的节点的下标，size表示堆里共有多少个节点，用于判断pos位置节点的孩子节点是否有越界
void AdjustDown(HPDataType* a, size_t pos,size_t size)
{
	//堆在逻辑空间上是一个完全二叉树，而二叉树如果采用顺序存储方式，则可以通过下标计算父子关系
	//child表示左右孩子中更大的那一个，先默认让左孩子充当child
	size_t child = 2 * pos + 1;
	//如果被调整节点的左孩子存在，则有需要调整的可能，进入循环，若不存在，则不需要向下调整，退出函数
	while (child<size)
	{
		//如果右孩子存在，并且右孩子的值大于左孩子，则让右孩子成为child
		if (child + 1 < size && a[child]<a[child + 1])
			child = child + 1;
		//如果满足条件，则开始交换父子节点
		if (a[pos]<a[child])
		{
			HPDataType temp = a[child];
			a[child] = a[pos];
			a[pos] = temp;
			//交换后还有可能继续向下调整，因此更新新的父子节点的下标
			//更新父节点下标
			pos = child;
			//更新孩子节点下标
			child = 2 * pos + 1;
		}
		else
			//如果父亲节点大于两个孩子节点中较大的孩子节点，则已经是大堆了，无需调整,直接break结束循环
			break;
	}
}
 
 
 
 
//a表示排序哪个数组，size表示数组元素的个数
void HeapSort(int* a, size_t size)
{
	//建堆方法1：从堆顶元素开始向上调整  O(N*logN)
	/*for (int i = 0; i < size; i++)
	{
		AdjustUp(a, i);
	}*/
 
	//建堆方法2：从第一个非叶子节点开始向下调整  O(N)
	//size-1表示最后一个元素的下标，代表最后一个叶子节点的下标，那么(size-1)-1/2就表示最后一个叶子节点的父亲节点了
	for (int i = (size-1-1)/2; i>=0; i--)
	{
		AdjustDown(a, i,size);
	}
	//end用于控制循环
	int end = size;
	while (end>0)//O(N*logN)
	{
		//交换数组首元素（堆顶）和数组最后一个元素
		int temp = a[0];
		a[0] = a[end - 1];
		a[end - 1] = temp;
		//交换完开始调整
		end--;
		AdjustDown(a, 0, end);
 
	}
	
}

测试代码如下，可以发现结果符合预期。

topK问题

求N个数据中前K个最大的元素或者最小的元素，一般情况下N远大于K。先说两个思路。

第一个思路

首先是堆排序。排序后自然就能选前K个最大或最小的元素了。再说说它的时间复杂度，堆排序首先会建堆，这里选择更优的【自下而上的向下调整法】去建堆，时间复杂度为O（N），然后开始循环，每次循环会交换数组首元素和数组最后一个元素，交换后会有一次AdjustDown向下调整，向下调整时间复杂度为O（logN)【注意时间复杂度中的所有N都表示堆中节点总数】，共调整N次，因此堆排序的时间复杂度为O(N）+O（N*logN)≈O（N*logN）。

第二个思路

第二个思路是建N个数的大堆或者小堆，然后开始循环，循环K次，每次循环通过Top拿到堆顶的极值，然后Pop删除该极值，通过这样的方法拿到 N个数据中前K个最大的元素或者最小的元素。时间复杂度：首先建堆，这里选择更优的【自下而上的向下调整法】去建堆，时间复杂度为O（N），然后Pop因为内部会调用AdjustDown，所以Pop的时间复杂度是O（logN），Pop会循环K次，因此最后的时间复杂度为O（N）+O（K*logN）≈O（N），可以将N和K带入值计算，这样的方法效率是比堆排序高了不少的。

问题：现在问题来了，前两个思路可以吗？

答案：在N的值比较小，即数据量很小时是可以的，但假如N的值是100亿，K为10，即在100亿个数据中找前10大的数据，前两种思路就是错误的了。为什么呢？因为内存不够存100亿个数据，不管你是堆排序，还是建堆去Top然后Pop，它们都是需要将数据存进内存的，100亿个int就是400亿字节，1G是10亿字节，那100亿个int就得花40G内存，内存是远远不够的，那该怎么办呢？

最佳方式的基本思路如下：

1.用数据集合中前K个元素来建堆，如果找前k个最大的元素，则建小堆；如果找前k个最小的元素，则建大堆。因为K的值是远小于数据总量N的，所以一般来说存K个数据是绰绰有余的。这里以找前K个最大值，去建小堆举例。

2.然后用剩余的N-K个元素依次与堆顶元素来比较，如果该元素比堆顶元素大，则让它替换堆顶元素，然后再AdjustDown向下调整堆顶元素让堆重新成为小堆。这N-K个数据既然在内存中存不下，那它可以存在文件里，我每次从文件读几个数据和你堆顶元素比较。

3.走完上面的流程后，堆里的K个数据就是N个数据中最小或者最大的前K个数据。

接下来分析它的时间复杂度，建K个数据的堆需要O（K），然后剩余的N-K个元素依次与堆顶元素来比较时，如果需要替换堆顶元素，则会向下调整，向下调整的时间复杂度是O（logN），这里有N-K个元素可能会发生调整，所以总共的时间复杂度为O（K）+O（（N-K）*logN）≈O（（N-K）*logN）。带入N和K的值可以发现时间复杂度并没有比之前的两种思路更优，但空间复杂度一定是远比它们更优秀的。

topK的代码如下图所示。

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