【落羽的落羽 数据结构篇】顺序结构的二叉树——堆

一、堆

1. 概念与分类

上一期我们提到，二叉树的实现既可以用顺序结构，也可以用链式结构。本篇我们来学习顺序结构的二叉树，起个新名字——堆（heap）。
堆是完全二叉树，它的底层是顺序结构的数组，具有二叉树特性的同时，还有一些其他性质：

堆分为大堆和小堆（或称为大根堆、小根堆）：

• 大堆：大堆的每个结点的存储值都 >= 它的子结点的存储值。
• 小堆：小堆的每个结点的存储值都 <= 它的子结点的存储值。

譬如，在一个大堆中，某一个父结点的值为20，则它的子结点的值一定<=20；在一个小堆中，某一个父结点的值为20，则它的子结点的值一定>=20。
左孩子和右孩子的值的大小关系不确定。

换句话说，一个堆一定是大堆或小堆。以下的二叉树，既不是大堆也不是小堆，它们就不是堆：

2. 结构与性质

定义数据结构堆：

typedef struct Heap
{HPDataType* arr;int size;int capacity;
}HP;

上面的画图是用逻辑结构表示堆，用存储结构表示堆就要用到数组了，牢记二叉树结点的编号方式：从上到下，从左到右：
不难推断，堆的数组中有下列性质：

• 大堆的首元素（根结点）是整个堆的最大值，小堆的首元素（根结点）是整个堆的最小值。
• 若子结点的下标为i，则它的父结点是(i-1)/2。
• 若父结点的下标为i，则它的左孩子是2i+1，右孩子是2i+2。结点个数是n，2i+1 >= n 说明无左孩子，2i+2 >= n 说明无右孩子。

顺带给出堆的初始化和销毁方法，以及后面要用到的交换两个变量值的方法：

void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}void HPDestory(HP* php) 
{assert(php);if (php->arr != NULL)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}void Swap(HPDataType* px, HPDataType* py)
{HPDataType tmp = *px;*px = *py;*py = tmp;
}

3. 入堆

想要把一个新的数据插入堆，分为两步：

1. 把它插入堆数组末尾
2. 仅仅插入数据后，可能会破坏堆的性质，所以还要进行“向上调整”操作：将新插入结点顺着其双亲往上调整位置至满足大堆或小堆的位置。
   我们以下面一个小堆为例，插入一个新数据10，如果它小于其父结点（不符合小堆），两者交换。再和新父结点比较，如果小于交换……直到满足小堆：

所以，我们要知道向上调整算法：它有两个参数：要被调整的堆数组，要调整位置的结点的下标：

void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2; //找这个结点的父结点while (child > 0){//调整的是小堆:  <//调整的是大堆:  >if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else //新数据已经到了对的位置{break;}}
}

这样，我们就能实现入堆操作了：

void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity) //空间不够则需增容{int newcapacity = php->capacity == 0 ? 5 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("relloc fail!");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x; //新数据插到末尾，即下标为size的位置AdjustUp(php->arr, php->size);php->size++;
}

测试：
我们来实现一个小堆，乱序给一些数：

将打印结果排列成堆的逻辑结构看看，发现确实是正确的小堆：

4. 出堆

我们所谓的出堆，出的并不是数组末尾数据，出的是第一个数据——堆的根结点。但是，直接除去数组首元素，再将后面元素的下标全体前挪，会使堆的所有结点位置关系“大乱套”，再想调整可就麻烦了。
因此，我们选择这样的出堆定元素方法：先将堆顶数据和堆的最后一个数据交换，size- -把数组末尾数据出掉，再对堆顶元素进行“向下调整”操作。相比刚才所有结点位置大乱套，这样只要调整一个结点的位置就好了。

向下调整算法和向上调整类似：它是比较结点和其较大或较小孩子的值，不断往下交换调整位置直至满足大堆或小堆：

向下调整算法有三个参数：要被调整的堆数组、要调整的结点的下标、堆的数据个数

void AdjustDown(HPDataType* arr, int parent, int n)
{int child = 2 * parent + 1;while (child < n){//调整的是小堆:                  >//调整的是大堆:                  <if (child + 1 < n && arr[child] < arr[child + 1]) //找两个孩子中的较大/较小者{child++;}//调整的是小堆:  <//调整的是大堆:  >if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else //调整完成{break;}}
}

这样，我们就能实现出堆操作了：

void HPPop(HP* php)
{assert(php);assert(php->size != 0); //堆不能为空，否则无数据可出Swap(&php->arr[0], &php->arr[php->size - 1]); //交换堆顶和堆尾数据php->size--; //将堆尾数据出掉AdjustDown(php->arr, 0, php->size);
}

测试：
我们来实现一个大堆，乱序给一些数，再进行一次出堆：

分析逻辑结构，可以看到大堆实现成功，出堆也没有问题：

二、堆排序

堆排序是一种排序方法，不是借助堆的数据结构，而是利用堆的思想进行排序：
一个n个元素的数组，假如想排升序，就将数组建成一个大堆，堆顶是最大值，将堆顶和堆尾交换，下标n-1处就是最大值了；我们再把前n-1个数据调整成大堆，此时堆顶就是第二大的数据，堆顶和堆尾交换，下标n-2处就是第二大值了……直至排序完成。

相反地，想排成降序就建小堆，道理是一样的，我们下面就以建成大堆为例。

堆排序的关键在于一开始建堆的方法，可以分为向下调整建堆和向上调整建堆：

void HPCreat_Down(int* arr, int n) //向下调整算法建堆
{//从尾结点的父结点开始往上遍历，每一个结点都进行向下调整for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n); }
}void HPCreat_Up(int* arr, int n) //向上调整算法建堆
{//从第一个结点开始往下遍历，每一个结点都进行向上调整for (int i = 0; i < n; i++){AdjustUp(arr, i);}
}//注：建的是大堆还是小堆，取决于AdjustUp和AdjustDown函数中的大于还是小于号，上面提到过

知道了建堆方式后，就能实现堆排序了：

void HeapSort(int* arr, int n)
{HPCreat_Down(arr, n);//或HPCreat_Up(arr, n);int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end); //对新堆顶进行向下调整，以保证堆的性质end--;}
}

测试：

很顺利。

关于两种建堆方式的时间复杂度：
推导需要用到数列相关定理公式，我就不再证明了，可以直接记住结果：

• 向下调整建堆：T(n) = n - log₂(n+1)，O(n)
• 向上调整建堆：T(n) = (n+1) [log₂(n+1) - 2] + 2，O(n*logn)

可见，向下调整建堆算法更好一些。

三、堆排序的应用——TOP-K问题

TOP-K问题，即求n个数据中前K个最大值或最小值，一般情况下n都很大且n >> k。
我们能想到的最简单的方法就是排序了，但是如果数据量太大，数据不能一下子全部加载到内存中，排序就不可取了。最佳的方式就是用堆来解决，思路为：

• 取前k个数据建堆，遍历剩下的n-k个数据跟堆顶比较。
• 如果找的是前k个最大值，就建小堆。若第k+1个数比堆顶大，就用它替换堆顶，再调整堆，再比较第k+2个数和堆顶……遍历完，最后堆中的k个数就是n个数里面前的k个最大值了。
• 如果找的是前k个最小值，就建大堆。若第k+1个数比堆顶小，就用它替换堆顶，再调整堆，再比较第k+2个数和堆顶……遍历完，最后堆中的k个数就是n个数里面前的k个最小值了。

应该很好理解吧。

举个栗子，我先来造十万个数据，保存到一个文本文件data.txt中

void CreatData()
{srand(time(0));FILE* file = fopen("data.txt", "w");if (file == NULL){perror("fopen fail!");exit(2);}for (int i = 0; i < 100000; i++){int x = (rand() + i) % 100000 + 1;fprintf(file, "%d\n", x);}fclose(file);
}

最后来实现TOP_K算法（以找前k个最小值为例）：

void Top_K()
{int k;printf("请输入K:");scanf("%d", &k);FILE* file = fopen("data.txt", "r");if (file == NULL){perror("fopen fail!");exit(2);}int* maxHeap = (int*)malloc(sizeof(int) * k);if (maxHeap == NULL){perror("malloc fail!");exit(1);}for (int i = 0; i < k; i++){//先将前k个数存到maxHeap中fscanf(file, "%d", &maxHeap[i]);}HPCreat_Down(maxHeap, k); //找前k个最小值，建大堆//遍历剩下的数int x;while (fscanf(file, "%d", &x) != EOF) //fscanf文件读取结束会返回EOF{//谁小谁当堆顶if (x < maxHeap[0]){maxHeap[0] = x;AdjustDown(maxHeap, 0, k);}}	fclose(file);//处理完成，打印结果for (int i = 0; i < k; i++){printf("%d ", maxHeap[i]);}
}

测试：

可以看到，每次输入一个k，都能找到前k个最小值，只不过不是按大小顺序输出的。顺带一提，这个算法的时间复杂度O(n) = k + (n - k)log₂k

本篇完，感谢阅读