1 / 5
文档名称:

C# 排序算法之堆排序.doc

格式:doc   大小:32KB   页数:5页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

C# 排序算法之堆排序.doc

上传人:taoapp 2022/4/17 文件大小:32 KB

下载得到文件列表

C# 排序算法之堆排序.doc

相关文档

文档介绍

文档介绍:C# 排序算法之堆排序
这里是指一种数据结构,而不是我们在C#中提到的用于存储引用类型对象的地方。它可以被当成一棵完全二叉树。
一、基本概念
堆:这里是指一种数据结构,而不是我们在C#中提到的用于存储引用类型对象的地方C# 排序算法之堆排序
这里是指一种数据结构,而不是我们在C#中提到的用于存储引用类型对象的地方。它可以被当成一棵完全二叉树。
一、基本概念
堆:这里是指一种数据结构,而不是我们在C#中提到的用于存储引用类型对象的地方。它可以被当成一棵完全二叉树。
为了将堆用数组来存放,这里对每个节点标上顺序。事实上,我们可以用简单的计算公式得出父节点,左孩子,右孩子的索引:
parent(i) =
left(i) = 2i
right(i)=2i + 1
最大堆和最小堆: 最大堆是指所有父节点的值都大于其孩子节点的堆,即满足以下公式:
A[parent[i]]A[i](A是指存放该堆的数组)
最小堆相反。
最大堆和最小堆是堆排序的关键,可知最大堆的根节点是堆中最大的节点。因此只要我们构造出最大(小)堆,最大(小)的元素也就得到了,然后再对剩下的元素继续构造最大(小)堆,就可以取出第二大(小)的元素,依此类推,直到排序完成。
二、构造最大(小)堆
我们已经得知构造最大(小)堆是堆排序的关键,下面就来看看如何构造最大堆。
万事开头难,首先来看一种特殊的情形吧:堆的根节点的左子树和右子树都已经是最大堆了,然而根节点却比孩子节点小,当然,这个堆不满足最大堆的定义。为了⑩这个堆成为最大堆,我们可以按如下步骤操作:
(1)将根节点与左右孩子中最大的交换
(2)交换之后可能会面临左或右子树不是最大堆的问题,但由于整个左(右)子树一开始就是最大堆,问题又回到了最开始的状态,因此只要如此反复即可得到最大堆。
对于上面的特殊堆已经找到了解决办法,但对于一般意义上的堆呢?
我们可以选择自底向上来构造:叶子节点是特殊的最大堆,举个例子有叶子节点a,b,它们的父节点是p;a,b肯定已经是最大堆了,这是要保证a,b,p组成的子树是最大堆。这个堆很眼熟是不是?没错,它就是前面提到的特殊的堆。在a,b,p组成的子树变成最大堆后,我们又可以类似的使该子树,该子树的父节点,以及同胞子树(或节点)组成的新子树成为最大堆,如此类推,最终使堆变为最大堆。
对于求解最小堆与此类似。
三、实现
完整代码:
复制代码代码如下:
namespace HeapSort
{
using System;
class Program
{
static int heapSize =0;
static void Main(string[] args)
{
var heap = new[] { -1, 10, 5, 12, 77, 54, 7, 34, 23, 11 };//为了方便,索引0处不存放元素(或存放无用元素)
heapSize = - 1;
BuildMaxHeap(heap);
for (var i = - 1; i >= 2; i--)
{
//,将第一个元素和最后一个元素交换;
//

最近更新

能源企业通信网光传输设备不同品牌联网的利弊.. 3页

聚晶金刚石复合片(PDC)放电修磨的实验研究 3页

耐热导线运行温度对带电作业安全距离的影响研.. 3页

绿色理念融入方案设计的必要性分析 3页

综合式消力池坎高与池深组合消能计算方法 3页

经济管理与企业发展的和谐性研究 3页

线上+线下深度学习——关于小学数学混合式教学.. 3页

纤维增强多层水泥板结构性能研究的试验方法 3页

精益生产方式在电机风电机座铆焊中的应用 3页

管道线路岩溶勘察工作重点及方法 3页

筑牢产业基础,助力乡村振兴的实践探索 3页

章先生“独身家庭”投资理财规划方案设计 10页

程序化交易系统的检测与优化体系 3页

移动互联网用户行为感知与分析技术 3页

科技数据资源的开放共享机制研究 3页

福建省部分高校健美操选项课教学情况调查分析.. 3页

碱渣综合治理技术在炼油厂的应用 4页

研究称摄入大量多脂鱼类对孕妇有益 3页

矿井水位监测与控制系统的设计研究 3页

药品“两票制”培训 18页

英语六级常用的易错易混词 42页

腹部手术病人的护理 18页

肾移植术后感染并发症 123页

2025年龙年简短的祝福文案精选200句 30页

2025年龙年属鼠犯太岁吗 4页

2025年龙年信息技术四个字公司适合好名800个 9页

2025年鸡年韦姓男孩起名方法 4页

2025年鲁滨逊漂流记观后感800字 9页

2025年高质量晚安文案句子说说 17页

2025年高考语文写作结构技巧 5页