已阅读5页，还剩4页未读， 继续免费阅读
版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
数据结构与算法设计堆的概念堆的操作堆的算法分析5.5堆堆的概念n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆或(i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+1可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值大根堆小根堆建堆（大根堆）找到最后一个分支节点（非叶子节点）。对这个节点进行向下调整，即与孩子节点相比较，把比自己大并且是最大的孩子节点与当前节点交换位置，如果发生交换，到达新位置的节点将继续向下调整，直到不发生交换位置或到达叶子节点。从后向前对所有分支节点进行向下调整。直到对根节点完成向下调整。堆的操作例：设节点分别为3、7、5、13、2、17、11，建立大根堆。添加节点把这个节点加到顺序表的末尾从下向上调整至合适位置删除节点把待删除的节点与最后一个节点交换位置删除最后一个节点把与删除节点交换位置的节点向下调整至合适位置堆的操作在堆中，向上调整和向下调整的操作次数不会大于二叉树的层数，所以单个节点的调整，其算法复杂度为log2n。建堆时，需要对所有分支节点做向下调整，在完全二叉树中分支节点的个数为n/2，所以建堆的算法复杂度为O(nlog2n)。增加节点和删除节点时，只需要对单个节点进行向上调整或向下调整，所以其算法复杂度为O(log2n)。堆的算法分析堆的插入和删除操作只需要进行O(log2n)次的交换操作，明显优于顺序表的O(n)次操作。相较于链表，堆在逻辑上存在一定的顺序，并且兼具二叉树的特点，可以在算法的优化上起到明显
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 今天陕西省高考语文作文题
- 生态保护与生态农业推广考核试卷
- 十八项护理核心制度
- 湖北省武汉市2023～2024学年高一数学下学期5月联考试题含答案
- 陕西省咸阳市高新一中2024−2025学年高一下学期第五次质量检测（3月） 数学试卷（含解析）
- 2025年济南历下区八年级第二学期数学期中考试试题（含答案）
- 江苏省无锡市港下中学2025年初三下期中数学试题含解析
- 西安交通大学城市学院《语言学概论》2023-2024学年第一学期期末试卷
- 江西省上饶市民校考试联盟婺源紫阳中学2025年高三第四次联考生物试题含解析
- 上海市格致初级中学2025年高三考前模拟英语试题含解析
- FANUC发那科机器人常规点检保养
- 医药有限公司公司奖惩制度
- 微电子学概论全套课件
- 实验室气瓶使用记录
- DB37T 2974-2017 工贸企业安全生产风险分级管控体系细则
- DB13(J)∕T 8054-2019 市政基础设施工程施工质量验收通用标准
- 混杂纤维增强的复合材料介绍、特点和应用
- 星巴克哈佛商学院案例
- 工程项目内部控制流程图表
- 强夯试夯报告(共12页)
- 骨优导介绍PPT
评论
0/150
提交评论