jialisoftw

java 实现最小二叉堆排序

写在前面： 
一觉醒来，我就突然有灵感了...... 
最小二叉堆定义： 
二叉堆是完全二元树或者是近似完全二元树,最小二叉堆是父结点的键值总是小于或等于任何一个子节点的键值的堆堆。 
存储： 
二叉堆一般用数组来表示。 
根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2； 
位置k的叶子的父节点位置为（k-1）/2； 
实现： 
Java代码:  
  1. /** 
  2.  * @description 元素添加到末尾，和它的父节点比，如果比它小就交换 
  3.  * @param array 
  4.  *  
  5.  * @author LynnWong 
  6.  */  
  7. private int[] getMinBinaryHeap(int[] array){  
  8.     int N = array.length;  
  9.     int minBinaryHeap[] = new int[N];  
  10.     int root;//根的值  
  11.     int heapSize = 0;//记录插入位置  
  12.     for(int num : array){  
  13.         minBinaryHeap[heapSize]=num;  
  14.         ++heapSize;  
  15.         int pointer = heapSize-1;//当前指向的数组元素位置  
  16.         while(pointer!=0){  
  17.             int leafPointer = pointer;//叶子节点位置  
  18.             pointer = (pointer-1)/2;//根节点位置  
  19.             root = minBinaryHeap[pointer];//根节点  
  20.             if(num>=minBinaryHeap[pointer]){//永远把当前数组元素看成叶子与其根比较或者换位  
  21.                 break;  
  22.             }//如果根比叶子大 就交换位置  
  23.             minBinaryHeap[pointer] = num;  
  24.             minBinaryHeap[leafPointer] = root;  
  25.               
  26.         }  
  27.     }  
  28.     return minBinaryHeap;  
  29.       
  30. }  
Java代码 : 
  1. /*** 
  2.  * 用随机数测试二叉堆排序 
  3.  * 测试10遍，强迫症似的变态... 
  4.  */  
  5. public void text(){  
  6.     for(int i=0;i<10;i++){  
  7.         Random rnd = new Random();   
  8.         int [] lala = {rnd.nextInt(6),rnd.nextInt(6),rnd.nextInt(6),rnd.nextInt(6),rnd.nextInt(6),rnd.nextInt(6)};  
  9.         System.out.print("输入：");  
  10.         for(int a : lala){  
  11.             System.out.print(a+" ");  
  12.         }  
  13.         System.out.println();  
  14.         int []array = this.getMinBinaryHeap(lala);  
  15.         System.out.print("输出：");  
  16.         for(int a : array){  
  17.             System.out.print(a+" ");  
  18.         }  
  19.         System.out.println();  
  20.     }  
  21. } 

posted on 2013-01-10 14:01 飞猪一号 阅读(1487) 评论(0)  编辑  收藏


只有注册用户登录后才能发表评论。
网站导航:
 

导航

<2013年1月>
日一二三四五六
303112345
6789101112
13141516171819
20212223242526
272829303112
3456789

统计

常用链接

留言簿

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜