当前位置： 首页 > news >正文

堆+堆排序+topK问题

news 2025/5/7 3:31:34

目录

堆：

1、堆的概念

2、堆的结构

3、堆的实现

3.1、建堆

3.1.1、向上调整建堆(用于堆的插入)

3.1.2、向下调整建堆

3.2、堆的删除

3.3、堆的代码实现

3.3.1、Heap.h

3.3.2、Heap.c

堆排序：（O(N*log(N))）

1、排序如何建堆

2、代码实现(以小堆为例)

topK问题：

1、方法1

2、方法2

堆：

1、堆的概念

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2、堆的结构

1、堆中某个结点的值总是<=或>=其父结点的值

2、堆 逻辑上 是一棵完全二叉树，物理上 是数组

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆

3、堆的实现

3.1、建堆

typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;
3.1.1、向上调整建堆(用于堆的插入)

适用：

1、已经是堆了，要进行插入时，只能用向上调整建堆

2、对于数组(N个元素)，可以用向上调整建堆，模拟插入的过程(插入一个，调整一次)，但是其时间复杂度为O(N*log(N))，对于一堆的数据，不建议使用，向上调整建堆

void AdjustUp(HPDataType* a, int child)//建小堆，child为插入元素的下标
{assert(a);int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent])//要建大堆，< 改 >{Swap(&a[parent], &a[child]);child = parent;parent = (parent - 1) / 2;}elsebreak;//没有交换，则就是在这个位置}
}int main()
{int arr[] = { 7,4,1,7,9,3,5,2,6,10 };int sz = sizeof(arr) / sizeof(arr[0]);for (int i = 0; i < sz; i++){AdjustUp(arr, i);}return 0;
}

 3、O(N*log(N))证明

节点数量为N个，根节点为第1层，树的高度为h层，h = log(N+1)

第h层   ：2^(h-1)个节点，向上调整h-1次

第h-1层：2^(h-2)个节点，向上调整h-2次

第2层   ：2^1个节点，向上调整1次

第1层   ：2^0个节点，向上调整0次

F(h) = 2^0 * 0 + 2^1 * 1 + ……+ 2^(h-2) * (h-2) + 2^(h-1) * (h-1) = 2^h * (h-2) + 2

        = (N+1)*(log(N+1) - 2) + 2   ，忽略后为 N*log(N)

3.1.2、向下调整建堆

适用：

1、对于数组(N个元素)，建议使用 向下调整建堆 时间复杂度为O(N)，更高效

2、向下调整建堆的前提：左右子树必须是堆(保证向下调整完后，还是堆)，因此，从第一个非叶子节点开始(对于叶子节点，可以认为就是堆)，向下调整建堆

void AdjustDown(HPDataType* a, int n, int parent)//建小堆,n为a的元素个数，parent为要向下调整的元素下标
{assert(a);int child = 2 * parent + 1;while (child < n){if (a[child] > a[child + 1] && child + 1 < n)//假设法，要建大堆，< 改 >child++;if (a[child] < a[parent])//要建大堆，< 改 >{Swap(&a[parent], &a[child]);parent = child;child = 2 * child + 1;}elsebreak;}
}int main()
{int arr[] = { 7,4,1,7,9,3,5,2,6,10 };int sz = sizeof(arr) / sizeof(arr[0]);for (int i = (sz - 1 - 1) / 2; i >= 0; i--)//倒数第一个非叶子节点，开始遍历{AdjustDown(arr, sz, i);}return 0;
}

3、 O(N)证明

节点数量为N个，根节点为第1层，树的高度为h层，h = log(N+1)

第h层   ：2^(h-1)个节点，向下调整0次

第h-1层：2^(h-2)个节点，向下调整1次

第2层   ：2^1个节点，向上调整h-2次

第1层   ：2^0个节点，向上调整h-1次

F(h) = 2^0 * (h-1) + 2^1 * (h-2) +……+ 2^(h-2) * 1 + 2^(h-1) * 0 = 2^h - 1 - h = N - log(N+1)

忽略后为  N

3.2、堆的删除

删除最后一个元素，无意义，删除堆是删除堆顶的数据，

如果是挪动数据，关系乱了，要重新建堆，效率低

所以将堆顶的数据和最后一个数据交换，size--，再进行向下调整算法

void HeapPop(Heap* php)
{assert(php);assert(php->_size > 0);Swap(&(php->_a[0]), &(php->_a[php->_size - 1]));php->_size--;AdjustDown(php->_a, php->_size, 0);
}

3.3、堆的代码实现

3.3.1、Heap.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);void HeapInit(Heap* php);
void HeapDestory(Heap* php);
void HeapPush(Heap* php, HPDataType x);
void HeapPop(Heap* php);
HPDataType HeapTop(Heap* php);
int HeapSize(Heap* php);
int HeapEmpty(Heap* php);
3.3.2、Heap.c
#include "Heap.h"void HeapInit(Heap* php)
{assert(php);php->_a = NULL;php->_size = php->_capacity = 0;
}void HeapDestory(Heap* php)
{assert(php);free(php->_a);php->_a = NULL;php->_size = php->_capacity = 0;
}void HeapCapacity(Heap* php)
{assert(php);if (php->_size == php->_capacity){php->_capacity = php->_capacity == 0 ? 4 : 2 * php->_capacity;HPDataType* tmp = (HPDataType*)realloc(php->_a,sizeof(HPDataType) * php->_capacity);if (tmp == NULL){perror("HeapCapacity()::realloc()");return;}php->_a = tmp;}
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)//建小堆,child为插入元素的下标
{assert(a);int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent])//要建大堆，< 改 >{Swap(&a[parent], &a[child]);child = parent;parent = (parent - 1) / 2;}elsebreak;//没有交换，则就是在这个位置}
}void AdjustDown(HPDataType* a, int n, int parent)//建小堆,n为a的元素个数,parent为要向下调整的元素下标
{assert(a);int child = 2 * parent + 1;while (child < n){if (a[child] > a[child + 1] && child + 1 < n)//假设法，要建大堆，< 改 >child++;if (a[child] < a[parent])//要建大堆，< 改 >{Swap(&a[parent], &a[child]);parent = child;child = 2 * child + 1;}elsebreak;}
}void HeapPush(Heap* php, HPDataType x)
{assert(php);HeapCapacity(php);//扩容php->_a[php->_size++] = x;AdjustUp(php->_a, php->_size-1);
}void HeapPop(Heap* php)
{assert(php);assert(php->_size > 0);Swap(&(php->_a[0]), &(php->_a[php->_size - 1]));php->_size--;AdjustDown(php->_a, php->_size, 0);
}HPDataType HeapTop(Heap* php)
{assert(php);assert(php->_size > 0);return php->_a[0];
}int HeapSize(Heap* php)
{assert(php);return php->_size;
}int HeapEmpty(Heap* php)
{assert(php);if (php->_size == 0)return 1;elsereturn 0;
}

堆排序：（O(N*log(N))）

对于数组，建堆时，用向下调整建堆，效率高，

此时是一定程度脱离了堆这个数据结构(没有用push，向上调整建堆)，只是用了向下调整的方法

1、排序如何建堆

升序：建大堆

如果建小堆，第1个数已经排好了，后面的数据，关系乱了（兄弟变父子，左右子树很可能不是堆了），要多次向下调整，才建好堆，效率低，

那建大堆，首尾交换(兄弟还是兄弟，左右子树还是堆，一次向下调整就建好堆)，再伪删除，"删除"完，就排好升序了

建堆(向下调整)，时间复杂度为O(N)

排序(首尾交换，向下调整)，时间复杂度为O(N*log(N))

节点数量为N个，根节点为第1层，树的高度为h层，h = log(N+1)

第h层   ：2^(h-1)个节点，交换，向下调整h-1次

第h-1层：2^(h-2)个节点，交换，向下调整h-2次

第2层   ：2^1个节点，交换，向下调整1次

第1层   ：2^0个节点，交换，向下调整0次

F(h) = 2^0 * 0 + 2^1 * 1 + ……+ 2^(h-2) * (h-2) + 2^(h-1) * (h-1) = 2^h * (h-2) + 2

        = (N+1)*(log(N+1) - 2) + 2   ，忽略后为 N*log(N)

降序：建小堆

依次类推

2、代码实现(以小堆为例)

void Heapsort(int* arr,int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--)//倒数第一个非叶子节点，开始遍历{AdjustDown(arr, n, i);}int end = n;while (end>1){Swap(&(arr[0]), &(arr[end-1]));end--;//伪删除AdjustDown(arr,end,0);}
}int main()
{int arr[] = { 7,4,1,7,9,3,5,2,6,10 };int sz = sizeof(arr) / sizeof(arr[0]);Heapsort(arr,sz);return 0;
}

topK问题：

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般N远大于K

以下 以找出前K个最大的数为例  N远大于K

1、方法1

建N个数的大堆O(N)

popK次            O(K*log(N))

时间复杂度为O(N)，但对空间要求太大

2、方法2

建一个K个小堆(先从文件里读K个元素，向下调整建堆)，再从文件里读一个个元素，大于堆顶元素，就覆盖，向下调整

void CreateNDate()
{// 造数据int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand()+i) % 10000000;//自己可以改10个大于10000000，相当于10标记，验证结果fprintf(fin, "%d\n", x);}fclose(fin);
}void TestHeap3()
{int k;printf("请输入k>:");scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail");return;}const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}// 读取文件中前k个数for (int i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);}// 建K个数的小堆for (int i = (k-1-1)/2; i>=0 ; i--){AdjustDown(kminheap, k, i);}// 读取剩下的N-K个数int x = 0;while (fscanf(fout, "%d", &x) > 0){if (x > kminheap[0]){kminheap[0] = x;AdjustDown(kminheap, k, 0);}}printf("最大前%d个数：", k);for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}printf("\n");fclose(fout);
}

注意：

交换后，向下调整，是一次，O(log(N))

直接堆数组向下调整建堆，是多次，O(N)

降序，找出前K个最大，建小堆


http://www.mrgr.cn/news/25832.html

相关文章：

  • 贪心算法之最小生成树详细解读（附带Java代码解读）
  • 基于51单片机的灯盘检测（PCF8591+CD4051 ）
  • 银行零售客群策略与标签体系搭建指南
  • 论文解读《LaMP: When Large Language Models Meet Personalization》
  • Autosar学习----AUTOSAR_SWS_BSWGeneral（三）
  • AI大模型与产品经理：替代与合作的深度剖析
  • 基于深度学习的文本引导的图像编辑
  • 聚观早报 | 问界M9大五座上市；荣耀Magic 7将亮相
  • 提取msi安装包中的文件
  • OpenAI 刚刚推出 o1 大模型！！突破LLM极限
  • ip地址a段b段c段是什么意思
  • （不用互三）【AI创作工具】Midjourney与Stable Diffusion选择攻略
  • 智慧升级新篇章：Vatee万腾平台引领企业迈向未来
  • [C#学习笔记]Newtonsoft.Json
  • 2024开学季必备好物有哪些？有哪些好物推荐？学生党必备好物清单！
  • 计算机组成原理(二) —— Cache 高速缓存
  • 砥砺前行 智护健康：衢州骨伤科医院建院十五周年庆典圆满启动
  • WPF中的控件转换（Transform）
  • 【深度学习】注意力机制介绍，了解什么是注意力计算规则以及常见的计算规则，知道注意力机制的工作流程
  • Kotlin 极简小抄 P2（插值表达式、运算符、选择结构赋值）