java 实现最小二叉堆排序的实例
写在前面：
一觉醒来，我就突然有灵感了……
最小二叉堆定义：
二叉堆是完全二元树或者是近似完全二元树,最小二叉堆是父结点的键值总是小于或等于任何一个子节点的键值的堆堆。
存储：
二叉堆一般用数组来表示。
根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2；
位置k的叶子的父节点位置为（k-1）/2；
实现：
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
/**
* @description 元素添加到末尾，和它的父节点比，如果比它小就交换
* @param array
*
* @author LynnWong
*/
private int[] getMinBinaryHeap(int[] array){
int N = array.length;
int minBinaryHeap[] = new int[N];
int root;//根的值
int heapSize = 0;//记录插入位置
for(int num : array){
minBinaryHeap[heapSize]=num;
++heapSize;
int pointer = heapSize-1;//当前指向的数组元素位置
while(pointer!=0){
int leafPointer = pointer;//叶子节点位置
pointer = (pointer-1)/2;//根节点位置
root = minBinaryHeap[pointer];//根节点
if(num>=minBinaryHeap[pointer]){//永远把当前数组元素看成叶子与其根比较或者换位
break;
}//如果根比叶子大 就交换位置
minBinaryHeap[pointer] = num;
minBinaryHeap[leafPointer] = root;
}
}
return minBinaryHeap;
}
|
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
/***
* 用随机数测试二叉堆排序
* 测试10遍，强迫症似的变态...
*/
public void text(){
for(int i=0;i<10;i++){
Random rnd = new Random();
int [] lala = {rnd.nextInt(6),rnd.nextInt(6),rnd.nextInt(6),rnd.nextInt(6),rnd.nextInt(6),rnd.nextInt(6)};
System.out.print("输入：");
for(int a : lala){
System.out.print(a+" ");
}
System.out.println();
int []array = this.getMinBinaryHeap(lala);
System.out.print("输出：");
for(int a : array){
System.out.print(a+" ");
}
System.out.println();
}
}
|
如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://lynnlysh.iteye.com/blog/1767372
相关文章
猜你喜欢
- 64M VPS建站：怎样优化以提高网站加载速度？ 2025-06-10
- 64M VPS建站：是否适合初学者操作和管理？ 2025-06-10
- ASP.NET自助建站系统中的用户注册和登录功能定制方法 2025-06-10
- ASP.NET自助建站系统的域名绑定与解析教程 2025-06-10
- 个人服务器网站搭建：如何选择合适的服务器提供商？ 2025-06-10
