当前位置:  编程技术>.net/c#/asp.net

C# 排序算法之堆排序

    来源: 互联网  发布时间:2014-10-14

    本文导语:  一、基本概念 堆:这里是指一种数据结构,而不是我们在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 = heap.Length - 1;
BuildMaxHeap(heap);
for (var i = heap.Length - 1; i >= 2; i--)
{
//1.每次在构建好最大堆后,将第一个元素和最后一个元素交换;
//2.第一次以索引1到length-1出的元素组成新的堆,第二次1到length-2,直到剩下最后两个元素组成堆
//3.每次新组成的堆除了根节点其他节点都能保持最大堆的特性,因此只要DoBuildMaxHeap(heap, 1)就可以得到新的最大堆
Swap(heap, 1, i);
heapSize--;
MaxHeapfy(heap, 1);
}
foreach (var i in heap)
Console.Write(i + " ");
}
static void BuildMaxHeap(int[] heap)
{
for (var i = (heap.Length - 1) / 2; i >= 1; i--)
{
MaxHeapfy(heap, i);
}
}
static void MaxHeapfy(int[] heap, int index)
{
var largerItemIndex = index;
var leftChildIndex = index

    
 
 

您可能感兴趣的文章:

  • C#排序算法之快速排序
  • C#实现Datatable排序的方法
  • c# n个数排序实现代码
  • c#冒泡排序算法示例
  • c#冒泡排序示例分享
  • C#中使用快速排序按文件创建时间将文件排序的源码
  • C# List排序的实例介绍
  • c#对list排序示例
  • C# 键值对数据排序代码
  • c# 快速排序算法
  • C#通过IComparable实现ListT.sort()排序
  • c#基数排序Radix sort的实现方法
  • c# 文件快速排序(按文件创建时间)的代码
  • C#对DataTable里数据排序的方法
  • c#集合快速排序类实现代码分享
  • c# 冒泡排序算法(Bubble Sort) 附实例代码
  • C#几种排序算法
  • C#拼接SQL语句 用ROW_NUMBER实现的高效分页排序
  • C#基础之数组排序、对象大小比较实现代码
  • C#中DataTable排序、检索、合并等操作实例
  • <<大话数据结构>>中冒泡排序算法改进
  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述
  • python算法学习之桶排序算法实例(分块排序)
  • 可视化算法排序过程 Sound of Sorting
  • 常用排序算法整理分享(快速排序算法、希尔排序)
  • C++实现顺序排序算法简单示例代码
  • 排序算法之PHP版快速排序、冒泡排序
  • 算法之排序算法的算法思想和使用场景总结
  • VC++实现选择排序算法简单示例
  • php冒泡排序算法实现代码
  • php排序算法 PHP版快速排序与冒泡排序
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • C++ Lists(链表) 成员 sort():给list排序
  • Java中的数组排序方式(快速排序、冒泡排序、选择排序)
  • STL vector+sort排序和multiset/multimap排序比较
  • java数组排序示例(冒泡排序、快速排序、希尔排序、选择排序)
  • java map(HashMap TreeMap)用法:初始化,遍历和排序详解
  • 问题:DefaulTableModel是否有排序的功能,如果没有,jTable如何排序,我是从XML取数据到Table里。
  • linux下top命令详解包括top命令参数使用及结果(virt,res,shr)排序举例说明
  • PHP快速排序小例子 php快速排序实现方法
  • 数据库查询排序使用随机排序结果示例(Oracle/MySQL/MS SQL Server)
  • 深入Java冒泡排序与选择排序的区别详解
  • 用c语言实现冒泡排序,选择排序,快速排序
  • php数组随机排序示例
  • jQuery表格排序插件 tablesorter
  • jQuery排序工具 jQuery.sorted
  • 关于awk数组的排序
  • Eclipse文本排序插件 SortIt
  • linux中对文件排序的命令(文件夹中包含子文件)
  • 请问怎么用sort对多个字段进行排序?
  • ll 命令输出,使用sort排序问题
  • 堆排序算法(选择排序改进)
  • jQuery 表格排序插件 Stupid Table




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3