【数据结构指南】堆排序和TopK

Ne0inhk

— 23 min read
【数据结构指南】堆排序和TopK

前言：

        在上一篇博客中，我们深入了解了堆的基础概念并完成了堆结构的具体实现。

        本篇将继续探讨堆在实际应用中的使用场景，重点分析两个核心应用：高效的堆排序算法和解决TopK问题的巧妙方法。

        

一、建堆

        

建堆算法是将无序数组转化为符合“堆规则”的完全二叉树（逻辑结构）的核心方法，是堆排序、Top K等所有堆应用的基础。

                

相比于通过数据结构中堆的插入建堆，需要额外O(N)的空间复杂度，基于数组原地实现建堆，仅需要O(1)的空间复杂度。        

        

1.1向上调整算法的回顾

        

场景实例：假设现在存在一个小堆，要向堆中插入一个元素，并维持堆的结构。

        

A.核心逻辑

        

①新元素插入堆尾后，它的父节点可能比新插入子节点小 —— 让新元素“ 上浮 ”，与父节点交换，直到它比父节点小，或浮到根节点（堆顶）。

                     

②简而言之，对于向上调整算法的核心思维就是：当子节点可能比父节点 “更合适”时，需要让子节点往上浮，找到合适位置。        

        

B. 实例分析

        

一、如上图所示，由于新插入的子节点的值为  10  与 其父亲节点的值 28 相比 不满足小堆的关系，所以我们需要让子节点向上浮动，直到它比父节点更小，或者一直向上浮动到根节点为止。

        

        

二、详解向上调整的过程

        

( 1 ) 上图中原来的小堆为: [15 , 18 , 19 , 25 , 28 , 34 , 65 , 49 , 27 , 37] ，堆中元素个数size=10，

        

       现需要插入一个元素 10 （放在堆尾索引为10的位置处）

       

        

( 2 ) 新插入的子节点的索引为 child = 10  插入后小堆变为：   [15 , 18 , 19 , 25 , 28 , 34 , 65 , 49 , 27 , 37，10]

        

        计算得到其父亲节点的索引为  parent=( child - 1 ) / 2  , 即索引为4 ，arr[4]=28。

        

        

( 3 )比较arr[child] 与 arr[parent] 的值，由于要维持小堆，所以当arr[child] < arr [parent] 时，就要对子节点和父亲节点进行交换

        

      交换后的小堆变为： [15 , 18 , 19 , 25 , 10 , 34 , 65 , 49 , 27 , 37，28]

        

        

( 4 )更新孩子节点的索引和父亲节点的索引：child=parent ;   parent=(child-1) / 2 ;

        

        

( 5 ) 重复这个过程，直到满足新插入的子节点比父节点更小，或者一直向上浮动到根节点为止，所以我们可以通过循环进行描述上述三个步骤。

                

                

三、向上调整算法的应用

        

void AdjustUp(HPDataType* a, int child) { //已知孩子节点的下标为child //父亲节点下标为:(child-1)/2 //初始时父亲节点的下标 int parent = (child - 1) / 2; while (child > 0) { if (a[child] < a[parent]) { //进行交换 swap(&a[child], &a[parent]); //更新孩子节点的下标 child = parent; //更新父亲节点的下标 parent = (child - 1) / 2; } else { break; } } //退出条件为： //1.子节点比父节点大 //2.子节点到达根的位置 }

        

        

四、若原来是大堆，只需把比较符号反转,将 “<” 变为 “>”, 即当前节点 > 父节点（大根堆性质破坏），则交换并继续上浮。

        

        

1.2利用向上调整算法建堆

       

        基于向上调整算法的思想，我们可以对任何一个数组进行建堆（大堆或小堆），通过循环，传入数组中的每个元素，及其下标，相当于对数组中的每个元素进行向上调整，即完成了建堆。

        

代码示例：

        

void swap(int *a,int *b) { int tmp=*a; *a=*b; *b=tmp; } //向上调整算法 void AdjustUp(HPDataType* a, int child) { //已知孩子节点的下标为child //父亲节点下标为:(child-1)/2 //初始时父亲节点的下标 int parent = (child - 1) / 2; while (child > 0) { if (a[child] < a[parent]) { //进行交换 swap(&a[child], &a[parent]); //更新孩子节点的下标 child = parent; parent = (child - 1) / 2; } else { break; } } } void PrintArray(int arr[], int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } } int main() { int arr[] = { 9,6,4,7,5,3,2,1 }; int size = sizeof(arr) / sizeof(arr[0]); printf("建堆前的数组: \n"); PrintArray(arr, size); for (int i = 0; i < size; i++) { AdjustUp(arr, i); } printf("\n建堆后的数组：\n"); PrintArray(arr, size); return 0; }

        

如下图所示建堆：

        

时间复杂度分析:

        由于堆是一棵完全二叉树，对于完全二叉树的高度h，满足h≈log2(N) ，最坏的情况下，需要从叶节点一直到根节点，向上浮动h次，故而向上调整算法的时间复杂度为O（logN）。

        对于一个数组而言有N个元素，即有N个节点，每个节点的最坏情况都是需要从叶节点到根节点，故而向上调整算法建堆的时间复杂度为：O(N*logN)

        

                

1.3 向下调整算法的回顾

        

场景实例：假设现在存在一个小堆，若堆顶元素被一个更大的值替代，并维持堆的结构。

        

A.核心思维

        

当父节点位置可能比子节点位置“不合适”时，需要让父节点往下沉，找到合适位置。

        

        

B.实例分析   

                  

 一、如上图所示，原堆顶元素5被更大的元素27替换后，破坏了小堆性质。

        

此时父节点位置已不满足条件，所以需要通过向下调整操作，直到它比子节点更小，或者到达叶节点位置

        

（温馨提示：判断是否到达叶节点位置，即只需要判断其子节点不在堆的范围内，循环的停止条件）。

        

二、详解向下调整的过程

        

( 1 ) 上图中原来的小堆为：[5，15，19，18，28，34，65，49，25，37] ，但是堆顶元素被替换为27，

        

        则现在的小堆变为：[27，15，19，18，28，34，65，49，25，37],此时堆中的元素不在满足小堆的特性,需要进行向下调整。

        

        

( 2 )  此时父亲节点的索引为：parent=0，

        

        其左孩子节点的索引为：leftchild=parent * 2 + 1 ，其右孩子节点的索引为：rightchild=parent*2+2。

        

        我们不能确定左孩子节点的值与右孩子节点的值的大小关系，所以需要进行比较确定出其中最小的一个。

        

        这里可以通过假设法，不用单独区分左孩子节点的索引和右孩子节点的索引，只需定义一个子节点索引child，然后假设左孩子节点的值最小，

        

        若左孩子节点的值大于右孩子节点的值，即右孩子节点的更小，仅需要对child++即可找到右孩子节点。

        

        

( 3 ) 比较arr[parent]与arr[child]的值，由于需要维持小堆，如果arr[parent]>arr[child],需要对父节点和子节点进行交换。

       

        交换后的小堆为：[15，27，19，18，28，34，65，49，25，37]

        

        

( 4 ) 更新parent的索引和child的索引：parent=child; child=parent * 2 + 1; 

        

        

( 5 ) 重复这个过程，直到它比子节点更小，或者到达叶节点位置（叶节点位置处满足：子节点不在堆的范围内）。

        

三、向下调整代码的实现：

        

void AdjustDown(HPDataType* a, int size, int parent) { //父亲节点下标：parent //左孩子节点下标为：parent*2+1 //右孩子节点下标为：parent*2+2 //假设左孩子是最小的 int child = parent * 2+1; while (child < size) { //保证child+1在有效范围 if (child+1 < size && a[child + 1] < a[child] ) { child++; } if (a[child] < a[parent]) { //交换父亲节点和孩子节点 swap(&a[child], &a[parent]); //更新父亲节点 parent = child; //更新孩子节点 child = parent * 2 + 1; } else { break; } } //退出循环的条件 //1.父节点无子节点，即到达了叶节点位置，通过不满足while循环条件退出 //2.父节点的值 < 子节点的值，通过break退出 }

        

四、若原来是大堆，只需把比较符号反转,将 “<” 变为 “>”, 即当前节点 > 父节点（大根堆性质破坏），则交换并继续下浮。

        

        

1.4利用向下调整算法建堆

        

        向下调整能建堆，本质是利用 “ 完全二叉树的特性 ”+“ 从后向前 ” 的调整顺序，让每个非叶子节点调整后，其所在的子树都符合堆规则，最终扩散到整个树，形成完整堆。

        这是一种局部到整体的思维，对于叶子节点而言，其可以被视为堆，所以只需要对非叶子节点所在的子树进行向下调整，直到每个节点所在的子树都满足堆的特性即完成了建堆。        

        

代码示例：

void swap(int *a,int *b) { int tmp=*a; *a=*b; *b=tmp; } void AdjustDown(int* a, int size, int parent) { //父亲节点下标：parent //左孩子节点下标为：parent*2+1 //右孩子节点下标为：parent*2+2 //假设左孩子是最小的 int child = parent * 2+1; while (child < size) { //保证child+1在有效范围 if (child+1 < size && a[child + 1] < a[child] ) { child++; } if (a[child] < a[parent]) { //交换父亲节点和孩子节点 swap(&a[child], &a[parent]); //更新父亲节点 parent = child; //更新孩子节点 child = parent * 2 + 1; } else { break; } } //退出循环的条件 //1.父节点无子节点，即到达了叶节点位置，通过不满足while循环条件退出 //2.父节点的值 < 子节点的值，通过break退出 } void PrintArray(int arr[], int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } } int main() { int arr[] = { 9,6,4,7,5,3,2,1 }; int size = sizeof(arr) / sizeof(arr[0]); printf("建堆前的数组: \n"); PrintArray(arr, size); //注意： //参数i初始时:给定的是最后一个叶子结点的父亲结点 for (int i = (size-1-1)/2; i>=0 ; i--) { AdjustDown(arr, size, i); } printf("\n建堆后的数组：\n"); PrintArray(arr, size); return 0; }

        

        

如图所示：

        

        

时间复杂度分析: 以满二叉为例，对于向下调整算法建堆，时间复杂度为O(N)，分析如下所示

        

        

        

二、堆排序

             堆是堆排序的 核心数据结构，其核心价值是“ 高效维护最大值 或 最小值 ”，堆排序的所有逻辑都围绕堆的这一特性展开，本质是把 “ 无序数组 ” 通过堆转化为 “ 有序序列 ”的过程。

        

核心步骤：

    1.建堆：排序前的数组是完全无序的（比如： [4,6,8,5,9,1,3,2,7]），此时无法直接快速找到最大值 或 最小值。

       堆的第一个作用就是：将无序数组转化为 大堆 或者 小堆，让数组满足 “堆顶是最大值 或 堆顶是最小值” 的特性。       

        

   2.反复 “取堆顶（最大值 或 最小值）+ 修复堆”，构建有序序列：

        建堆后，数组的最大值已经在堆顶，但其他元素仍无序。

        堆的第二个作用是：持续提供（最大值 或 最小值），并快速修复堆结构，让每次都能高效取到 “剩余元素的（最大值或最小值）”。

        

        

2.1 升序：建大堆

        

        为什么说升序建大堆更合理，而不是建小堆更合理呢，这里是很多帅观众的疑惑？

        我们知道，小堆的堆顶是堆中最小的元素，对于升序而言，需要每次把最小值放在数组的最前面，而第一个元素已经是最小值了，所以需要从第二个元素开始进行排列。

        但我们发现，以第二个元素为堆顶，其堆的结构就已经破坏了，需要再次对以第二个元素为堆顶进行建小堆，这样每次的消耗过大，所以更好的方式为：建大堆，请听我娓娓道来。

        

核心思想：

        

①目标：将数组排成 升序（小元素在前，大元素在后）

        

②堆类型：大堆（父节点 >= 子节点，堆顶是当前最大值）

        

③核心操作：建初始大堆 → 循环交换堆顶（最大值）与堆尾 → 调大堆。

        

步骤一：将无序数组建成大堆。

        

步骤二：将堆顶元素与最末尾元素进行互换，如图所示，将堆中最大的元素9与堆尾元素1进行互换，则最大元素放在了堆尾，最大值 9 被固定到数组末尾（最终位置），后续不再处理，未排序区域缩小为[1，7，8，2，5，6，4]。

        

        

步骤三：将堆尾元素1与堆顶元素交换后，此时堆顶元素为1，破坏了大堆的性质，所以需要进行向下调整，找出次大的元素放置堆顶。

        

        

步骤四：重复这个过程，即可将无序数组，排列成有序数组。

        

代码实现：

#include<stdio.h> void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } void maxHeapify(int* arr, int size, int parent) { //假设左孩子节点最大 int child = parent * 2 + 1; //进行向下调整,到根节点就退出即 child>=size while ( child< size ) { //假设失败，右孩子大于左孩子 if (child + 1 < size && arr[child + 1] > arr[child]) { child++; } if (arr[child] > arr[parent]) { Swap(&arr[child], &arr[parent]); //更新父亲节点 parent = child; //更新孩子节点 child = parent * 2 + 1; } else { break; } } } void HeapSort(int *a,int size) { //利用向下调整算法进行建堆 for (int i = (size - 1 - 1) / 2; i >= 0; i--) { maxHeapify(a, size, i); } //end为队尾一个元素的下标 int end = size - 1; //end=0即为最后一个元素无需排序 while (end > 0) { swap(&a[0], &a[end]); //交换后需要向下调整的元素个数为end maxHeapify(a, end, 0); --end; } } void testHeapSort() { int a[8] = { 4 , 2 , 8 , 1 , 5 , 6 , 9 , 7 }; printf("未进行堆排之前的元素顺序：\n"); for (int i = 0; i < 8; i++) { printf("%d ", a[i]); } HeapSort(a, 8); printf("\n进行堆排之后的元素顺序：\n"); for (int i = 0; i < 8; i++) { printf("%d ", a[i]); } } int main() { testHeapSort(); return 0; }

        

        

2.2 降序：建小堆

        

同理，若降序建小堆，通过将堆顶元素与堆尾元素进行交换后，然后不断进行调小堆，即可让堆中的最小元素放在堆尾，通过不断进行该操作即可让无序数组变成有序。

        

核心思想：

        

①目标：将数组排成 降序（大元素在前，小元素在后）

        

②堆类型：小顶堆（父节点 ≤ 子节点，堆顶是当前最小值）

        

③核心操作：建初始小堆 → 循环交换堆顶（最小值）与堆尾 → 调小堆」。

        

步骤一：将无序数组建成小堆。

        

步骤二：将堆顶元素与最末尾元素进行互换，如图所示，将堆中最小的元素1与堆尾元素7进行互换，则最小元素放在了堆尾，最小值1被固定到数组末尾（最终位置），后续不再处理，未排序区域缩小为[7，2，6，4，5，8，9]。

        

        

步骤三：将堆顶元素1与堆尾元素交换7后，此时堆顶元素为7，破坏了小堆的性质，所以需要进行向下调整，找出次小的元素放置堆顶。

        

        

步骤四：重复这个过程，即可将无序数组，排列成有序数组。

        

        

代码示例： 

       

#include<stdio.h> void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } void minHeapify(int* a, int size, int parent) { //父亲节点下标：parent //左孩子节点下标为：parent*2+1 //右孩子节点下标为：parent*2+2 //假设左孩子是最小的 int child = parent * 2 + 1; while (child < size) { if (child + 1 < size && a[child + 1]< a[child] ) { child++; } if (a[child] < a[parent]) { //交换父亲节点和孩子节点 Swap(&a[child], &a[parent]); //更新父亲节点 parent = child; //更新孩子节点 child = parent * 2 + 1; } else { break; } } } void HeapSort(int *a,int size) { //利用向下调整算法进行建堆 for (int i = (size - 1 - 1) / 2; i >= 0; i--) { minHeapify(a, size, i); } //end为队尾一个元素的下标 int end = size - 1; //end=0即为最后一个元素无需排序 while (end > 0) { swap(&a[0], &a[end]); //交换后需要向下调整的元素个数为end minHeapify(a, end, 0); --end; } } void testHeapSort() { int a[8] = { 4 , 2 , 8 , 1 , 5 , 6 , 9 , 7 }; printf("未进行堆排之前的元素顺序：\n"); for (int i = 0; i < 8; i++) { printf("%d ", a[i]); } HeapSort(a, 8); printf("\n进行堆排之后的元素顺序：\n"); for (int i = 0; i < 8; i++) { printf("%d ", a[i]); } } int main() { testHeapSort(); return 0; }

        

三、topk问题

        

TopK 问题是算法中的经典场景 ——从海量数据（N个元素）中找出前 k 个最大 / 最小的元素。

比如：在1千万个人中，找出前10个最富有的人； 找出 1百万条数据中前 5 个最小的数 , 诸如此类问题，我们称之为TopK问题。

        

方法一：

        可以通过使用堆这个数据结构，通过建小堆 / 建大堆 的方式取出堆顶元素，然后进行向下调整，找出次小的元素放在堆顶，然后取出次小的堆顶，依次重复k次，即可找出前 k 个最大 / 最小的元素。 

        

但这样会面临一个问题，在建堆的时候，需要存储海量的数据，导致空间复杂度过高

假设需要存储10亿个整数

        

根据1GB=1024MB=1024×1024KB=1024×1024×1024Byte

        

需要大约4GB的内存，即使是放在文件磁盘中也是一个不小的消耗。

方法二：

               以找出 1百万条数据中前 k 个最大的数为例，可以先建立k个大小为整形的大堆，然后将N-k个数据与堆顶数据进行比较，如果比堆顶的数据更大，则替代堆顶的数据，然后进行向下调整，继续维持堆的特性。

代码示例：

        

#define _CRT_SECURE_NO_WARNINGS #include"Heap.h" #include<time.h> const int N = 10000; void swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } void AdjustDown(int* a, int size, int parent) { //父亲节点下标：parent //左孩子节点下标为：parent*2+1 //右孩子节点下标为：parent*2+2 //假设左孩子是最小的 int child = parent * 2+1; while (child < size) { if (child+1<size && a[child] > a[child + 1] ) { child++; } if (a[child] < a[parent]) { //交换父亲节点和孩子节点 swap(&a[child], &a[parent]); //更新父亲节点 parent = child; //更新孩子节点 child = parent * 2 + 1; } else { break; } } } //从N个数中，选出K个最大的数 void TopK(int *a,int k) { int* kheap = malloc(sizeof(int) * k); if (kheap == NULL) { perror("malloc fail"); return; } //读入k个数据 for (int i = 0; i < k; i++) { kheap[i] = a[i]; } //利用向下调整建小堆 //从第一个非叶子节点开始调整到根的位置 for (int i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(kheap, k, i); } //比较N-K个数据 for (int i = k; i < N; i++) { if (kheap[0] < a[i]) { kheap[0] = a[i]; AdjustDown(kheap, k, 0); } } printf("最大的十个数为: "); for (int i = 0; i < k; i++) { printf("%d ", kheap[i]); } } void testTopK() { int k; printf("请输入k值: "); scanf("%d", &k); int* arr =(int *)malloc(sizeof(int) * N); if (arr == NULL) { perror("arr malloc fail"); return 0; } srand((time_t)time(0)); for (int i = 0; i < N; i++) { arr[i] = rand()%10000+i; } arr[10] = 1000000 + 1; arr[11] = 1000000 + 2; arr[12] = 1000000 + 3; arr[13] = 1000000 + 4; arr[14] = 1000000 + 5; arr[15] = 1000000 + 6; arr[16] = 1000000 + 7; arr[17] = 1000000 + 8; arr[18] = 1000000 + 9; arr[19] = 1000000 + 10; TopK(arr, k); } int main() { testTopK(); return 0; }

        

既然看到这里了，不妨关注+点赞+收藏，感谢大家，若有问题请指正。

Read more

Flutter 三方库 xpath_selector 的鸿蒙化适配指南 - 在鸿蒙系统上构建极致、透明、精准的 HTML/XML 数据抓取与 Web 结构解析引擎

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 xpath_selector 的鸿蒙化适配指南 - 在鸿蒙系统上构建极致、透明、精准的 HTML/XML 数据抓取与 Web 结构解析引擎 在鸿蒙（OpenHarmony）系统的网络爬虫、自动化测试审计、或者是从复杂的第三方 Web 公告（HTML）中提取关键数据（如新闻标题、资产负债表）时，如何摆脱凌乱的正向正则（Regex），转而使用业界标准的 XPath 语法进行语义化选取？xpath_selector 为开发者提供了一套工业级的、基于 Dart 的 HTML/XML 结构化查询方案。本文将深入实战其在鸿蒙端数据治理中的应用。 前言 什么是 XPath Selector？

By Ne0inhk

Java 算法实践（七）：动态规划

这回溯算法本质上是一种暴力的穷举搜索，它遍历了问题的所有可能性（状态空间树）。然而，在许多问题中，回溯搜索会产生大量的重叠子问题，导致计算资源的极度浪费。 动态规划（Dynamic Programming, DP） 动态规划并非一种具体的算法，而是一种数学优化的思维方式。是一种通过将复杂问题分解为子问题，并存储子问题的解以避免重复计算的算法技术。它与分治法（Divide and Conquer）的区别在于：分治法的子问题通常是独立的（如归并排序），而动态规划的子问题是重叠的。 DP 的核心思想是空间换时间。通过维护一个表格（Table，通常是数组）来记录已经计算过的状态，将指数级的时间复杂度优化为多项式级（通常是线性或平方级）。 一、 从递归到动态规划：思维演进 理解 DP 的最佳路径是从斐波那契数列（Fibonacci）开始。虽然这是一个简单的数学问题，但它完美展示了算法复杂度的演变。 1.1 暴力递归 斐波那契数列定义： f ( n ) = f ( n − 1

By Ne0inhk
【数据结构入坑指南（三.1）】--《面试必看：单链表与顺序表之争，读懂“不连续”之美背后的算法思想》

【数据结构入坑指南（三.1）】--《面试必看：单链表与顺序表之争，读懂“不连续”之美背后的算法思想》

🔥@晨非辰Tong：个人主页  👀专栏：《C语言》、《数据结构与算法》 💪学习阶段：C语言、数据结构与算法初学者 ⏳“人理解迭代，神理解递归。” 引言：学完顺序表，深受其扩容和插入删除低效之苦？ 是时候认识单链表了。它用指针串联数据，以“不连续”的物理结构，完美解决了顺序表的痛点。 接下来，让我们一起探索这种更优雅的数据结构。 目录 一、单链表特性全解 1.1  单链表：数据的"一线牵" 1.2  单链表结构：数据的“小火车” 二、单链表的实现（初） 2.1  铺垫 2.2  单链表尾插 2.3  单链表头插 2.4

By Ne0inhk
别再让类型限制你的代码！【Java包装类+泛型】，让数据结构开发一步到位

别再让类型限制你的代码！【Java包装类+泛型】，让数据结构开发一步到位

🎁个人主页：User_芊芊君子 🎉欢迎大家点赞👍评论📝收藏⭐文章 🔍系列专栏：Java.数据结构 【前言】 在Java中，包装类为基本数据类型提供对象封装，实现基本类型与对象的无缝转换；泛型则通过类型参数化，实现代码的通用复用并在编译期保证类型安全。二者结合，让数据结构能灵活适配多种类型，同时兼顾安全性与开发效率，是Java实现高效、通用数据操作的核心技术组合。 文章目录： * 一、包装类 * 1. 什么是包装类？ * 2.基本数据类型与包装类对应表 * 3.装箱和拆箱 * 二、泛型 * 1.什么是泛型？ * 2.基本语法 * 3.引出泛型 * 4.泛型的使用 * 5.擦除机制 * 5.泛型的上界 * 5.1语法 * 5.2 示例 * 6.

By Ne0inhk