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 << 1;
var rightChildIndex = (index<<1) + 1;
if (leftChildIndex <= heapSize && heap[leftChildIndex] > heap[index])
{
largerItemIndex = leftChildIndex;
}
if (rightChildIndex <= heapSize && heap[rightChildIndex] > heap[largerItemIndex])
{
largerItemIndex = rightChildIndex;
}
if( index != largerItemIndex)
{
Swap(heap, index, largerItemIndex);
MaxHeapfy(heap, largerItemIndex);
}
}
static void Swap(int[] heap, int index1, int index2)
{
var temp = heap[index1];
heap[index1] = heap[index2];
heap[index2] = temp;
}
}
}
1.MaxHeapfy:该方法的前提是index处节点的左右子树已经是最大堆，最终的目的是使以index处节点为根的堆成为最大堆
2.BuildMaxHeap：该方法涉及一个事实：如果一个对含n个元素，那么从
开始的元素（假设节点下表从1开始）就一定是叶子节点（这一点可以用反证法证明，假设
处节点不是叶子节点，那么该节点必包含子节点，从而可以得出其左孩子的索引2 *(
) > n的结论，显然这是错误的）。在这个前提下，该方法至底向上通过MaxHeapfy将堆构建成最大堆。
相关推荐
-
内部排序之堆排序的实现详解
堆排序(Heap Sort)只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间.(1)基本概念a)堆:设有n个元素的序列:{k1, k2, ..., kn}对所有的i=1,2,...,(int)(n/2),当满足下面关系: ki≤k2i,ki≤k2i+1 或
-
Java排序算法总结之堆排序
本文实例讲述了Java排序算法总结之堆排序.分享给大家供大家参考.具体分析如下: 1991年计算机先驱奖获得者.斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序算法( Heap Sort ).本文主要介绍堆排序用Java来实现. 堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素.堆排序是不稳定的排序方法,辅助空间为O(1), 最坏
-
老生常谈比较排序之堆排序
对于堆排序会涉及一些完全二叉树知识.对于待排序列{10, 2, 11, 8, 7},把它看成是一颗完全二叉树,如下图所示. 堆分为大根堆和小根堆:大根堆表示每个根节点均大于其子节点(L(i) >= L(2i) && L(i) >= L(2i + 1)),小根堆表示每个根节点均小于其子节点(L(i) <= L(2i) && L(i) <= L(2i + 1)).(在完全二叉树中第i个节点的左子节点为2i,其右字节点为2i + 1) 本文将以大根堆的构建
-
详解堆排序算法原理及Java版的代码实现
概述 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,
-
PHP排序算法之堆排序(Heap Sort)实例详解
本文实例讲述了PHP排序算法之堆排序(Heap Sort).分享给大家供大家参考,具体如下: 算法引进: 在这里我直接引用<大话数据结构>里面的开头: 在前面讲到 简单选择排序 ,它在待排序的 n 个记录中选择一个最小的记录需要比较 n - 1 次,本来这也可以理解,查找第一个数据需要比较这么多次是正常的,否则如何知道他是最小的记录. 可惜的是,这样的操作并没有把每一趟的比较结果保存下来,在后一趟的比较重,有许多比较在前一趟已经做过了,但由于前一趟排序时未保存这些比较结果,所以后一趟排序时又重
-
图解Java排序算法之堆排序
目录 预备知识 堆排序 堆 堆排序基本思想及步骤 再简单总结下堆排序的基本思路: 总结 预备知识 堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序.首先简单了解下堆结构. 堆 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆:或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆.如下图: 同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面
-
Java 十大排序算法之堆排序刨析
二叉堆是完全二叉树或者是近似完全二叉树. 二叉堆满足二个特性︰ 1．父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值. 2．每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆). 任意节点的值都大于其子节点的值--大顶堆(最后输出从小到大排) 任意节点的值都小于其子节点的值---小顶堆(最后输出从大到小排) 堆排序步骤 1.堆化,反向调整使得每个子树都是大顶或者小顶堆(建堆) 2.按序输出元素∶把堆顶和最末元素对调,然后调整堆顶元素(排序) 堆排序代码实现(大顶堆) publ
-
JAVA十大排序算法之堆排序详解
目录 堆排序 知识补充 二叉树 满二叉树 完全二叉树 二叉堆 代码实现 时间复杂度 算法稳定性 思考 总结 堆排序 这里的堆并不是JVM中堆栈的堆,而是一种特殊的二叉树,通常也叫作二叉堆.它具有以下特点: 它是完全二叉树 堆中某个结点的值总是不大于或不小于其父结点的值 知识补充 二叉树 树中节点的子节点不超过2的有序树 满二叉树 二叉树中除了叶子节点,每个节点的子节点都为2,则此二叉树为满二叉树. 完全二叉树 如果对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左而右.则深度为k的,有
-
C# 排序算法之堆排序
一.基本概念 堆:这里是指一种数据结构,而不是我们在C#中提到的用于存储引用类型对象的地方.它可以被当成一棵完全二叉树. 为了将堆用数组来存放,这里对每个节点标上顺序.事实上,我们可以用简单的计算公式得出父节点,左孩子,右孩子的索引: parent(i) = left(i) = 2i right(i)=2i + 1 最大堆和最小堆: 最大堆是指所有父节点的值都大于其孩子节点的堆,即满足以下公式: A[parent[i]]A[i](A是指存放该堆的数组) 最小堆相反. 最大堆和最小堆是堆排序的关
-
PHP排序算法之归并排序(Merging Sort)实例详解
本文实例讲述了PHP排序算法之归并排序(Merging Sort).分享给大家供大家参考,具体如下: 基本思想: 归并排序:就是利用归并(合并)的思想实现的排序方法.它的原理是假设初始序列含有 n 个元素,则可以看成是 n 个有序的子序列,每个子序列的长度为 1,然后两两归并,得到 ⌈ n / 2⌉ (⌈ x ⌉ 表示不小于 x 的最小整数)个长度为 2 或 1 的有序序列:再两两归并,······,如此重复,直至得到一个长度为 n 的有序序列为止,这种排序方法就成为 2 路归并排序. 一.归并
-
PHP排序算法之基数排序(Radix Sort)实例详解
本文实例讲述了PHP排序算法之基数排序(Radix Sort).分享给大家供大家参考,具体如下: 基数排序在<大话数据结构>中并未讲到,但是为了凑齐八大排序算法,我自己通过网络学习了这个排序算法,并给大家分享出来. 基本思想: 基数排序(radix sort)属于"分配式排序"(distribution sort),又称"桶子法"(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶&quo
-
PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】
本文实例讲述了PHP四种排序算法实现及效率分析.分享给大家供大家参考,具体如下: PHP的四种基本排序算法为:冒泡排序.插入排序.选择排序和快速排序. 下面是我整理出来的算法代码: 1. 冒泡排序: 思路:对数组进行多轮冒泡,每一轮对数组中的元素两两比较,调整位置,冒出一个最大的数来. //简单版: function bubbleSort($arr) { $n = count($arr); for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮) for($j=0;$j<
-
浅谈Java常见的排序算法
目录 一.直接插入排序 二. 希尔排序 三.冒泡排序 四.快速排序 五.选择排序(Selection Sort) 六.堆排序 七.归并排序 一.直接插入排序 基本思想: 将一个记录插入到已排序的有序表中,使插入后的表仍然有序 对初始关键字{49 38 65 97 76 13 27 49}进行直接插入排序 package Sort; //插入排序 public class InsertSort { public static void main(String[] args) { int [] ar
-
java排序算法图文详解
目录 一.直接插入排序 二. 希尔排序 三.冒泡排序 四.快速排序 五.选择排序(Selection Sort) 六.堆排序 一.堆排序的基本思想是: 二.代码示例 七.归并排序 总结 一.直接插入排序 基本思想: 将一个记录插入到已排序的有序表中,使插入后的表仍然有序 对初始关键字{49 38 65 97 76 13 27 49}进行直接插入排序 package Sort; //插入排序 public class InsertSort { public static void main(Str