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

数据结构篇--优先级队列排序--实验报告

news 来源：原创 2025/7/5 21:48:46

实验简介
框架代码
实验步骤
运行结果
实验总结

实验概述

优先队列排序算法的基本思想是：

将所有待排序元素依次插入到优先队列中，然后按照从大到小的顺序，通过重复删除优先队列中的最大元素，取出所有元素，从而实现排序。

void PQsort(Item a[], int l, int r){PQinit(r-l+1);int k;for (k = l; k<=r; k++) {PQinsert(a[k]);}for (k = r; k >=l; k--) {a[k] = PQdelmax();}
}

本实验旨在通过实际运行和时间测量，比较两种基于优先队列的排序算法的性能：一种使用二叉堆作为优先队列的基础，另一种使用二项队列作为优先队列的基础。

实验将针对随机生成的整数键值进行排序，测试的数据规模 $N$ 分别为 $10^3$ 、 $10^4$ 、 $10^5$ 、 $10^6$ ，以经验性地评估它们在不同数据量下的时间效率。理论上，这两种基于优先队列的排序算法的时间复杂度都为 $O(N\log N)$ 。

本实验将重点关注在实际运行中，不同数据结构所带来的常数因子差异。

框架代码

Makefile

CC = gcc
CFLAGS = -O0
TestSortWithHeapPQ: Exercise966.c HeapPQ.c$(CC) $(CFLAGS) -o $@ $^TestSortWithBinomialQueue: Exercise966.c BinomialQueue.c$(CC) $(CFLAGS) -o $@ $^clean:rm -f avg TestSortWithHeapPQ TestSortWithBinomialQueue

Exercise966.c
Item.h

typedef int Item;#define key(A) (A)
#define less(A,B) (key(A) < key(B))
#define exch(A, B) { Item t = A; A = B; B = t; }

PQ.h
HeapPQ.c
BinomialQueue.c

实验步骤

# 编译TestSortWithHeapPQ
make TestSortWithHeapPQ
# 编译TestSortWithBinomialQueue
make TestSortWithBinomialQueue
# 运行
./TestSortWithHeapPQ
# 运行
./TestSortWithBinomialQueue

运行结果

--- Running Heap-based Sort (Results below) ---
N		Time (ms)
---------------------------
1000		0.00
10000		1.00
100000		13.00
1000000		150.00--- Running Binomial Queue-based Sort (Results below) ---
N		Time (ms)
---------------------------
1000		0.00
10000		2.00
100000		25.00
1000000		300.00=======================================================
Combined Performance Comparison: Binomial Queues vs Heaps
=======================================================Heap-based Sort Results:
N		Time (ms)
---------------------------
1000		0.00
10000		1.00
100000		13.00
1000000		150.00Binomial Queue-based Sort Results:
N		Time (ms)
---------------------------
1000		0.00
10000		2.00
100000		25.00
1000000		300.00Summary (N | Heap Time (ms) | Binomial Time (ms))
---------------------------------------------------
1000			0.00			0.00
10000			1.00			2.00
100000			13.00			25.00
1000000			150.00			300.00
---------------------------------------------------

从实验结果可以看出，在所有测试的数据规模 $N$ 下，基于二叉堆的排序通常比基于二项队列的排序表现出更快的执行时间。

对于较小的数据量（例如 $N=1000, 10^4$ ），两者的时间差异不明显，可能都在毫秒级别，甚至显示为 $0.00$ 毫秒，这表明两种数据结构的基本操作都非常高效。
然而，随着数据规模的增大（尤其是在 $N=10^5$ 和 $N=10^6$ 时），二叉堆的优势变得更加显著。在 $N=10^6$ 时，二叉堆排序的时间大约是二项队列排序时间的一半。

原因分析：

常数因子： 尽管两种算法的渐近时间复杂度都是 $O(N\log N)$ ，但它们内部操作的常数因子不同。
- 二叉堆（Binary Heap）通常采用数组实现，这提供了更好的缓存局部性。堆的 fixUp 和 fixDown 操作主要涉及数组元素的简单比较和交换，这些操作对 CPU 缓存非常友好。
- 二项队列（Binomial Queue）的实现涉及更复杂的指针操作和动态内存分配（尤其是合并操作 pair 和 BQjoin_internal）。它的结构是链式存储的二项树森林，这可能导致内存访问不连续，从而降低缓存效率。每次插入和删除最大元素都需要执行一系列的二项树合并操作，这些操作虽然渐进复杂度低，但实际的指令开销可能较大。
操作复杂性：
- 二叉堆的插入和删除最大元素操作是相对直接的上浮或下沉，涉及到有限的比较和交换。
- 二项队列的插入和删除最大元素操作则涉及将一个元素（或一个树）与队列中的多个树进行合并（类似二进制加法），删除最大元素后还需要将最大树的子树重新合并回队列。这些逻辑比二叉堆的维护更为复杂。

实验总结

本实验结果支持了理论分析中关于数据结构常数因子的考量。

在实际应用中，如果对性能有较高要求，且数据规模较大，二叉堆作为优先队列的基础通常是更优的选择，因为它在实现上的简洁性和更好的缓存性能使其具有更小的常数因子。

二项队列虽然在某些理论场景下（如合并两个大型优先队列）表现出色，但在简单的 insert 和 delmax 操作的反复执行中，其复杂性可能会导致性能略逊于二叉堆。

数据结构篇--优先级队列排序--实验报告

实验简介框架代码实验步骤运行结果实验总结实验概述优先队列排序算法的基本思想是： 将所有待排序元素依次插入到优先队列中，然后按照从大到小的顺序，通过重复删除优先队列中的最大元素，取出所有元素，从而实现排序…...

编程日记 2025/7/5 21:48:46

【图像大模型】基于深度对抗网络的图像超分辨率重建技术ESRGAN深度解析

基于深度对抗网络的图像超分辨率重建技术ESRGAN深度解析一、技术背景与核心创新1.1 图像超分辨率技术演进1.2 核心技术创新对比二、算法原理深度解析2.1 网络架构设计2.1.1 RRDB模块结构 2.2 损失函数设计2.2.1 对抗损失（Adversarial Loss）2.2.2 感知损…...

编程日记 2025/6/27 23:40:34

Ubuntu 20.04卸载并重装 PostgreSQL

在 Ubuntu 下彻底卸载并重新安装 PostgreSQL（包括所有版本及其数据目录）的步骤下面是一个在 Ubuntu 下彻底卸载并重新安装 PostgreSQL（包括所有版本及其数据目录）的步骤。文章目录在 Ubuntu 下彻底卸载并重新安装 PostgreSQL&…...

编程日记 2025/6/27 22:57:39

1. Ruby 环境 Redis-dump 是一个 Ruby 工具，需先安装 Ruby 和 RubyGems。安装命令： sudo apt update sudo apt install ruby-full build-essential[roota29d39f5fd10:/opt/redis-dump/bin# apt install ruby-full build-essential Reading pac…...

编程日记 2025/6/27 22:57:41

AI智能分析网关V4玩手机检测算法精准管控人员手机行为，搭建智慧化安防监管体系

一、背景移动终端普及使随意用机成为常态，在生产车间、加油站、考场、手术室等场景，人员使用手机易引发生产事故、爆炸、作弊、仪器干扰等问题。传统人工巡查存在覆盖不足、响应慢、主观性强等局限，难以满足现代安全管理需求。AI智能分析…...

编程日记 2025/6/27 23:18:53

支持向量存储：PostgresSQL及pgvector扩展详细安装步骤！老工程接入RAG功能必备！

之前文章和大家分享过，将会出一篇专栏（从电脑装ubuntu系统，到安装ubuntu的常用基础软件：jdk、python、node、nginx、maven、supervisor、minio、docker、git、mysql、redis、postgresql、mq、ollama等），目前…...

编程日记 2025/7/5 21:45:39

小土堆pytorch--神经网络-非线性激活线性层及其他层介绍

1. 神经网络-非线性激活 1.1 relu与sigmoid 1.1.1 ReLU（Rectified Linear Unit，修正线性单元 ） 定义与数学表达：数学定义为 f ( x ) max ⁡ ( 0 , x ) f(x) \max(0, x) f(x)max(0,x) ，即当输入 x > 0 x > …...

编程日记 2025/6/27 23:08:48

【Vue3】数据的返回和响应式处理（ref reactive）

目录一、拉开序幕的setup 二、ref函数 2.1 访问对象的响应式处理小结：ref函数三、reactive函数 3.1 reactive同样也可以修改数组： 3.2 reactive小结： 四、Vue3中的响应式原理 4.1 vue2的响应式，对象属性的添加 4.2…...

编程日记 2025/7/2 9:38:41

【Rust智能指针】Rust智能指针原理剖析与应用指导

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，…...

编程日记 2025/6/27 23:34:22

C++ - 仿 RabbitMQ 实现消息队列（3）（详解使用muduo库）

C - 仿 RabbitMQ 实现消息队列（3）（详解使用muduo库） muduo库的基层原理核心概念总结：通俗例子：餐厅模型优势体现典型场景 muduo库中的主要类EventloopMuduo 的 EventLoop 核心解析1. 核心机制：事…...

编程日记 2025/7/5 21:45:38

Java异常处理全解析：从基础到自定义

目录 🚀前言🤔异常的定义与分类💯运行时异常💯编译时异常💯异常的基本处理 🌟异常的作用🐧自定义异常💯自定义运行时异常💯自定义编译时异常 ✍️异常的处理方案&#x1…...

编程日记 2025/6/27 22:57:44

C++初阶-vector的模拟实现2

目录 1.vector已经实现的代码总结 2.vector::resize的模拟实现 3.vector::vector(const vector& v)拷贝构造函数的模拟实现 4.vector::operator(const vector& x)的模拟实现（原始写法） 5.vector::swap的模拟实现 6.vector::operator(const …...

编程日记 2025/6/27 23:18:19

【图数据库】--Neo4j 安装

目录 1.Neo4j --概述 2.JDK安装 3.Neo4j--下载 3.1.下载资源包 3.2.创建环境变量 3.3.运行 Neo4j 是目前最流行的图形数据库(Graph Database)，它以节点(Node)、关系(Relationship)和属性(Property)的形式存储数据，专门为处理高度连接的数据而设计。…...

编程日记 2025/6/27 23:25:27

elementui初学1

当然可以！下面是从零开始创建一个最简单的 Element UI 程序的完整流程，基于 Vue 2 Element UI（如果你想用 Vue 3，请告诉我，我可以给你 Element Plus 的版本）。 ✅ 一、准备环境确保你已经安装了&#xf…...

编程日记 2025/6/27 23:32:08

lanqiaoOJ 4185：费马小定理求逆元

【题目来源】 https://www.lanqiao.cn/problems/4185/learning/ 【题目描述】给出 n，p，求。其中， 指存在某个整数 0≤a<p，使得 na mod p1，此时称 a 为 n 的逆元，即。数据保证 p 是质数且 n mod p≠0…...

编程日记 2025/6/27 23:09:23

计算机视觉与深度学习｜ Python实现CEEMDAN-ISOS-VMD-GRU-ARIMA时间序列预测（完整源码和数据)

以下是结合CEEMDAN、ISOS-VMD、GRU和ARIMA的时间序列预测的Python完整实现方案。本方案包含完整的代码、数据生成逻辑和实现细节说明。完整代码实现 import numpy as np import pandas as pd from PyEMD import CEEMDAN from vmdpy import VMD from scipy.optimize import di…...

编程日记 2025/7/3 19:51:51

前端开发遇到 Bug，怎么办？如何利用 AI 高效解决问题

前端开发遇到 Bug，怎么办？如何利用 AI 高效解决问题作为前端开发者，遇到 Bug 几乎是日常。无论是样式错乱、功能异常，还是接口数据不对，Bug 总能让人头疼。但随着人工智能（AI）技术的发展&…...

编程日记 2025/7/5 14:25:11

博主总结框架

1.博主总结框架 1.1 计算机基础类（数据结构、计算机网络、操作系统等） （1）数据结构 （2）操作系统 （3）计算机网络 （4）其他物联网入门框架 1.2 计算机图形…...

编程日记 2025/6/27 23:00:15

国产化Excel处理组件Spire.XLS for .NET系列教程：通过 C# 将 TXT 文本转换为 Excel 表格

在数据处理和管理场景中，将原始文本文件（TXT）高效转换为结构化的 Excel 电子表格是一项常见要求。对于那些需要自动生成报表或者处理日志文件的开发人员而言，借助 C# 实现 TXT 到 Excel 的转换工作，可以简化数据组织和…...

编程日记 2025/6/27 23:24:02

网络安全--PHP第一天

目标熟悉信息传递架构基于phpstydy-mysql-php 前置条件需要先在数据库中创建相应的库和表名并配置表的结构该文件为数据库配置文件名字为config.php <?php $dbip localhost;//连接数据库的地址远程连接需要输入ip等 $dbuser root;//连接数据库的用户 $dbpass ro…...

编程日记 2025/6/27 23:15:05

结构型：组合模式

目录 1、核心思想 2、实现方式 2.1 模式结构 2.2 实现案例 3、优缺点分析 4、适用场景 1、核心思想目的：将总是在重复、迭代地显示的某种自相似性的结构（部分与整体结构特征相似），例如树形结构，以统一的方式处…...

编程日记 2025/6/27 23:23:07

Node.js多版本安装工具NVM详细使用教程

一、nvm 简介 nvm（Node Version Manager）是一个用于管理多个 Node.js 版本的命令行工具，允许开发者在单个系统中轻松切换、安装和卸载不同版本的 Node.js。它是前端和后端开发中处理 Node.js 版本兼容性问题的核心工具之一。二、nvm 安装 …...

编程日记 2025/6/27 23:01:26

深度解析 Java 中介者模式：重构复杂交互场景的优雅方案

一、中介者模式的核心思想与设计哲学在软件开发的历史长河中，对象间的交互管理一直是架构设计的核心难题。当多个对象形成复杂的网状交互时，系统会陷入 "牵一发而动全身" 的困境。中介者模式（Mediator Pattern）作为行…...

编程日记 2025/6/27 22:57:43

（八）深度学习---计算机视觉基础

分类问题回归问题聚类问题各种复杂问题决策树√线性回归√K-means√神经网络√逻辑回归√岭回归密度聚类深度学习√集成学习√Lasso回归谱聚类条件随机场贝叶斯层次聚类隐马尔可夫模型支持向量机高斯混合聚类LDA主题模型一.图像数字化表示及建模基础二.卷积神经网络CNN基本原…...

编程日记 2025/6/29 8:33:14

深入剖析原型模式：原理、实现与应用实践

在软件开发的世界里，设计模式如同建筑师手中的蓝图，为复杂系统的构建提供了行之有效的解决方案。其中，原型模式（Prototype Pattern）作为创建型设计模式的重要一员，以其独特的对象创建方式，在提高代码复用性、增强系统灵活性等方面发挥着关键作用。本文将深入剖析原型模式…...

编程日记 2025/6/27 23:25:59

【论文阅读 | CVPR 2024 |RSDet:去除再选择：一种用于 RGB - 红外目标检测的由粗到精融合视角】

论文阅读 | CVPR 2024 |RSDet:去除再选择：一种用于 RGB - 红外目标检测的由粗到精融合视角 1.摘要&&引言2. 方法2.1 “由粗到细”融合策略2.2 冗余光谱去除模块（RSR）2.3 动态特征选择模块（DFS）2.4 去除与选择检…...

编程日记 2025/6/27 23:35:00

WinForms 应用中集成 OpenCvSharp 实现基础图像处理

引言欢迎关注dotnet研习社，今天我们要讨论的主题是WinForms 应用中集成 OpenCvSharp 实现基础图像处理。在常规的图像处理软件开发中，图像处理功能是这些应用程序的核心组成部分。无论是简单的照片编辑工具，还是复杂的计算机视觉应用&…...

编程日记 2025/6/27 23:16:49

apache http client连接池实现原理

在java开发中我们经常会涉及到http 请求接口，一般有几种方式： java自带的 HttpURLConnectionokHttpClientapache http client 一般我们使用apache http client会比较多点，在代码中会进行如下调用方式： private static class Htt…...

编程日记 2025/6/27 23:19:43

adb抓包

目录抓包步骤步骤 1: 获取应用的包名步骤 2: 查看单个应用的日志步骤 3: 使用日志级别过滤器步骤 4: 高级日志过滤可能的原因： 解决方案： 额外提示： 日志保存抓包步骤连接设备 adb devices 步骤 1: 获取应用的包名首先…...

编程日记 2025/6/27 22:58:50

C语言---结构体、联合体、枚举

一、初识结构体 1、结构体类型结构体和数组都是集合，但是结构体有成员，类型可以不同；数组有成员，类型相同。 int main() {struct tag{member--list //一个或者多个成员，成员变量}variable--list;//可以省略&#x…...

编程日记 2025/6/27 23:20:08

Web Workers 使用指南

文章目录前言基础使用高级特性使用 ES Modules实际应用场景图像处理大数据处理轮询任务性能优化技巧现代开发方式使用 worker-loader (Webpack) Vite中的Worker使用限制与注意事项DOM限制:通信限制:同源策略:最佳实践前言 Web Workers 是浏览器提供的 JavaScript 多线程解…...

编程日记 2025/6/27 23:19:23

JVM 与容器化部署调优实践（Docker + K8s）

📌 文章目录 📘 前言1️⃣ 容器环境下 JVM 面临的新挑战2️⃣ JVM 的容器资源感知机制详解3️⃣ JVM 内存调优：如何正确使用堆内存4️⃣ JVM CPU 调优：GC 与编译线程控制5️⃣ Kubernetes 典型配置误区与对策6️⃣ 实战案例&#…...

编程日记 2025/6/27 23:37:56

Android OkHttp控制链：深入理解网络请求的流程管理

OkHttp作为Android和Java平台上广泛使用的HTTP客户端，其核心设计之一就是"控制链"(Chain)机制。本文将深入探讨OkHttp控制链的工作原理、实现细节以及如何利用这一机制进行高级定制。一、什么是OkHttp控制链 OkHttp控制链是一种责任链模式的实现&#…...

编程日记 2025/6/27 23:13:40

《易经》的数学表达：初级版和高级版

《易经》的数学表达， 一、初级版，可基于以下框架构建， 涵盖符号系统、结构代数及变换规则： 此框架将《易经》抽象为离散数学结构，兼容符号逻辑、概率论与群论，为算法化占断、卦象拓扑分析及跨文化比较提供…...

编程日记 2025/6/27 23:25:20

卷积神经网络基础（十）

之前我们学习了SGD、Momentum和AdaGrad三种优化方法，今天我们将继续学习Adam方法。 6.1.6 Adam 我们知道Momentum参照的是小球在碗中滚动的物理规则进行移动而实现的，AdaGrad为参数的每个元素适当地调整更新步伐。那如果我们将这两种方法融合在一起会不…...

编程日记 2025/6/27 23:18:02

怎么把cursor（Cursor/ollama）安装到指定路径

使用PowerShell命令打开电脑开始菜单，输入powerShell，使用管理员权限打开powerShell窗口，使用cd命令到cursor或ollama安装包的下载目录，如我的Cursor所在的目录为D:\environment\cursor\soft，输入以下 cd E:\downloa…...

编程日记 2025/6/27 23:18:54

第21天-pyttsx3语音播放功能

示例1：语音参数控制（语速/音量/音调） import pyttsx3def speech_demo():engine = pyttsx3.init()# 获取当前语音参数print("默认语速:", engine.getProperty(rate))print("默认音量:", engine.getProperty(volume))print("可用语音:", engin…...

编程日记 2025/6/27 20:49:02

Multi-Query Attention：传统自注意力（ Self-Attention）优化显存和加速方案

本文导读：Multi-Query Attention（MQA）是 Google Research 2022 年提出的一项轻量化注意力技术，通过“多查询、单键值”的设计，把自注意力层的 KV 缓存从 O(hnd) 降到 O(nd)，在不牺牲模型精度的前提下大幅节…...

编程日记 2025/6/27 23:03:45

学习路之uniapp--unipush2.0推送功能--服务端推送消息

学习路之uniapp--unipush2.0推送功能--服务端推送消息一、二、三、一、二、三、...

编程日记 2025/7/5 0:10:44

如何使用AI搭建WordPress网站

人工智能正迅速成为包括网页设计在内的许多行业在其功能设置中添加的一种工具。在数字设计和营销领域，许多成熟的工具都在其产品中添加了人工智能功能。WordPress 也是如此。作为目前最流行的网站建设工具之一，WordPress 的人工智能插件越来越多也就不足…...

编程日记 2025/6/27 23:07:23

Java 项目管理工具：Maven 与 Gradle 的深度对比与选择

Java 项目管理工具：Maven 与 Gradle 的深度对比与选择在 Java 开发领域，项目管理工具对于项目的构建、依赖管理等起着至关重要的作用。Maven 和 Gradle 是目前最主流的两款工具，它们各自有着独特的优势和适用场景。本文将对 Maven 与 Gradl…...

编程日记 2025/6/27 23:35:50

Elasticsearch简单集成java框架方式。

Elasticsearch 在 Java 中最常用的客户端是什么？如何初始化一个 RestHighLevelClient？如何用 Spring Boot 快速集成 Elasticsearch？Spring Data Elasticsearch 如何定义实体类与索引的映射？ 最常用的 Java 客户端目前官方推荐使用…...

编程日记 2025/6/27 23:00:54

50天50个小项目 (Vue3 + Tailwindcss V4) ✨ | Hidden Search Widget （交互式搜索框）

📅 我们继续 50 个小项目挑战！—— Hidden Search Widget 组件仓库地址：https://github.com/SunACong/50-vue-projects 项目预览地址：https://50-vue-projects.vercel.app/ ✨ 组件目标点击按钮展开隐藏的搜索框再次点击按钮…...

编程日记 2025/6/27 23:30:48

python爬虫和逆向：百度翻译数据采集的几种方式

更多内容请见：爬虫和逆向教程-专栏介绍和目录文章目录一、官方API方式（推荐）1.1 百度翻译开放平台API二、网页版逆向方式（代码可直接运行）2.1 拿到js加密方法2.2 python解密代码三、浏览器自动化方式3.1 Selenium自动化操作3.2 Playwright自动化四、移动端API逆向4.1 分…...

编程日记 2025/6/27 23:13:59

spring5-配外部文件-spEL-工厂bean-FactoryBean

spring配外部文件我们先在Spring里配置一个数据源 1.导c3p0包,这里我们先学一下hibernate持久化框架，以后用mybites. <dependency><groupId>org.hibernate</groupId><artifactId>hibernate-core</artifactId><version>5.2.…...

编程日记 2025/7/5 16:33:10

Ubuntu部署私有Gitlab

这个东西安装其实挺简单的，但是因为我这边迁移了数据目录和使用自己安装的 nginx 代理还是踩了几个坑，所以大家可以注意下先看下安装 # 先安装必要组件 sudo apt update sudo apt install -y curl openssh-server ca-certificates tzdata perl# 添加gi…...

编程日记 2025/6/27 23:07:27

Activiti 7建表语句及注释

Activiti数据库表Oracle兼容DM建表语句及字段注释。附件下载版地址点这里 --通用属性表 create table ACT_GE_PROPERTY (NAME_ NVARCHAR2(64),VALUE_ NVARCHAR2(300),REV_ INTEGER,primary key (NAME_) );COMMENT ON TABLE ACT_GE_PROPERTY IS 通用属性表;COMMENT ON COLUMN …...

编程日记 2025/6/27 23:20:15

React中使用 Ant Design Charts 图表

// 引入 Ant Design Charts 的柱状图组件 Column import { Column } from ant-design/charts;// 定义函数组件 App，用于展示柱状图 function App() {// 数据源：每个对象代表一个柱子，包含类型（type）和销售额&#xff0…...

编程日记 2025/6/27 23:14:04

佰力博科技与您探讨压电材料的原理与压电效应的应用

压电材料的原理基于正压电效应和逆压电效应，即机械能与电能之间的双向转换特性。压电材料的原理源于其独特的晶体结构和电-机械耦合效应，具体可分为以下核心要点： 1. ‌正压电效应与逆压电效应的定义‌ ‌正压电效应‌：当压电…...

编程日记 2025/6/27 23:22:05

vscode打开vue + element项目

好嘞，我帮你详细整理一个用 VS Code 来可视化开发 Vue Element UI 的完整步骤，让你能舒服地写代码、预览界面、调试和管理项目。用 VS Code 可视化开发 Vue Element UI 全流程指南一、准备工作安装 VS Code 官网下载安装：https://code…...

编程日记 2025/6/27 22:57:51

实验概述

框架代码

实验步骤

运行结果

实验总结

相关文章：