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

堆的实现-向上调整算法-向下调整算法-堆排序-TopK问题 C语言

堆的实现与堆排序及TopK问题的C语言代码

下面是详细的堆实现,包括向上调整、向下调整算法,以及堆排序和解决TopK问题的完整C语言示例代码。

1. 堆的实现

首先,定义堆的数据结构:

#include <stdio.h>
#include <stdlib.h>#define MAX_HEAP_SIZE 100typedef struct {int data[MAX_HEAP_SIZE];int size;
} Heap;Heap* createHeap() {Heap* heap = (Heap*)malloc(sizeof(Heap));heap->size = 0;return heap;
}
2. 向上调整算法
void heapifyUp(Heap* heap, int index) {int parentIndex = (index - 1) / 2;if (index > 0 && heap->data[index] > heap->data[parentIndex]) {// 交换当前节点和父节点int temp = heap->data[index];heap->data[index] = heap->data[parentIndex];heap->data[parentIndex] = temp;// 递归向上调整heapifyUp(heap, parentIndex);}
}
3. 向下调整算法
void heapifyDown(Heap* heap, int index) {int largest = index;int leftChild = 2 * index + 1;int rightChild = 2 * index + 2;if (leftChild < heap->size && heap->data[leftChild] > heap->data[largest]) {largest = leftChild;}if (rightChild < heap->size && heap->data[rightChild] > heap->data[largest]) {largest = rightChild;}if (largest != index) {// 交换当前节点和最大子节点int temp = heap->data[index];heap->data[index] = heap->data[largest];heap->data[largest] = temp;// 递归向下调整heapifyDown(heap, largest);}
}
4. 插入元素到堆
void insertHeap(Heap* heap, int value) {if (heap->size >= MAX_HEAP_SIZE) {printf("Heap is full!\n");return;}heap->data[heap->size] = value;heap->size++;heapifyUp(heap, heap->size - 1);
}
5. 删除堆顶元素
int extractMax(Heap* heap) {if (heap->size <= 0) {printf("Heap is empty!\n");return -1;}int maxValue = heap->data[0];heap->data[0] = heap->data[heap->size - 1];heap->size--;heapifyDown(heap, 0);return maxValue;
}
6. 堆排序
void heapSort(int* array, int length) {Heap* heap = createHeap();for (int i = 0; i < length; i++) {insertHeap(heap, array[i]);}for (int i = length - 1; i >= 0; i--) {array[i] = extractMax(heap);}free(heap);
}
7. TopK问题

解决TopK问题,即找出数据流中前K大的元素,可以使用一个最小堆来实现。

void topK(int* array, int length, int k) {if (k <= 0 || k > length) {printf("Invalid value of K!\n");return;}Heap* heap = createHeap();for (int i = 0; i < k; i++) {insertHeap(heap, array[i]);}for (int i = k; i < length; i++) {if (array[i] > heap->data[0]) {heap->data[0] = array[i];heapifyDown(heap, 0);}}printf("Top %d elements: ", k);for (int i = 0; i < k; i++) {printf("%d ", extractMax(heap));}printf("\n");free(heap);
}
8. 测试代码
int main() {int array[] = {3, 2, 1, 5, 6, 4};int length = sizeof(array) / sizeof(array[0]);// 测试堆排序heapSort(array, length);printf("Sorted array: ");for (int i = 0; i < length; i++) {printf("%d ", array[i]);}printf("\n");// 测试TopK问题int k = 3;int array2[] = {3, 2, 1, 5, 6, 4};length = sizeof(array2) / sizeof(array2[0]);topK(array2, length, k);return 0;
}

解释

  1. 堆的实现:使用数组和一个结构体来表示堆,包含堆的数据和大小。
  2. 向上调整算法:在插入新元素后,通过比较当前节点和父节点的值来调整堆,确保堆的性质。
  3. 向下调整算法:在删除堆顶元素后,通过比较当前节点和子节点的值来调整堆,确保堆的性质。
  4. 堆排序:利用堆的插入和删除操作,将数组中的元素排序。
  5. TopK问题:使用最小堆找出数据流中前K大的元素。

通过这些步骤和代码实现,可以高效地进行堆操作、堆排序以及解决TopK问题。

相关文章:

堆的实现-向上调整算法-向下调整算法-堆排序-TopK问题 C语言

堆的实现与堆排序及TopK问题的C语言代码 下面是详细的堆实现&#xff0c;包括向上调整、向下调整算法&#xff0c;以及堆排序和解决TopK问题的完整C语言示例代码。 1. 堆的实现 首先&#xff0c;定义堆的数据结构&#xff1a; #include <stdio.h> #include <stdli…...

【C++BFS】1466. 重新规划路线

本文涉及知识点 CBFS算法 LeetCode1466. 重新规划路线 n 座城市&#xff0c;从 0 到 n-1 编号&#xff0c;其间共有 n-1 条路线。因此&#xff0c;要想在两座不同城市之间旅行只有唯一一条路线可供选择&#xff08;路线网形成一颗树&#xff09;。去年&#xff0c;交通运输部…...

服务器并发模型

服务器&#xff1a; 单循环服务器&#xff1a;服务器在同一时刻只能响应一个客户端的请求 并发服务器模型&#xff1a;服务器在同一时刻可以响应多个客户端的请求 UDP:无连接 TCP:有连接 1.多进程 资源空间消耗大 效率低 2.多线程 相…...

Chapter 23 数据可视化——地图

欢迎大家订阅【Python从入门到精通】专栏&#xff0c;一起探索Python的无限可能&#xff01; 文章目录 前言一、基础绘图二、视觉映射三、案例分析 前言 随着地理信息系统&#xff08;GIS&#xff09;技术的迅猛发展和大数据时代的到来&#xff0c;数据可视化已经成为分析和理…...

Linux笔记 --- 组合数据类型

结构体 简单的定义结构体的方法 struct student {char name;int age;float score; };//使用student模板创建两个结构体变量 struct student Jack,Rose; 结构体中可以存放除了函数以外的任何数据类型的数据&#xff0c;在创建结构体时student被称为结构体模板名称&#xff0c;…...

DaoCloud-Dockfile文件NGINX文件

Dockfile文件 安装依赖&#xff0c;打包&#xff0c;配置NGINX代理&#xff0c;最后把打完的包复制到服务器相应的文件夹下&#xff0c;构建镜像成功。 # syntax docker/dockerfile:experimental FROM xx.xx.xx.xx/public/node:16.14.2 as builder# LABEL maintainer"e…...

耳机行业中MIC ENC

0 Preface/Foreword ENC&#xff1a; Environment Noise Cancellation&#xff0c;环境降噪&#xff0c;主要指在通话过程中&#xff0c;戴着ENC通话降噪耳机的使用者&#xff0c;即使在嘈杂的环境&#xff0c;比如在嘈杂的街区&#xff0c;开着窗运行的汽车上&#xff0c;说话…...

python-自动化办公-Excel-Openpyxl

Python处理Excel数据之Openpyxl 1.1 Openpyxl库的安装使用 openpyxl模块是一个读写Excel 2010文档的 Python 库&#xff0c;如果要处理更早格式的Excel文档&#xff0c;需要用到额外的库&#xff0c;openpyxl是一个比较综合的工具&#xff0c;能够同时读取和修改Excel文档。其…...

图形编辑器基于Paper.js教程10:导入导出svg,导入导出json数据

深入了解Paper.js&#xff1a;实现SVG和JSON的导入导出功能 Paper.js是一款强大的矢量绘图JavaScript库&#xff0c;非常适合用于复杂的图形处理和交互式网页应用。本文将详细介绍如何在Paper.js项目中实现SVG和JSON格式的导入导出功能&#xff0c;这对于开发动态图形编辑器等…...

[STM32][Bootloader][教程]STM32 HAL库 Bootloader开发和测试教程

0. 项目移植 对于不想知道其执行过程的朋友来说&#xff0c;可以直接移植&#xff0c;我的板子是STM32F411CER6, 512K M4内核 项目地址&#xff1a; Bootloader&#xff08;可以自己写标志位用于自测&#xff0c;项目中这部分代码已经被注释&#xff0c;可以打开自行测试&…...

如何手写一个SpringBoot框架

你好&#xff0c;我是柳岸花开。 在这篇文章中&#xff0c;我们将手写模拟SpringBoot的核心流程&#xff0c;让大家能够以一种简单的方式了解SpringBoot的大概工作原理。 项目结构 我们创建一个工程&#xff0c;包含两个模块&#xff1a; springboot模块&#xff0c;表示Spring…...

vite解决前端跨域步骤

Vite 解决跨域问题的原理主要是通过其内置的开发服务器功能实现的&#xff0c;具体来说&#xff0c;是通过 HTTP 代理&#xff08;HTTP Proxy&#xff09;机制。在开发环境中&#xff0c;Vite 服务器可以配置为一个代理服务器&#xff0c;将前端应用发出的请求转发到实际的后端…...

同步交互与异步交互:深入解析与选择

同步交互与异步交互&#xff1a;深入解析与选择 1、同步交互2、异步交互3、选择策略 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 在软件开发的世界里&#xff0c;交互方式主要分为两大类&#xff1a;同步与异步。下面是对这两种方式的解…...

Day1

首先&#xff0c;大概学习了一下用anaconda去创建一个环境&#xff08;因为Django是有python版本的要求&#xff09;&#xff0c;然后学着去切换环境。 创建环境&#xff1a;conda create -n django_study python3.10 激活环境&#xff1a;conda activate django_study 删除环…...

Introduction to Data Analysis with PySpark

1.DataFrame and RDDs 2.Spark Architecture 3. Data Formats and Data Sources 倘若您觉得我写的好&#xff0c;那么请您动动你的小手粉一下我&#xff0c;你的小小鼓励会带来更大的动力。Thanks....

基于双PI控制器结构的六步逆变器供电无刷直流电机调速simulink仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 4.1 无刷直流电机&#xff08;BLDCM&#xff09;原理 4.2 六步换相逆变器 4.3 双PI控制器设计 5.完整工程文件 1.课题概述 基于双PI控制器结构的六步逆变器供电无刷直流电机调速simulink仿真。双PI控制…...

双向链表的基本操作

#include<iostream> #include<cmath> #include<cstring> using namespace std; typedef long long ll; typedef struct line {int data;struct line *pre;//前指针struct line *next;//后指针 }line,*a; line* init_line(line*head) {cout<<"请输…...

modbus tcp和modbusRTU的区别是什么?

Modbus是一种应用广泛的通信协议&#xff0c;主要用于工业自动化和过程控制系统。Modbus有多种变体&#xff0c;其中Modbus TCP和Modbus RTU是最常见的两种。以下是它们之间的主要区别&#xff1a; 1. 基本定义 Modbus RTU (Remote Terminal Unit): 是基于串行通信的协议&am…...

web小游戏开发:拼图(四)对调和移动拼图玩法的实现

web小游戏开发:拼图(四)对调和移动拼图玩法的实现 对调方式对调模式实现移动方式移动的实现小结对调方式 在完成了原始拼图玩法后,剩下两个玩法其实相对就变得简单的多了。 对调模式,简单来说,就是选中两个图块,然后位置对调一下。 那么,我们来整理一下,看看需要哪…...

前端:Vue学习 - 智慧商城项目

前端&#xff1a;Vue学习 - 智慧商城项目 1. vue组件库 > vant-ui2. postcss插件 > vw 适配3. 路由配置4. 登录页面静态布局4.1 封装axios实例访问验证码接口4.2 vant 组件 > 轻提示4.3 短信验证倒计时4.4 登录功能4.5 响应拦截器 > 统一处理错误4.6 登录权证信息存…...

陶瓷淬火时“啪“一声裂开的瞬间,背后藏着相场模型里的连续损伤演化。今天咱们用Matlab玩个热应力场+相场断裂的耦合计算,看看脆性材料怎么被温度场玩坏

matlab相场热力耦合断裂问题&#xff0c;陶瓷淬火算例&#xff0c;paraview可视化先上主菜——相场控制方程。核心是温度场T与相场d的相爱相杀&#xff1a; % 热传导方程残差计算 function R_T calc_heat_residual(T, d, dt)kappa 1e-5; % 热扩散系数grad_T gradient(T);R_T…...

FindSomething:革新性网页智能信息提取工具完全指南

FindSomething&#xff1a;革新性网页智能信息提取工具完全指南 【免费下载链接】FindSomething 基于chrome、firefox插件的被动式信息泄漏检测工具 项目地址: https://gitcode.com/gh_mirrors/fi/FindSomething 在数字时代&#xff0c;网页中隐藏的敏感信息和数据模式往…...

FLUX.1-dev像素生成器效果对比:不同Scale值对像素结构强度影响实测

FLUX.1-dev像素生成器效果对比&#xff1a;不同Scale值对像素结构强度影响实测 1. 像素艺术生成技术概述 像素幻梦&#xff08;Pixel Dream Workshop&#xff09;是基于FLUX.1-dev扩散模型构建的专业像素艺术生成工具。它采用16-bit现代明亮风格设计&#xff0c;为创作者提供…...

如何快速上手MoMask:面向初学者的3D人体运动生成完整指南

如何快速上手MoMask&#xff1a;面向初学者的3D人体运动生成完整指南 【免费下载链接】momask-codes Official implementation of "MoMask: Generative Masked Modeling of 3D Human Motions (CVPR2024)" 项目地址: https://gitcode.com/gh_mirrors/mo/momask-code…...

用了Qoder写代码飞快,联调时却总因字段不一致返工,问题出在哪?

发版前夜&#xff0c;前端字段对不上后端接口&#xff0c;联调卡了整晚。这种场景在 AI Coding 普及后并不罕见&#xff0c;不少团队用了 Qoder 觉得生成快、跑通快&#xff0c;可一旦要改需求&#xff0c;系统就僵住了。看似工具背锅&#xff0c;其实根子往往不在速度&#xf…...

Repomix用户体验:CLI界面设计与交互的终极指南

Repomix用户体验&#xff1a;CLI界面设计与交互的终极指南 【免费下载链接】repomix &#x1f4e6; Repomix (formerly Repopack) is a powerful tool that packs your entire repository into a single, AI-friendly file. Perfect for when you need to feed your codebase t…...

CLIP-GmP-ViT-L-14图文匹配工具实战:新闻配图与标题语义一致性自动检测

CLIP-GmP-ViT-L-14图文匹配工具实战&#xff1a;新闻配图与标题语义一致性自动检测 你有没有遇到过这种情况&#xff1f;看到一篇新闻&#xff0c;标题写得挺吸引人&#xff0c;但配图却让人摸不着头脑——标题说“科技创新”&#xff0c;配图却是风景照&#xff1b;标题讲“经…...

OpenClaw环境隔离方案:GLM-4.7-Flash多项目独立配置

OpenClaw环境隔离方案&#xff1a;GLM-4.7-Flash多项目独立配置 1. 为什么需要环境隔离&#xff1f; 去年夏天&#xff0c;我同时接手了两个截然不同的自动化项目&#xff1a;一个是帮朋友处理电商数据整理的私人需求&#xff0c;另一个是公司内部的知识库维护工作。当我兴冲…...

从0到1手把手教你搭建AI Agent,打造多智能体协同系统

本文完整展示如何从 0 到 1 手搓一个 AI Agent 的搭建过程。在具体动手实操的过程中&#xff0c;重点为大家展示从需求分析到如何搭建。需求分析中包含如何识别 AI 提效场景和、梳理提效场景流程。如何搭建中包含工作流创建、智能体创建、智能体发布。接下来&#xff0c;将结合…...

建议收藏|降AIGC工具深度测评与2026年最好用推荐

2026年真正好用的AI论文降重与改写工具&#xff0c;核心看降重效果、去AI味、格式保留、学术适配四大指标。综合实测&#xff0c;千笔AI、ThouPen、豆包、DeepSeek、Grammarly 是当前最值得推荐的梯队&#xff0c;覆盖从免费到付费、从中文到英文、从文科到理工的全场景需求。 …...