数据结构课设——应用小大根交替堆实现双端优先队列

数据结构课程设计

设计题目: 应用小大根交替堆实现双端优先队列

专业名称 计算机科学与技术
班级学号 计科1801班20188936
学生姓名 张紫闻
指导教师 马海涛
设计时间 2019年12月30日—2020年 1月2日

课程设计任务书

专业:计算机科学与技术 学号:20188936 学生姓名 :张紫闻

设计题目:
一、设计实验条件
自主完成
二、设计任务及要求

  1. 给出双端优先队列的 ADT 描述,包括优先队列的逻辑结构及其上基本操作。
  2. 给出小大根交替堆的 ADT 描述,并实现该 ADT。
  3. 以小大根交替堆结构为辅助结构实现双端优先队列的存储表示并实现其上的基本操作。
  4. 应用双端优先队列的 ADT 实现依据学生成绩实现对学生信息的查询。
  5. 学生信息存放在文本文件中(格式自定,内容自行输入)
  6. 实现良好的可视化操作
  7. 算法执行效率的对比

三、设计报告的内容

  1. 设计题目与设计任务(设计任务书)

应用小大根交替堆实现双端优先队列
任务:双端优先队列是一个支持如下操作的数据结构:
Insert (S, x) – 将元素 x 插入集合 S
Extract –Min (S) –删除 S 中的最小关键字
Extract –Max (S) –删除 S 中的最大关键字
要求:① 给出双端优先队列的 ADT 描述,包括优先队列的逻辑结构及其上基本操作。② 给出小大根交替堆的 ADT 描述,并实现该 ADT。③ 以小大根交替堆结构为辅助结构实现双端优先队列的存储表示并实现其上的基本操作。④ 应用双端优先队列的 ADT 实现依据学生成绩实现对学生信息的查询。⑤ 学生信息存放在文本文件中(格式自定,内容自行输入)。

  1. 前言(绪论)(设计的目的、意义等)

我们都知道堆有一个性质,在一个给定优先次序的情况下。堆顶元素的优先级最高。而且这个性质递归的适用于每一个子堆。所以,我们每次都可以用O(1)的时间得到优先级最高的一个元素。如果要删除,那么我们只需要O(log2(N))的时间去维护整个堆,使其仍然满足堆的性质。
而要同时得到最小值和最大值,我们可以用二叉平衡树来实现(最左孩子和最右孩子就是所求最值)。而这里,我们只需要得到两个最值,而不需要知道中间结果,我们不妨引入一个最小最大堆,来实现这个功能。
所谓最小最大堆,其实是一个最小最大交替堆。前面我们提到,堆的性质:在于在一个堆里面,堆顶元素是优先级最高的元素。这个最小最大交替堆同理,第一层的元素是整个堆里面优先级最小的元素。而以第二层的元素为堆顶的堆,则堆顶是整个子堆里面优先级最大的元素。
以此类推,相互交替。
意义:在一个系统或者在一个生活场景中,我们需要实时的知道当前的最大值最小值,这个时候,如果我们每次都得通过遍历得到最值,那么效率无疑是低下的。那么这个时候,小大根交替堆就能为此应用场景提供适配。

  1. 设计主体(各部分设计内容、分析、结论等)

3.1需求分析

本程序通过大小根交替堆的构建实现了双端优先队列,并应用于学生信息管理系统中,得到良好的交互结果与反馈。程序主要是将Min_Max_Heap可视化,从而更好的直观体会Min_Max_Heap的更新与维护。

上图是Min_Max_Heap的类图,以及student类的类图

上图是主对话框的类图,其中包含的主要功能是:打印每个单元,打印一整个堆。以及消息处理双击鼠标弹出对话框。

输入的形式:键鼠交互。
输入值的范围:
分数:整形(0~100)
其余变量均是都是长度小于10的字符串
输出的形式:
 将最小最大堆展示在主界面。于此同时进行鼠标交互。
程序所能够达到的功能:
 通过添加按钮,可以往系统添加学生信息。
 通过文件读入按钮,将文件中的信息添加到系统。
 通过文件输出按钮,将系统中的信息输出到文件。
 通过 “删除最大(小)值”按钮,将系统最大(小)值删除。
 通过“查看最大(小)值”按钮,查看系统最大(小)值。
 通过鼠标双击相应的地方,可以展示相应同学的信息。
 通过“速度测试”按钮,将最小最大堆的性能与底层基于红黑树c++标准类模板set以及暴力求极值的方法进行比较。
测试数据:
 当输入的文件如《StudengInfo.dat》所示时:

系统一开始:

按下“文件读入”后:

系统会 以每秒插入一个数据的速度,逐个打印当前堆的状态。直到最后如上图所示。

3.2系统设计
本程序所用到的数据主要包括在student类里面,其含有的属性为:
Int:成绩
String: 姓名,学号,生日,出生地,手机,性别
其基本操作为:

下面的是Min_Max_Heap的插入部分以及删除部分的伪代码:

    Min_Max_Heap::Insert(item x){
    ①if(length==0),则直接插入到堆头;
    ②if(now_level==MIN)//如果当前要插入的值在小层堆
            if(heap[tail] 

如何更新堆:

Min_Max_Heap :: PushUP(int index,int status) //index表示当前节点编号, status表示当前节点是在小根层还是大根层

{
    if(index==1||(index/2==1)) return; //如果不是根节点或者第一个大根层
        if(status==MIN)                    //如果当前节点是在小层堆,那么意味着接下来的操作只需要在相对应的小层堆里面更新,无论如何更新,大层堆永远满足条件
            if(heap[index]

删除最大值需要两个函数,一个是popMax();一个是向下更新的pushDown();

void popMax() //弹出最大
        {
            int index = 1;
            for (int i = 1; i  length) return;
            pushDown(index, maxmax); //这里的maxmax是一个函数指针,现在相当于传递了一个大于号过去PushDown
        }
        void pushDown(int root,bool (*cmp)(item a,item b))
        {
            int index=root;
            if(root*2

3.3系统实现
 ①实现小大根堆:总的来说,算法不难,如果掌握并理解了普通的堆的实现,并且代码能力稍强的,基本上没有太大的问题。主要的是理解堆的性质——“所谓堆就是堆顶元素是整个堆的最值”这样看来,小大根堆之所以能解决双端优先队列的问题,正正是因为相交换的这个结构,并且每一层均满足堆的性质。这样维护起来特别的方便,特别的有趣。

 ②实现小大根堆的打印:我是采用的MFC来打印代码,MFC是微软公司提供的一个类库。在这个类库里面提供了很多“可见即可得”的东西。比如ListCtrl菜单控件,PictureCtrl图片控件等等。这次的小大根堆的打印正是基于PictureCtrl控件来打印的。
 一、先获取PictureCtrl的坐标,
 二、记录好长宽,定位好根节点所在的位置。
 三、通过递归打印的方法,打印每一层每一个元素的信息。
 四、为了方便以及代码的复用,我把打印每一个元素的这个方法单独实现,即PrintCell,打印每个子细胞。然后不断连线等等。

③实现细节:
 1、双击可见信息。
 2、添加过程中延迟输入,可视化输入过程
 3、添加过程中,增加Special标识,也就是把更新的点进行Special标记,也就是变红。使可视化更友好。
 4、实现类模板,方便二次调用Min_Max_Heap最小最大堆
 5、最后增加了“速度测试”按钮,通过底层红黑树的set以及暴力两种方法和Min_Max_Heap的速度进行对比。可以更好的分析出各个方法的优劣。

遇到的问题:
 ①小大根堆不会实现:一开始对照着报告册上面的例子反复钻研,用纸把样例画出来后,再模拟推算一遍就差不多会了。
 ②不知道如何进行可视化:我一开始先写完裸的Min_Max_Heap,然后想着可视化得写很多东西,不知道从何下手。然后想到以前实现过一些类似“树的打印”的东西。然后就开始各种百度:如何获取某某控件的大小,如何画矩形,如何改变画笔颜色等等。
 ③不知道如何实现对话框弹出之后,显示一个列表:在显示列表的时候。我犹豫了很久。因为想起一年前的我也卡在这个坎里面卡了很久。然后睡了一觉之后突然想到:所谓变量,都是“依附”于某个类里面的。那么我要传递一个student的变量进去函数,那么我为何不干脆在该类中也设置个同样的student类型的指针,指向我现在的需要的值。然后再调用该类的方法打印到ListCtrl控件。
 ④“速度测试”功能比我想象中慢了10倍:平时写代码的时候会注意一些时间复杂度的问题,比如这次我用来跑暴力的代码,时间复杂度应该是O(n^2),但是在数据量为5000的情况,竟然跑了10s,这非常非常的不可思议。平时应该1秒就ok的。百度无果之后,咨询学长。被告知一个概念:“O2优化”。在这个提醒下,成功将代码正常运行。

时间复杂度分析:
 本次课程设计所实现的Min_Max_Heap最小最大交替堆的时间复杂度为:
 插入某个值:O(Log2(n))
 删除最大或最小值:O(Log2(n))
 得到最大值最小值:O(1)
 建堆:建堆相当于n遍的插入,即:O(nlog2(n));

 空间复杂度:在Min_Max_Heap里面定义了一个用类模板定义的大小为400050的student数组。所以,空间复杂度为O(400050); 不过如果算使用的空间的话,空间复杂度为:O(n); n为堆中元素。

3.4用户手册

3.5测试
程序打开时进入的主界面:

当点击“文件读入”将会以每秒1帧的方式,逐个显示插入的数字,并标红。

当点击文件输出按钮时:将会把系统信息重新储存到数据库中:

此时数据库里面的顺序已经发生了变动

当点击:查看最大值按钮时:会有如下弹窗

当点击:查看最小值按钮时,会有如下弹窗:

不仅如此,在红框所示的区域内,每一个小矩阵进行双击,都可以查看对应学生的信息详情。

当点击:“删除最大值”时最大值会被标红1秒后被删除:

同理删除最小值也是如此:

若填好信息,并且点击“添加学生信息”按钮:

系统会立马得到反馈,并且告知所添加到的位置是红色区域

双击红框还可以得到对应的信息:(不过在中文情况下好像会乱码,暂时不知道怎么解决这个问题。)

点击“速度测试”按钮:静待十秒

  1. 结束语(设计的成果,展望等)
    本次课程设计内容是最小最大堆。并且在最小最大堆的基础上,应用于学生信息管理系统中。实践证明,最小最大堆的算法效率比普通不应用数据结构纯暴力的学生信息管理系统要快许多。在40w数据量下,只需要1.489s就可以处理完全部的数据,可谓效率之高。
    不过注意到:C++类模板基于红黑树的Set的实践将近手写堆的三分之一速度。这让我非常好奇。set和Min_Max_Heap均能实现:快速查询当前最小当前最大值的功能。Set功能更多,它的里面就是一棵平衡二叉树。所以它能从小到大直接迭代遍历整个数组。但是Min_Max_Heap不行,它只有一个性质,就是堆顶元素始终保持最优性质,无论在哪一层。那为什么Min_Max_Heap比Set时间要长呢。这需要对set底层代码进行剖析研究之后再思考。
  1. 参考资料 http://www.jizhuomi.com/software/257.html VS2010/MFC编程入门教程之目录和总结
  2. 附录 带注释的源程序。

#pragma once
#include
#include
#include
#include 

using namespace std;
#include "framework.h"
template
class min_max_heap{
    private:
        const int MIN=1;
        const int MAX=2;

        int tail;

        int getStatus(int x)  //得到当前层的状态
        {
            if((int)(log(x)/log(2))%2==0) return MIN;
                else return MAX;
        }
        void pushUP(int index,int status)//网上更新维护
        {
            if(index==1||(index/2==1)) return; //如果不是根节点或者第一个大根层 
            if(status==MIN)
            {
                if(heap[index] length) return;
            pushDown(index, maxmax);
        }
        item getMax()   //得到最大值
        {
            int ans=1;
            for(int i=1;i

下面是学生类的代码<studentInfo.h>:

您可能还喜欢...

发表评论

电子邮件地址不会被公开。 必填项已用*标注