版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
1、10.优先级队列(d) 堆排序算法J. Williams, 1964初始化：建堆，heapify()，O(n)迭代：取出堆顶并调整复原，remove()，O(logn)等效同于常规selectionsort()正确性无疑时间= O(n) + n x O(logn)= O(nlogn)若词条已组织为向量完全可以就地排序O(1)附加空间HeapHeapMXMXSortedNpercolate downSortedHeapMXswapSorted实现template /对向量区间lo, hi)做就地堆排序void Vector:heapSort(Rank lo, Rank hi) plHeap H(
2、_elem, lo, hi); /待排序区间建堆，O(n) while (!H.empty() /反复迭代，直至堆空 _elem-hi = H.delMax(); /摘除最大元并归入原区间：等效于堆顶与末元素对换后下滤 /若绕过封装后的操作，可以就地实现HeapMXNpercolate downSorted实例：建堆425134422551133442255113344335511225533441122实例：选取+调整223344115555334411224433221155443322115113322445331122445实例：选取+调整33112245221133452211345112234511234123545综合评价易于理解，便于实现 /完全基于二叉堆结构及其操作接口快速高效 /尤其适用于大规模数据可实现就地运转 /in-space，O(1)附加空间不需全排序即可找出前k个词条 /O(klogn)的selection算法不稳定 /为什么？可否克服？权衡：采用就地策略，是否值得
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 企业入驻战略代理协议
- 代理人员工安全管理
- 交通运输安全健康合同
- 交通运输行业职业介绍合同范本
- 互联网公司股东投资合同样本
- 交通翻译服务合同模板
- 代理人谈判技巧与合同管理
- IT服务支持与维护管理规范
- 产学研合作创协议
- 企业入驻战略诉讼协议
- 人工智能儿童科普
- 产品经济性设计与分析报告
- 基于核心素养初中数学跨学科教学融合策略
- RFJ 006-2021 RFP型人防过滤吸收器制造与验收规范（暂行）
- 2024年高中语文学业水平过关测试四-名句名篇默写积累过关训练（全国通用）学生版
- 内蒙古的特色美食
- 招投标-招投标管理
- 售后工程师热水系统维护培训
- 项目管理机构及人员配备表
- 空乘大学生职业生涯规划
- 使用电器安全教育课件
评论
0/150
提交评论