堆+堆排序+topK问题

目录

堆：

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.xdnf.cn/news/141979.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

yjs06——numpy的介绍与优势（1）

yjs06——numpy的介绍与优势（1）

1.numpy是什么&#xff1f; numpy是python的一个科学计算库&#xff0c;用于快速处理 任意维度的数据&#xff1b; numpy的存储单元/基本数据类型是 ndarray&#xff08;多维数组&#xff09; 2.多维数组的建立&#xff1a; import numpy as np np.array([ [1,2,3], [4,5,6…
阅读更多...
ZYNQ7010_7020_硬件LVDS设计

ZYNQ7010_7020_硬件LVDS设计

ZYNQ7010_7020_硬件LVDS设计 ZYNQ7010_7020_硬件LVDS设计 1.版本说明2.概述3.目标4.硬件设计5.IO SERDES 1.版本说明 日期作者版本说明20240916风释雪初始版本 2.概述 当我们使用ZYNQ7010/15/20的时候&#xff0c;本身BANK只支持HR&#xff0c;不支持HP, 如图&#xff1a; …
阅读更多...
Flink有界流实现(1)

Flink有界流实现(1)

flink实现有界流需要使用StreamExecutionEnvironment类&#xff0c;并且最后需要使用env.execute() 方法&#xff0c;有界和无界的算子有时候会有不同的 复杂的写法 package org.example.test; import org.apache.flink.api.java.functions.KeySelector; import org.apache.fl…
阅读更多...
Redis的缓存穿透、缓存雪崩、缓存击穿怎么解决

Redis的缓存穿透、缓存雪崩、缓存击穿怎么解决

Redis在实际使用中是会遇到很多问题的&#xff0c;例如今天说到的缓存穿透、缓存雪崩、缓存击穿。 缓存穿透&#xff1a; 缓存穿透是指客户端请求的数据在redis缓存和数据中都不存在&#xff0c;这样缓存永远都不会生效&#xff0c;这些请求都会打到数据库当中&#xff0c;对…
阅读更多...
【CTF MISC】XCTF GFSJ1088 [中等] QR1 Writeup（图像处理+QR Code识别）

【CTF MISC】XCTF GFSJ1088 [中等] QR1 Writeup（图像处理+QR Code识别）

[中等] QR1 一张空白的图片&#xff1f; 解法 一张空白图片。 用 Photoshop 打开&#xff0c;放大&#xff0c;发现很多小黑点。 将图片复制到新文档&#xff0c;用魔棒工具选择白色部分。 Ctrl Shift i 反选。编辑&#xff0c;描边&#xff0c;黑色&#xff0c;10px&#…
阅读更多...
java面向对象：构造方法

java面向对象：构造方法

给出javabean类代码 package google.test5;public class Student {private String name;private int age;public Student(){System.out.println("看看我打印了嘛&#xff1f;");}public Student(String name, int age){this.name name;this.age age;}public void …
阅读更多...
2024 年高教社杯全国大学生数学建模竞赛 B 题 生产过程中的决策问题 第二问chatGPT4的回答，matlab和python代码

2024 年高教社杯全国大学生数学建模竞赛 B 题 生产过程中的决策问题 第二问chatGPT4的回答，matlab和python代码

持续更新中，2024年所有 数学建模比赛思路代码都会发布到专栏内，只需要订阅一次。 5号6号半价，会结合历年优秀论文、人工智能深度学习算法、chatgpt。会定期发布思路、代码和论文。思路和论文基本拿不到国奖，想要获得国奖的同学不要购买。适合基础差的学生，只适合冲击省奖。…
阅读更多...
PMP--一模--解题--61-70

PMP--一模--解题--61-70

文章目录 14.敏捷61、 [单选] 作为估算活动持续时间过程的一部分&#xff0c;项目经理促成了与产品负责人和Scrum团队的冲刺计划会议。项目经理将用户故事分解为较小的任务项&#xff0c;以小时为单位估算所需时间&#xff0c;并根据团队的能力确定冲刺待办事项列表。尽管计划周…
阅读更多...
您使用过哪些AI集成工具提升工作效率

您使用过哪些AI集成工具提升工作效率

您使用过哪些AI集成工具提升工作效率 随着AI技术的飞速发展&#xff0c;个人开始寻求高效的方法来构建和管理定制化模型&#xff0c;以简化复杂的开发过程&#xff0c;提高工作效率。说起用AI集成工具来提高工作效率&#xff0c;个人作为开发者&#xff0c;确实在使用AI代码辅助…
阅读更多...
引用和指针的区别(面试概念性题型)

引用和指针的区别(面试概念性题型)

个人主页&#xff1a;Jason_from_China-CSDN博客 所属栏目&#xff1a;C系统性学习_Jason_from_China的博客-CSDN博客 所属栏目&#xff1a;C知识点的补充_Jason_from_China的博客-CSDN博客 概念概述 内存占用&#xff1a; 引用&#xff1a;引用一个变量时&#xff0c;实际上并…
阅读更多...
.ipynb 图解介绍，轻松入门，提升效率

.ipynb 图解介绍，轻松入门，提升效率

目录 01 使用jupyter遇到的问题1.1 Python requires ipykernel installed or requires an update 1.1.1 查询所有内核 1.1.2 选择对应的Python版本 02 理解jupyter规则 2.1 系统命令 01 使用jupyter遇到的问题 1.1 Python requires ipykernel installed or requires an up…
阅读更多...
IP 协议分析《实验报告》

IP 协议分析《实验报告》

目录 一、 实验目的 二、实验设备和环境 三、实验记录 1、实验环境搭建 2、IP 协议分析 1.设置抓包接口 2.IP 报文分析 3.报文长度计算 4.生存时间 TTL 5.分析总结 3、IP分片 1.IP 分片简介 2.捕获分组 3.结果分析 一、 实验目的 1、掌握 IP 协议数据报格式&…
阅读更多...
CPLEX+Yalmip+MATLAB2022a配置

CPLEX+Yalmip+MATLAB2022a配置

来源&#xff1a;yalmipcplex12.10文件及安装教程-CSDN博客https://blog.csdn.net/qq_41944352/article/details/126421198 安装包 来源&#xff1a;yalmipcplex12.10文件及安装教程-CSDN博客 Cplex 需下载&#xff1a; Microsoft Visual C 2015 Redistributable 添加路径&a…
阅读更多...
跨界融合，GIS如何赋能游戏商业——以《黑神话：悟空》为例

跨界融合，GIS如何赋能游戏商业——以《黑神话：悟空》为例

在数字化时代&#xff0c;地理信息系统&#xff08;GIS&#xff09;技术正以其独特的空间分析和可视化能力&#xff0c;为游戏产业带来革命性的变革。《黑神话&#xff1a;悟空》作为中国首款3A级别的动作角色扮演游戏&#xff0c;不仅在游戏设计和技术上取得了突破&#xff0c…
阅读更多...
【Hot100】LeetCode—4. 寻找两个正序数组的中位数

【Hot100】LeetCode—4. 寻找两个正序数组的中位数

目录 1- 思路题目识别二分 2- 实现⭐4. 寻找两个正序数组的中位数——题解思路 3- ACM 实现 原题链接&#xff1a;4. 寻找两个正序数组的中位数 1- 思路 题目识别 识别1 &#xff1a;给定两个数组 nums1 和 nums2 &#xff0c;找出数组的中位数 二分 思路 将寻找中位数 —…
阅读更多...
Java和西门子S7-1200通讯调试记录

Java和西门子S7-1200通讯调试记录

这是很久以前做的一个项目&#xff0c;工业现场一个agv&#xff0c;主要作用的清扫摇床&#xff08;一种选矿设备&#xff09;&#xff0c;选用的S7-1200的CPU。工作原理是agv上面放一个机械臂&#xff0c;机械臂上面装一个扫把&#xff0c;到固定位置以后&#xff0c;执行清扫…
阅读更多...
结合人工智能，大数据，物联网等主流技术实现业务流程的闭环整合的名厨亮灶开源了

结合人工智能，大数据，物联网等主流技术实现业务流程的闭环整合的名厨亮灶开源了

明厨亮灶视频监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒&#xff0c;省去繁琐重复的适配流程&#xff0c;实现芯片、算法、应用的全流程组合&#xff0c;从而大大减少企业级应用约95%的开发成本。AI技术可以24小时…
阅读更多...
Beyond Compare 标准版与专业版 区别

Beyond Compare 标准版与专业版 区别

Beyond Compare 的标准版是一个功能齐全的比较工具&#xff0c;而不是一个精简的“精简版”。标准版具有全屏编辑、完全 Unicode 支持、语法高亮等等。 但是&#xff0c;Pro 版增加了以下高级功能&#xff1a; 3 路合并 将独立更改与共同上级进行比较&#xff0c;以便为文件夹…
阅读更多...
C++第五十一弹---IO流实战：高效文件读写与格式化输出

C++第五十一弹---IO流实战：高效文件读写与格式化输出

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】 目录 1. C语言的输入与输出 2. 流是什么 3. CIO流 3.1 C标准IO流 3.2 C文件IO流 3.2.1 以写方式打开文件 3.2.1 以读方式打开文件 4 stringstre…
阅读更多...
算法入门-贪心1

算法入门-贪心1

第八部分&#xff1a;贪心 409.最长回文串&#xff08;简单&#xff09; 给定一个包含大写字母和小写字母的字符串 s &#xff0c;返回通过这些字母构造成的最长的回文串 的长度。 在构造过程中&#xff0c;请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串…
阅读更多...
最新文章

Copyright @ 2022~2023