`

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

    堆排序 heapsort c语言实现

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

    C语言实现堆排序heapSort算法

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

    堆排序算法(java)

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

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

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

    java实现堆排序算法

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

    各种排序的C++算法实现(插入排序、合并排序、堆排序、快速排序)

    全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...

    python常用排序算法汇总

    # sort.heapSort() #堆排序 # sort.countSort() #计数排序 # sort.quickSort() #快速排序 该排序算法把每次的排序结果都列出来,可供初学者学习。 self.arr存放的是待排序列表,可改成自己的数据

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

    我刚用C#写的堆排序算法(HEAPSORT),算法简洁,质量不错,只是注释不多

    多种排序算法C代码实现

    包含以下九种排序算法的C代码实现源码:可以自已生成随机数以便...合并排序算法的改进算法(MergeSort2)、堆排序算法(HeapSort)。注:每一个皆可使用gcc编译通过,未发现无warning,有些可能需要链接math库,加-lm即可

    各类排序算法的C实现

    /交换函数/直接插入排序/冒泡排序/直接选择排序/shell 排序/QSort 快速排序/Restore 重建堆/HeapSort 堆排序等排序算法的实现。

    几种常见排序算法实现

    1. 5 HeapSort:用最大堆实现。 实现时:建堆:置换堆顶元素和最后一个元素,堆大小减少,保持新的堆为最大堆; 保持最大堆: 从底向上依次保持最大堆,从第一个父节点到根部。 1.6 MergeSort:拆分数组,递归实现...

    ED2-HeapSort:堆排序算法的实现

    ED2-堆排序 堆排序算法的实现

    heapsort.cpp

    堆排序(Heapsort)是指利用堆这种数据结构(后面的...大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列; 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

    算法导论中堆排序c++源程序

    算法导论上的堆排序c++源程序||学习分享

    各种排序算法总结

    常用排序算法总结,包括插入排序(InsertionSort),冒泡排序(BubbleSort),选择排序(SelectionSort),快速排序(QuickSort), * 二路归并排序(MergeSort),堆排序...有每一种排序算法的复杂度分析以及实现思路~

    Python实现的堆排序算法原理与用法实例分析

    本文实例讲述了Python实现的堆排序算法。分享给大家供大家参考,具体如下: 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆性质:即子结点的键值或...

    变形堆排序 c++源代码

    4) 编程实现算法tHeapSort(同时实现堆排序(HeapSort)),对于给定个数(>15个)的元素,随机生成元素的排列(随机生成>50次),统计排序过程中元素比较次数,并与HeapSort的结果进行比较,并说明算法性的优劣;

    Swift实现堆排序算法的代码示例

    堆排序(HeapSort)是一树形选择排序,堆排序的时间复杂度O(nlogn),这里我们来看一下Swift实现基堆排序算法的代码示例,首先对堆排序算法的基本概念作一个了解:

    挑战七大排序算法-04堆排序

    堆排序 1.原理 2.实现 3.性能分析 堆排序 1.原理 基本原理也是选择排序,只是不再使用遍历的方式查找无序区间的最大数,而是通过堆来选择无序区间的最大数 升序:大顶堆;降序:小顶堆 堆排序的基本思路: a.将无需...

Global site tag (gtag.js) - Google Analytics