`

对HeapSort原理的分析和堆排序算法的简单实现

阅读更多
堆排序(HeapSort)是一种应用于海量数据处理的一种常用算法,它的时间复杂度为O(nlogn),其平均时间复杂度接近与其最坏的复杂度,所以堆排序对处理大数量的数据很有优势。-----中国大姨夫()

   

堆排序定义

  n个关键字序列Kl,K2,…,Kn称为(Heap),当且仅当该序列满足如下性质(简称为堆性质):

  (1)ki=号。//k(i)相当于二叉树的非叶结点,K(2i)则是左孩子,k(2i+1)是右孩子。 

      换句话说:  若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:

  树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。



下面请看我的一个实现堆排序的具体例子:

      问题:从一个具有3000万个int类型的数据堆中找出十个最大数据输出。(如果你的内存够大的话还可以处理更大的数据量)

     这明显是一个处理海量数据的例子,我们可以这样来实现:假如这3000万个int类型数据存于一个数组中

[code="java"]private static int[] heap =new int[30000000];
static{
Random ran = new Random();
for(int i=0;i(1)用大根堆排序的基本思想

  ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区

  ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key

  ③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。

  ……

  直到无序区只有一个元素为止。

  (2)大根堆排序算法的基本操作:

  ① 初始化操作:将R[1..n]构造为初始堆;

  ② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。

     这样的的话把每次BuildHeap(建立堆)所得到的无序堆的第一个元素R[1]存到另外一个数组就行了,因为通过BuildHeap()方法使堆顶即数组的第一个元素Heap[0]就是当前无序堆中最大的数。由于我们这里只要找出前十个最大数,所以BuildHeap()十次就行了。



下面是具体的代码*:

[code="java"]package SearchTop;

import java.util.Random;

/**
* 堆排序 实现类
* @author Administrator
*
*/
public class HeapSort {
private static int[] array ;
private static int[] heap =new int[30000000];
static{
Random ran = new Random();
for(int i=0;i=0;i--){
buildHeap(i,heap.length,heap);
}
}
/**
* 调整堆
* @param location 起始位置
* @param unSortLength 无序堆的长度
*/
public void buildHeap(int location,int unSortLength,int[] arr){
int temp;
int tempLoc;
//判断该父节点是否有左右孩子
if((tempLoc = (location+1)*2)arr[tempLoc-1]){//如果右节点大于左节点
if(arr[tempLoc]>arr[location]){//如果右节点大于父节点  就双方交换值
temp = arr[location];
arr[location] = arr[tempLoc];
arr[tempLoc] = temp;
buildHeap(tempLoc,unSortLength,arr);//递归
}
}else{//如果左节点大于右节点
if(arr[tempLoc-1]>arr[location]){//如果左节点大于父节点
temp = arr[location];
arr[location] = arr[tempLoc-1];
arr[tempLoc-1] = temp;
buildHeap(tempLoc-1,unSortLength,arr);//递归
}
}
}else if((tempLoc =((location+1)*2-1))arr[location]){//如果右节点大于父节点
temp = arr[location];
arr[location] = arr[tempLoc];
arr[tempLoc] = temp;
buildHeap(tempLoc,unSortLength,arr);//递归
}
}
}
}



通过测试可以得到其中一组结果:

999999978
999999938
999999928
999999922
999999893
999999859
999999841
999999831
999999810
999999796
一共用时:1166毫秒



下面我再给出用常规的Exhaustive Sort实现一下:

[code="java"]package SearchTop;

import java.util.Random;
/**
*  通过优先队列中的穷举法去查找前十个最大数
* @author Administrator
*
*/
public class SortTop10 {
private static int[] array = new int[30000000];
static{
Random ran = new Random();
for(int i=0;iqueue[i]){
insert(i,value);
break;
}
}
}
/**
* 定义插入元素的方法
*/
public void insert(int index,int value){

for(int i=index;i
2
0
分享到:
评论

相关推荐

    c语言实现堆排序算法 heapsort

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 堆排序的平均时间复杂度为Ο...

    c语言实现堆排序算法

    通过以上分析,我们可以看到,堆排序算法通过巧妙地利用最大堆或最小堆的特性,实现了高效的排序过程。在C语言的实现中,通过对堆的调整和维护,能够有效地完成对数组的排序,从而达到优化数据结构和提升程序效率的...

    堆排序算法实现

    总的来说,这个C语言实现的堆排序算法不仅涉及到了排序算法的基本原理,还涵盖了C语言的基础知识,对于理解和掌握这两种技术都有很大帮助。通过阅读和分析源代码,我们可以深入理解堆排序的工作机制,同时提高C语言...

    堆排序算法实例

    总结来说,"堆排序算法实例"涵盖了计算机科学中一个重要的排序算法——堆排序,它是通过构建和调整堆来实现排序的。结合《算法导论》的理论,我们可以用VC6.0这样的开发环境编写和测试代码,理解堆排序的实现细节,...

    堆排序 heapsort c语言实现

    c语言实现堆排序算法 heapsort 排序算法 。采用随机产生100个数 利用堆排序 。排序1000次 计算排序用的时间。

    C语言实现堆排序heapSort算法

    我们首先实现了swap函数用于交换两个元素的值,然后实现了heapify函数用于调整堆,最后实现了heapSort函数用于进行堆排序。在main函数中,我们定义了一个数组并对其进行...运行该代码,您将看到堆排序算法的执行结果。

    堆排序算法实现堆排序

    堆排序是一种基于比较的排序算法,它通过构造一个近似完全二叉树的堆结构来实现数据的排序。在此,我们将深入探讨堆排序的基本概念、原理以及如何通过编程实现。 一、堆排序的概念 堆是一个近似完全二叉树的结构,...

    排序算法-基于C语言实现的排序算法之HeapSort实现.zip

    在分析和实现排序算法的过程中,理解每种算法的优缺点至关重要。例如,HeapSort虽然具有良好的时间复杂度,但其性能受输入数据的影响较大,对于已经部分有序的数组,它的效率可能会降低。因此,在实际应用中,选择...

    排序算法之堆排序算法:用C++语言实现堆排序算法

    标题"排序算法之堆排序算法:用C++语言实现堆排序算法",意味着我们将讨论如何用C++编程语言来实现堆排序的过程。C++是面向对象的编程语言,具有丰富的库支持和高效的执行性能,是实现算法的理想选择。 描述"排序...

    堆排序算法(流程图、关键代码、复杂度分析)

    堆排序算法(流程图、关键代码、复杂度分析) 堆排序算法是一种基于比较的...我们通过建立流程图、实现关键代码和复杂度分析来详细介绍堆排序算法的实现细节。同时,我们也对实验环境和实验任务解决方案进行了介绍。

    C++堆排序算法的实现

    总结一下,C++中的堆排序算法通过构建和调整最大堆实现排序。`heapify`函数确保每个子树都是最大堆,而`heapSort`函数整体上负责构建最大堆和交换元素以达到排序目的。这个过程无需额外的存储空间,且时间复杂度为O...

    堆排序算法(java)

    java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。

    实现快速排序算法和堆排序算法

    // 堆排序 #include typedef int InfoType; // 定义其它数据项的类型 #include "compare.h" #include "sort.h" typedef SqList HeapType; // 堆采用顺序表存储表示 void HeapAdjust(HeapType &H,int s,int m) // ...

    C语言实现堆排序的算法

    VC++提供了友好的IDE界面和调试工具,有助于开发和测试堆排序算法。 五、性能分析 堆排序的时间复杂度为O(n log n),空间复杂度为O(1),因为它是一种原地排序算法,不需要额外的存储空间。然而,由于频繁的交换...

    java实现堆排序算法

    heapSort 方法实现了堆排序算法。它使用以下步骤进行排序: 构建最大堆:从非叶子节点开始向上调整,使得父节点的值大于等于子节点的值。 排序阶段:依次从堆顶(最大值)开始,将堆顶元素与末尾元素交换,然后...

    C++实现的一个堆排序算法

    ### C++实现的堆排序算法知识点解析 #### 一、堆排序基本概念 堆排序(Heapsort)是一种基于比较的排序技术,它利用了完全二叉树的特性来进行数据的排序。堆排序分为两个阶段:构建初始堆与排序过程。 - **构建...

    C#写的堆排序算法(heap sort)

    堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在C#中实现堆排序,我们可以分为两个主要步骤:建堆和调整堆。这里,我们将深入探讨堆排序的基本原理、C#实现的细节以及其在实际应用中的...

    堆排序与直接插入排序算法的比较

    本文通过对堆排序和直接插入排序算法的实现和比较,分析它们的优缺点,并讨论在不同场景下的应用。结果表明,堆排序的时间复杂度优于直接插入排序,但堆排序是不稳定的。因此,在实际应用中,需要根据具体情况选择...

    C语言编程实现堆排序HeapSort的源代码

    C语言编程实现堆排序HeapSort的源代码。堆排序(Heap Sort)是一种基于堆数据结构的选择排序算法,O(nlogn),不需要额外的存储空间,因此具有 原地排序 和 不稳定排序 的特点。堆排序适用于对大量数据进行排序,尤其...

Global site tag (gtag.js) - Google Analytics