Shulou(Shulou.com)06/01 Report--

Editor to share with you how to use heap sorting in C language, I believe most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's learn about it!

I. the concept of heap sorting

? Heap sorting (Heapsort): a sorting algorithm designed by using the data structure of heap tree (heap). It is a kind of selective sorting. To select data through the heap, we should pay attention to building a large heap in ascending order and a small heap in descending order.

Heap sorting uses heap to select numbers, which is much more efficient.

Time complexity:

Space complexity:

Stability: instability

2. Implementation of heap sorting

Let's first create a heap-sorted function:

Void HeapSort (int arr [], int n)

Suppose we want to use heap sort (ascending order) on the following array:

Int arr [] = {70, 56, 30, 25, 15, 10, 75}

According to what we have learned before, the array can be seen directly as a complete binary tree, so we can turn it into a heap. At this point, we can "select numbers" (heap sorting is essentially a selective sort).

Step 1: build the heap

The first step is to find a way to build the arr array into a heap (here we build a small heap first). We introduce two methods, the upward adjustment algorithm and the downward adjustment algorithm:

Method 1: adjust up

Through the "upward adjustment" we have learned before, we use the idea of insertion to solve the problem. First of all, an upward adjustment algorithm is designed:

Void Swap (HPDataType* px, HPDataType* py) {HPDataType tmp = * px; * px = * py; * py = tmp;} / * upward adjustment of the small heap * / void AdjustUp (int* arr, int child) {assert (arr); / / first calculate the father's subscript int parent = (child-1) / 2 according to the formula / / worst case: set to root, child=parent ends when child is root node (root node is always 0) while (child > 0) {if (arr [child])

< arr[parent]) { // 如果孩子小于父亲（不符合小堆的性质） // 交换他们的值 Swap(&arr[child],&arr[parent]); // 传地址 // 往上走 child = parent; parent = (child - 1) / 2; } else { // 如果孩子大于父亲（符合小堆的性质） // 跳出循环 break; } }} ① 首先，通过公式计算出父亲的下标，公式如下： ② 其次，设计循环部分，最坏情况为调到根，如果已经符合大堆的条件则终止循环。 ③ 进入循环后进行判断，如果 child ＞ parent，则交换它们的值，让父亲获得孩子的值，孩子得到父亲的值，从而让它们符合大堆的性质。 ④ 交换完毕后，以便于继续判断，我们需要更新 child 和 parent 指向的元素，做到 "往上走" 此时，我们把数组里的元素依次调整即可。 ???? 方法1： /* 升序 */void HeapSort(int arr[], int n) { for (int i = 1; i < n; i++) { AdjustUp(arr, i); // 传入数组 和 child的下标 }} 我们不需要从 0 开始调，从 1 开始调。所以 i 的起始值设置为 1 。此时，小堆就构建好了。 方法2：向下调整 向下调整算法我们在堆那个章节也学过了，这里我们再来复习一下： void SmallAjustDown(int* arr, int n, int parent) { int child = parent * 2 + 1; // 默认为左孩子 while(child < n) { // 叶子内 // 选出左右孩子中小的那一个 if(child + 1 < n && arr[child + 1] < arr[child]) { child = child + 1; } // 如果孩子小于父亲（不符合小堆的性质） if(arr[child] < arr[parent]) { // 交换它们的值 Swap(&arr[child], &arr[parent]); // 往下走 parent = child; child = parent * 2 + 1; } else { // 如果孩子大于父亲（符合小堆的性质） // 跳出循环 break; } }} ① 因为要考虑左孩子还是右孩子，我们可以定义两个变量，分别记录左孩子和有孩子。但是我们这里可以用更好的方法，只需要定义一个孩子即可。具体实现方法如下：首先创建 child，我们先默认它是左孩子，利用传进来的 parent 根据公式计算出 child 的大小： 因为我们暂且默认为左孩子，我们随后进入循环后要进行检查，看看是左孩子大还是右孩子大，这里我们只需要根据数组的性质，将 child + 1 即可得到右孩子的下标，从而方便我们进行比较。比较完毕后将 child 重新赋值，拿个孩子小就将 child 给谁。 ② 一共有两个结束条件（出口），第一个结束条件是父亲小于孩子就停止，第二个结束条件是chi调整到叶子。所以，循环体判断部分根据我们分析的结束条件，如果调整到叶子就结束，我们接受了 n，也就是数组的大小，只要 child 超过数组的大小（child >

N) it's over, this is the first exit.

After the ③ enters the loop, the child is delivered to whichever child is smaller than the left child or the right child. It should also be noted here that the situation where the child does not exist should be prevented. If child + 1 is larger than n, the child does not exist. So when we write the if judgment condition again, we should pay attention to, we add a child + 1

< n 的条件限制一下： if(child + 1 < n && arr[child + 1] < arr[child]) {...} ④ 确认好较小的孩子后，我们就可以开始比较孩子和父亲的大小了。如果孩子小于父亲，就不符合小堆的性质，我们就要交换它们的值。这里我们直接调用我们刚才写的 Swap 接口即可，这就是为什么在写向上调整的时候要我们单独把交换部分的代码写成函数的原因。 ⑤ 交换完毕后，他们的值已经互相交换好了，这时我们要改变 parent 和 child 的指向，让它们往下走，parent = child ，child 再次根据公式算出新的 child 即可。 ⑥ 设计下 if 的 else 部分，如果数组的 child 的值大于 parent 的值，说明符合小堆的性质了， break 跳出循环即可，这是第二个出口。 向下调整算法的前提：左右子树必须都是小堆 如果左子树和右子树不是小堆，怎么办？ 可以用递归解决，但是我们能用循环就用循环来解决： 叶子所在的子树是不需要调的。所以，我们从倒着走的第一个非叶子结点的子树开始调。 （所以我们先调整30） 为了能够演示得更明显，我们再给数组再加点数据，假设我们需要对以下数组排序： 这里，我们找到了15。 …… 下标不断地 - - 后： 由于，从倒着走的第一个非叶子结点的子树开始调，即，最后一个节点的父亲。 我们已知最后一个节点的下标为： 那么，我们可以通过公式计算出他父亲的下标： ???? 方法2： /* 升序 */void HeapSort(int arr[], int n) { for (int i = (n - 1 - 1) / 2; i >

= 0; iMurt -) {AdjustDown (arr, n, I);}}

⚡ may be able to read it more clearly by writing it this way:

/ * Ascending order * / void HeapSort (int arr [], int sz) {int father = ((sz-1)-1) / 2; / / calculate the father of the last leaf node while (father > = 0) {AdjustDown (arr, sz, father); father--;}}

? Test whether the heap has been created:

We choose to use method 2 here. In addition, what we have just realized is a small pile.

# include / * Exchange function * / void Swap (int* px, int* py) {int tmp = * px; * px = * py; * py = tmp;} / * small heap down * / void AdjustDown (int arr [], int sz, int father_idx) {int child_idx = father_idx * 2 + 1 / / calculate the value of the left child (default is that the left child is older) while (child_idx)

< sz) { // 最坏情況：调到叶子（child >

= array range must have been adjusted to leaf) if ((child_idx + 1)

< sz) && (arr[child_idx + 1] < arr[child_idx])) { // 如果右孩子存在且右孩子比左孩子小 child_idx = child_idx + 1; // 让其代表右孩子 } if (arr[child_idx] < arr[father_idx]) { // 如果孩子的值小于父亲的值（大符合小堆的性質） Swap(&arr[child_idx], &arr[father_idx]); // 交换它们的值 /* 往下走 */ father_idx = child_idx; // 更新下标 child_idx = father_idx * 2 + 1; // 计算出该节点路线的新父亲 } else { // 如果孩子的值大于父亲的值（符合小堆的性质） break; // 终止循环 } }} /* 升序 */void HeapSort(int arr[], int sz) { /* 创建大堆，选出最大的数 O(N) */ int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲 while (father >

= 0) {AdjustDown (arr, sz, father); father--;}} void HeapPrint (int arr [], int sz) {for (int I = 0; I)

< sz; i++) { printf("%d ", arr[i]); } printf("\n");} int main(void){ int arr[] = {70, 56, 30, 25, 15, 10, 75, 33, 50, 69}; int sz = sizeof(arr) / sizeof(arr[0]); HeapSort(arr, sz); HeapPrint(arr, sz); return 0; } ???? 运行结果：10 15 30 25 56 70 75 33 50 69 第二步：排序 刚才介绍了两种方法来构建堆，现在堆已经构建完毕了，我们可以开始设计排序部分的算法了。 ❓ 如果排升序，建小堆…… ① 选出最小的数，放到第一个位置，这很简单，直接取顶部就可以得到最小的数。 ② 但问题来了，如何选出次小的数呢？ 从 15 开始，剩下的元素看作一个堆。但是这之前建立好的堆关系全部乱了！你还得重新建堆，才能选出次小的数。建堆的时间复杂度为 ，需要不断地建堆 则用小堆的时间复杂度就是

Oh, this is outrageous! After a long circle, it turns out that it is not as convenient as going through the selection directly.

It is possible to build a small pile to sort ascending order, but the efficiency is too low! It doesn't show the advantage of using heap at all!

⚡ solution: use large heaps to sort ascending order!

? We have just implemented a small heap. According to the knowledge learned in the previous section, the small heap should be turned into a large heap, just change the "" of the code just now:

# include / * Exchange function * / void Swap (int* px, int* py) {int tmp = * px; * px = * py; * py = tmp;} / * large heap downregulation * / void AdjustDown (int arr [], int sz, int father_idx) {int child_idx = father_idx * 2 + 1 / / calculate the value of the left child (default is that the left child is older) while (child_idx)

< sz) { // 最坏情況：调到叶子（child >

= array range must have been adjusted to leaf) if ((child_idx + 1)

< sz) && (arr[child_idx + 1] >

ARR [child _ idx]) {/ / if the right child exists and the right child is older than the left child child_idx = child_idx + 1 / / Let it represent the right child} if (arr [child _ idx] > arr [child _ idx]) {/ / if the child's value is greater than the father's value (does not match a large number of sexuality) Swap (& arr [child _ idx], & arr [child _ idx]) / / swap their values / * go down * / father_idx = child_idx; / / update subscript child_idx = father_idx * 2 + 1 / / calculate the new father of the node route} else {/ / if the child's value is less than the father's value (in line with a large number of properties) break / / end cycle}} / * Ascending order * / void HeapSort (int arr [], int sz) {/ * create a large heap and select the maximum number O (N) * / int father = ((sz-1)-1) / 2 / / calculate the father of the last leaf node while (father > = 0) {AdjustDown (arr, sz, father); father--;}} void PrintArray (int arr [], int sz) {for (int I = 0; I)

< sz; i++) { printf("%d ", arr[i]); } printf("\n");} int main(void){ int arr[] = {70, 56, 30, 25, 15, 10, 75, 33, 50, 69}; int sz = sizeof(arr) / sizeof(arr[0]); HeapSort(arr, sz); PrintArray(arr, sz); return 0; } ???? 运行结果：75 69 70 50 56 10 30 33 25 15 ???? 现在改成了大堆，我们要排升序，我们可以让堆顶数和最后的数进行交换： 这并不会带来堆结构的破坏！我们把75不看作堆的一部分即可。再进行向下调整，就可以找到次小的数了。此时时间复杂度为 ???? 步骤总结： ① 建大堆，选出最大的数。 ② 最大的数跟最后一个数交换。 ③ 如何选出次大的数呢？把最后一个数不看作堆里面，进行向下调整。 ???? 代码实现（用 while）： /* 堆排序 - 升序 */void HeapSort(int arr[], int sz) { /* 创建大堆，选出最大的数 O(N) */ int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲 while (father >

= 0) {AdjustDown (arr, sz, father); father--;} / * select the number in turn, adjust the heap O (N * logN) * / int end = sz-1; while (end > 0) {Swap (& arr [0], & arr [end]) / / the largest number and the last number exchange AdjustDown (arr, end, 0); / / heap to select the next largest number end--;}}

? Code implementation (in for):

Void HeapSort (int arr [], int sz) {/ * heap * / for (int father = (sz-1-1) / 2; father > = 0; father--) {AdjustDown (arr, sz, father);} / * sort * / for (int end = sz-1; end > 0 End--) {Swap (& arr [0], & ARR [end]); / / the largest number is exchanged with the last number AdjustDown (arr, end, 0); / / heap, select the next largest number}} III. Complete code

(to build a large pile in ascending order and a small pile in descending order)

? Ascending order: using large heaps

# define _ CRT_SECURE_NO_WARNINGS 1#include void Swap (int* pa, int* pb) {int tmp = * pa; * pa = * pb; * pb = tmp;} void AdjustDown (int arr [], int sz, int father) {int child = father * 2 + 1; while (child

< sz) { if (child + 1 < sz && arr[child + 1] >

Arr [child]) {child + = 1;} if (arr [child] > arr [father]) {Swap (& arr [child], & arr [child]); father = child; child = father * 2 + 1 } else {break;} / * Heap sort-Ascending order * / void HeapSort (int arr [], int sz) {/ * create a large heap and select the maximum number O (N) * / int father = ((sz-1)-1) / 2 / / calculate the father of the last leaf node while (father > = 0) {AdjustDown (arr, sz, father); father--;} / * select the number in turn, and adjust the heap O (N * logN) * / int end = sz-1 While (end > 0) {Swap (& arr [0], & arr [end]); / / the largest number is exchanged with the last number AdjustDown (arr, end, 0); / / the heap is adjusted to select the next largest number end--;}} void HeapPrint (int arr [], int sz) {int I = 0 For (I = 0; I)

< sz; i++) { printf("%d ", arr[i]); } printf("\n");} int main(void){ int arr[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 }; int sz = sizeof(arr) / sizeof(arr[0]); printf("排序前: "); HeapPrint(arr, sz); HeapSort(arr, sz); printf("排序后: "); HeapPrint(arr, sz); return 0;} ???? 运行结果： ❓ 如果要排降序呢？使用小堆即可！ ???? 降序：使用小堆 #include /* 交换函数 */void Swap(int* px, int* py) { int tmp = *px; *px = *py; *py = tmp;} /* 小堆下调 */void AdjustDown(int arr[], int sz, int father_idx) { int child_idx = father_idx * 2 + 1; // 计算出左孩子的值（默认认为左孩子大） while (child_idx < sz) { // 最坏情況：调到叶子（child >

= array range must have been adjusted to leaf) if ((child_idx + 1)

< sz) && (arr[child_idx + 1] < arr[child_idx])) { // 如果右孩子存在且右孩子比左孩子小 child_idx = child_idx + 1; // 让其代表右孩子 } if (arr[child_idx] < arr[father_idx]) { // 如果孩子的值小于父亲的值（不符合小堆的性質） Swap(&arr[child_idx], &arr[father_idx]); // 交换它们的值 /* 往下走 */ father_idx = child_idx; // 更新下标 child_idx = father_idx * 2 + 1; // 计算出该节点路线的新父亲 } else { // 如果孩子的值大于父亲的值（符合小堆的性质） break; // 终止循环 } }} /* 堆排序 - 降序 */void HeapSort(int arr[], int sz) { /* 创建大堆，选出最大的数 O(N) */ int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲 while (father >

= 0) {AdjustDown (arr, sz, father); father--;} / * select the number in turn, adjust the heap O (N * logN) * / int end = sz-1; while (end > 0) {Swap (& arr [0], & arr [end]) / / the largest number exchanges AdjustDown (arr, end, 0) with the last number; / / heaps to select the next smallest number end--;}} void PrintArray (int arr [], int sz) {for (int I = 0; I)

< sz; i++) { printf("%d ", arr[i]); } printf("\n");} int main(void){ int arr[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 }; int sz = sizeof(arr) / sizeof(arr[0]); printf("排序前: "); PrintArray(arr, sz); HeapSort(arr, sz); printf("排序后: "); PrintArray(arr, sz); return 0;} ???? 运行结果： 四、证明建堆的时间复杂度 因为堆是完全二叉树，而满二叉树也是完全二叉树。此处为了简化，将采用满二叉树来证明。（时间复杂度本来看的就是近似值，所以多几个节点不会影响最终结果）： 假设树的高度为： 第 层：个节点，需要向下移动层 第层：

Nodes, you need to move the layer down

Layer: one node, you need to move the layer down

Layer: a node, you need to move the layer down

……

Layer: nodes that need to move down the layer

The total number of mobile steps required for the mobile node is:

one

two

②-① dislocation subtraction:

Therefore, the time complexity of building a heap is

The above is all the content of the article "how to use heap sorting in C language". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.