???? 堆排序（HeapSort）是一种应用于海量数据处理的一种常用算法，它的时间复杂度为O(nlogn),其平均时间复杂度接近与其最坏的复杂度，所以堆排序对处理大数量的数据很有优势。
????
堆排序定义
n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），当然，这是小根堆，大根堆则换成>=号。//k(i）相当于hashu.html" target="_blank">二叉树的非叶结点，K(2i）则是左孩子，k(2i+1）是右孩子。??
???? ?换句话说：? 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。
?
?
下面请看我的一个实现堆排序的具体例子：
????? 问题：从一个具有3000万个int类型的数据堆中找出十个最大数据输出。（如果你的内存够大的话还可以处理更大的数据量）
?????这明显是一个处理海量数据的例子，我们可以这样来实现：假如这3000万个int类型数据存于一个数组中?
private static int[] heap =new int[30000000];
static{
Random ran = new Random();
for(int i=0;i<heap.length;i++){
heap[i]=ran.nextInt(1000000000);
}
}
???声明该数组并且用随机数赋初始值。
其具体的实现思想是这样的：
?? （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()十次就行了。
?
?
下面是具体的代码*:
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<heap.length;i++){
heap[i]=ran.nextInt(1000000000);
}
}
/** 主类 */
public static void main(String[] args) {
HeapSort h = new HeapSort();
long start = System.currentTimeMillis();
h.heapSort(heap, 10);
long end = System.currentTimeMillis()-start;
System.out.println("一共用时："+end+"毫秒");
}
/**
* 用堆排序方法 找出前十个最小数
*/
public void heapSort(int[] arr,int top){
array = new int [top];
initHeap();//
int temp;
for(int i=0;i<array.length;i++){
array[i]= heap[0];
temp=heap[heap.length-i-1];
heap[heap.length-i-1]=heap[0];
heap[0]=temp;
buildHeap(0,heap.length-i-1,heap);
}
//打印出排序后的数组
for(int i=0;i<array.length;i++){
System.out.println(array[i]);
}
}
/**
* 创建初始无序堆
*/
public void initHeap(){
for(int i=heap.length-1;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)<unSortLength){
if(arr[tempLoc]>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))<unSortLength){//如果该父节点有左节点
if(arr[tempLoc]>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实现一下：
?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;i<array.length;i++){
array[i]=ran.nextInt(1000000000);
}
}
/**
* @param args
*/
public static void main(String [] args){
SortTop10 sort = new SortTop10();
long start = System.currentTimeMillis();
sort.searchTop_Priority();
long end = System.currentTimeMillis()-start;
System.out.println("一共用时："+end+"毫秒");
}
/**
* 用优先队列排序
*/
public void searchTop_Priority(){
//将数组元素添加到优先队列
MypriorityQueue queue = new MypriorityQueue(10);
for(int i=0;i<array.length;i++){
queue.add(array[i]);
}
//取出并打印优先队列中的元素
int size = queue.size();
for(int i=0;i<size;i++){
int k = queue.poll();
System.out.println("优先队列中的值："+k);
}
}
}
/**
* 自定义优先队列 用于上面的测试
* @author Administrator
*
*/
public class MypriorityQueue {
int [] queue ;
/**
* 构造函数
*/
public MypriorityQueue(int length){
queue = new int[length];
}
/**
* add方法 添加元素 并自动按照从大到小的顺序排列
*/
public void add(int value){
for(int i=0;i<queue.length;i++){
if(queue[0]==0){
queue[0]=value;
}else if(value>queue[i]){
insert(i,value);
break;
}
}
}
/**
* 定义插入元素的方法
*/
public void insert(int index,int value){
for(int i=index;i<queue.length-1;i++){
queue[index+1]=queue[index];
}
queue[index]=value;//将该元素复制给当前的索引位置
}
/**
* 取出元素 并移除数组头
* @return
*/
public int poll(){
int value = queue[0];
int [] newQueue = new int[queue.length-1];
for(int i=0;i<newQueue.length;i++){
newQueue[i]=queue[i+1];
}
queue=newQueue;
return value;
}
//返回优先队列的size
public int size(){
return queue.length;
}
}
通过测试可以得到其中一组结果：
优先队列中的值：999999955
优先队列中的值：999999939
优先队列中的值：999999907
优先队列中的值：999999896
优先队列中的值：999999850
优先队列中的值：999999807
优先队列中的值：999999793
优先队列中的值：999999747
优先队列中的值：999999675
优先队列中的值：999999594
一共用时：1961毫秒
?
由此可见在处理海量数据的时候堆排序效率明显要高！
?
?
?
?
?
相关文章
