顺序二叉树是由堆来实现的，堆是一种特殊的二叉树（完全二叉树），在具备着普通二叉树的性质的基础上，还有一些其它的性质。
一.堆的基础概念和性质
在一个数据集合中，所有的数据元素按照完全二叉树的方式排列，并且满足对于每个根节点来说，其左右子节点均小于该根节点的完全二叉树。
而根据左右子节点是小于/大于该根节点，可将其定义为：小根堆（小堆）/大根堆（大堆）。
完全二叉树一定要满足小堆/大堆，才可以进行成堆的数据结构处理。同时，堆也一定是一颗完全二叉树。
在小根堆和大根堆中需要额外注意的是，只是对于每个根节点来说，其左右子节点小于该根节点，而非按照特定的升序/降序进行排列。
根据完全二叉树的性质，给定一个确定位置下标的节点 i 元素，则其父节点为
其左右子节点分别为：，
。
注意父节点如果计算结果为负数，表示该节点没有父节点。而左右子节点的计算结果如果大于等于（因为数组元素下标到n-1，所有等于的情况无法取到）数组元素个数n，则表示该点没有右/左右子节点。
二.堆结构代码的实现
堆本质是一个数组，所以和顺序表/栈的基础数据结构实现方式类似，都由一个数组，一个指向数组下标的size变量，和一个指示当前数组大小的capacity变量。
2.1堆的初始化——void HeapInit(pHeap php);
在初始化时，给定数组初始大小为4，size为0表示目前没有任何元素，capacity置为4表示目前数组中有着可以存放4个元素大小的空间。
2.2堆的销毁——void HeapDestroy(pHeap php)
对于堆的销毁，类似于顺序表，只需要销毁由calloc/malloc开辟的动态数组即可。其余变量置为0，表示没有任何元素以及数组大小。
2.3判断堆是否为空堆——bool HeapEmpty(pHeap php)
如果堆的size为0，表示目前堆中不存在任何元素，为空堆。为空堆时返回值为1，不为空堆时返回值为0。
2.4堆底Push数据——void HeapPush(pHeap php, HeapDataType x)
在往堆底放数据时，首先需要判断堆的空间是否足够存放下一个新数据，如果不够则需要进行扩容。
扩容完成后，在堆的最后一个元素的下一个位置，即size的位置插入数据。
插入数据后，该堆不一定满足大堆/小堆的定义，所以需要对于插入数据后的堆的最后一个元素进行向上调整处理。
向上调整处理函数——void HeapAdjustUp(HeapDataType* arr, int child)
以大堆为示例，传递的参数为数组，以及新插入后的最后一个元素的下标，指示要对哪个元素进行调整。
根据堆的性质，可以计算除新插入元素（最后一个元素）的父节点。
对于大堆的情况，父节点需要大于左右子节点，if判断条件为子节点的数据大于父节点，则二者需要进行交换。然后将父节点赋值为子节点，利用新的父节点重新计算一个子节点，直到堆顶的根节点，所以循环的判断条件为child > 0 ，表示如果子节点转移到了根节点的位置，就可以不用继续比较了。
数据交换函数——void Swap(HeapDataType* x, HeapDataType* y)
整体过程如下图所示：
例如在堆最后插入的数据为80，其下标为6，可以找到其父节点为（6-1）/2 = 2。两个元素比较，子节点大于父节点，进行位置的交换。
然后子节点的下标改为父节点的下标，此时子节点下标为2，计算新父节点的下标，为0。两个元素进行比较，发现子节点仍然大于父节点，进行数据交换。再将子节点的下标改为现在父节点的下标，此时子节点下标为0，已经是根节点，循环跳出。新形成的堆满足大堆的定义。
在向上调整结束后，需要将size自增1，从而指向堆的下一个元素，以方便进行数据插入。
2.5堆顶Pop数据——void HeapPop(pHeap php)
堆顶弹出数据，如果直接将指向数组下标为0的元素删除，就是将根节点删除，则会将左右子树分开，两个树之间没有联系，将其融合为一个新的完全二叉树的过程较为繁琐。
所以这里的思路为将堆顶和堆底最后一个下标的元素进行数据交换，然后只需要删除堆底元素的数据，之后将堆顶元素进行向下调整到合适的位置即可。
向下调整函数——void HeapAdjustDown(HeapDataType* arr, int n ,int parent)
向下调整函数中，需要传递的参数为数组，堆中所有元素的个数，以及需要向下调整的父节点下标。
在函数中，根据给定的父节点，可根据2 i +1求出左子节点。
以大堆为例，一个父节点有左右两个子节点，左节点已经求出，右节点为左节点+1。对于大堆的情况来说，需要找到左右子结点中较大的节点和父节点进行比较，然后进行相应的数据交换。因为大堆需要满足父节点大于左右两个子节点，所以要找到两个子节点中较大的元素，交换数据后才能满足大堆的定义。
然后将父节点赋值为子节点的位置，利用新的父节点下标，求出新的子节点下标，数据进行比较后，重复交换过程。如果求出其子节点的下标大于等于n，就代表该节点没有子节点，该节点到达了叶子节点的位置，就不需要再进行向下调整了。
整个过程示意图如下所示：
先进行堆顶和堆底元素交换，删除堆底元素。此时堆顶元素为10，左右子节点为30和56，56较大，10和56进行交换。56成为新的堆顶，10没有子节点，交换结束。仍然满足大堆的定义。
2.6取出堆顶的数据——HeapDataType HeapTop(pHeap php);
取出堆顶的数据，只需要找到并返回数组下标为0的元素即可。
至此，基础堆代码的实现完成。需要注意的是，上述代码实现的是大根堆，如果想实现小根堆，则需要在向上调整和向下调整函数中，修改父节点和子节点判断大小的逻辑以及左右子节点判断大小的逻辑。
三.堆排序算法
对于大堆和小堆来说，其最有特点的节点为第一个根节点，以大堆为例：其顶部的根节点为整个堆（数组）中的最大值。根据这个性质可以写出以堆的思想为基础的排序算法。
升序排列的堆排序算法
将给定的数组元素建成一个大堆数组，然后将堆顶和堆底元素进行交换，此时堆底的元素为最大值，将数组长度减1后，下次对数组进行操作就无法操作到最大值元素。
之后将堆顶元素向下处理，形成一个新的大堆，重复堆顶堆底元素交换，交换后长度减一。直到遍历整个数组。
给定一个数组，内部放着随机的元素，要将其排序为一个升序数组。
首先需要将该数组变成一个大堆：成堆化处理
成堆化处理思路有两种，向上调整建堆和向下调整建堆，先介绍向上调整建堆。
向上调整建堆的思路，类似于在堆底Push数据的思路。首先对数组第一个元素进行建堆，只有一个根节点，是一个堆；之后将数组第二个元素放入堆底，堆底元素向上调整。外层循环整个数组，表示每次循环多进入堆底一个数组元素，内层循环进行向上调整的成堆化处理。
向下调整建堆的思路为，找到最后一颗最小的二叉树，对其父节点进行向下调整。然后调整相邻的最小二叉树，之后再进行更大的二叉树的向下处理，直到最后根节点。同样外层循环为父节点，内层循环为向下调整。
至此，将一个数组成堆化（大堆）处理完成，之后只需要将堆的首元素和尾元素交换位置，然后数组长度自减1，堆顶元素向下调整，重复该过程即可。
以下是堆排序算法的整体代码实现：注释部分为向下调整建堆
void HeapSort(int* arr, int n) { int i = 0; //先把乱序数组处理成堆 //从最小的树开始，分批处理 //向下调整建堆思路，从下往上找到最小的二叉树，向下调整 //int last_parent = (n - 1 - 1) / 2; //for (i = last_parent; i >= 0 ; i--)//堆顶也要进行向下处理，所以i需要等于到0 //{ // int parent = i; // int child = (parent * 2) + 1; // while (child < n) // { // if (child + 1 < n && arr[child] < arr[child + 1]) // { // child = child + 1; // } // if (arr[child] > arr[parent]) // { // int tmp = arr[child]; // arr[child] = arr[parent]; // arr[parent] = tmp; // // parent = child; // child = 2 * parent + 1; // } // else // { // break; // } // } //} //向上调整建堆思路，每次从数组中多取出一个元素，然后进行建堆 for (i = 1; i < n; i++) { int child = i; int parent = (child - 1) / 2; while (child > 0) { if (arr[child] > arr[parent]) { int tmp = arr[child]; arr[child] = arr[parent]; arr[parent] = tmp; child = parent; parent = (child - 1) / 2; } else { break; } } } //处理成堆之后，进行排序 //大堆的顶元素是最大值，和最后一个元素交换位置。 //之后数组长度--，继续向下处理，每次只将堆顶和堆底交换位置 while (n>0) { int tmp = arr[0]; arr[0] = arr[n-1]; arr[n-1] = tmp; n--; int parent = 0; int child = (parent * 2) + 1; while (child < n) { if (child+1 < n && arr[child] < arr[child + 1]) { child = child + 1; } if (arr[child] > arr[parent]) { int tmp = arr[child]; arr[child] = arr[parent]; arr[parent] = tmp; parent = child; child = 2 * parent + 1; } else { break; } } } }将数据升序排列需要建立一个大堆，然后将数组首尾元素交换位置，重复该过程；同理，如果要将数组降序排列，则需要建立一个小堆，首尾元素交换位置，重复。
四.TopK问题
TopK问题的描述为，给定一组大量的数据，从这些数据中，找出前k个最大/最小的数据。由于数据量极大，不好将其存放如内存中。
整体思路为：将数据放入到一个文件中，首先读取前k个数据，利用这k个数据建立一个堆，然后从文件中读取一个新数据，利用这个新数据和堆顶元素进行比较，如果这个数据比堆顶元素大/小，将该数据替换堆顶数据，然后进行向下建堆处理。这样遍历完整个文件的数据后，最后堆中的数据就是最大/最小的前k个数据。
以下是找到前k个最大数据的TopK算法实现
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<assert.h> //Top_k问题，从数量级极大的数据中，找出前k个最大/最小的数据 //由于数据量极大，所以无法直接创建一个合适的数组进行存储 //从文件中读取前k个数据，建立合适的堆结构 //然后从文件中多读取一个数据，和堆顶进行比较。 //整个文件的元素遍历结束，就得到了最大/最小的k个值组成的堆 void CreateNumFile() { FILE* NumFile = fopen("Top_K.txt","w"); int i = 0; for (i = 0; i < 10000000; i++) { int r = rand()%1000000; fprintf(NumFile , "%d\n",r); } fclose(NumFile); NumFile = NULL; } void Swap1(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } void HeapAdjustDown1(int* arr, int parent, int k) { int child = parent * 2 + 1; while (child < k) { if (child + 1 < k && arr[child] > arr[child + 1]) { child = child + 1; } if (arr[child] < arr[parent]) { Swap1(arr + child, arr + parent); parent = child; child = parent * 2 + 1; } else { return; } } } void MakeHeap(int* arr, int k) { assert(arr); int i = 0; for (i = (k - 1 - 1) / 2; i >= 0; i--) { HeapAdjustDown1(arr, i, k); } } void Top_K(int* arr, int k) { assert(arr); FILE* NumFile = fopen("Top_K.txt","r"); int tmp = 0; while (fscanf(NumFile, "%d", &tmp) != EOF) { if (arr[0] < tmp) { arr[0] = tmp; HeapAdjustDown1(arr, 0, k); } } } int main() { srand((unsigned int)time(NULL)); CreateNumFile(); FILE* NumFile = fopen("Top_K.txt","r"); int k = 0; printf("请输入要查询的前k个数据:"); scanf("%d",&k); int* arr = (int*)calloc(k, sizeof(int)); int i = 0; for (i = 0; i < k; i++) { fscanf(NumFile,"%d",arr+i); } MakeHeap(arr, k); Top_K(arr, k); for (i = 0; i < k; i++) { printf("%d\n",arr[i]); } return 0; }上述代码，首先创建了一个存放有1千万个随机值数据的txt文件，要从这1000个数据中找出最大的前k个数据。
首先在主函数中输入要找出的k个数据的k变量的值，根据这个值，建立一个能够存放k个数据大小的数组，将txt文件中的前k个数据先存入数组。之后对这数组中的k个元素进行成堆化处理，利用向下建堆思路，建立了一个小堆。
之后进行Top_K问题的求解：读取文件，将文件中的一个数据存放入变量tmp中，将变量tmp与堆顶元素进行比较，如果比堆顶元素大，将其替换为新的堆顶数据，之后对于新的堆进行向下调整处理，直到循环1千万次，遍历完整个txt文件中的数据。
在这里着重解释为什么要建立小堆而不是大堆：小堆有一个重要的特性就是堆顶元素为最小值，其余元素均比堆顶要大。每次新数据如果比堆顶最小值还要大，将其放入堆中，调整完后，又会将一个最小的元素放到堆顶的位置，从而与下一个元素进行替换操作，每次替换一个堆中的最小值，那么所有数据遍历完后，堆中剩下的就是所有数据中最大的k个数据。
而如果建立的是一个大堆，其堆顶为最大值元素，如果tmp比堆顶大，入堆，向下调整后，堆顶仍为该数据，最后只有堆顶是最大的元素，其余仍然是初始化过程中的k-1个元素。但成大堆，就可以找到数据中前k个最小值元素。
