对HeapSort原理的分析和堆排序算法的简单实现
???? 堆排序（HeapSort）是一种应用于海量数据处理的一种常用算法，它的时间复杂度为O(nlogn),其平均时间复杂度接近与其最坏的复杂度，所以堆排序对处理大数量的数据很有优势。
????
堆排序定义
n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），当然，这是小根堆，大根堆则换成>=号。//k(i）相当于二叉树的非叶结点，K(2i）则是左孩子，k(2i+1）是右孩子。??
???? ?换句话说：? 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。
?
?
下面请看我的一个实现堆排序的具体例子：
????? 问题：从一个具有3000万个int类型的数据堆中找出十个最大数据输出。（如果你的内存够大的话还可以处理更大的数据量）
?????这明显是一个处理海量数据的例子，我们可以这样来实现：假如这3000万个int类型数据存于一个数组中?
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;}//返回优先队列的sizepublic int size(){return queue.length;}}?
通过测试可以得到其中一组结果：
优先队列中的值：999999955
优先队列中的值：999999939
优先队列中的值：999999907
优先队列中的值：999999896
优先队列中的值：999999850
优先队列中的值：999999807
优先队列中的值：999999793
优先队列中的值：999999747
优先队列中的值：999999675
优先队列中的值：999999594
一共用时：1961毫秒
?
由此可见在处理海量数据的时候堆排序效率明显要高！
?
?
?
?
?