jialisoftw
java 实现最小二叉堆排序
写在前面:
一觉醒来,我就突然有灵感了......
最小二叉堆定义:
二叉堆是完全二元树或者是近似完全二元树,最小二叉堆是父结点的键值总是小于或等于任何一个子节点的键值的堆堆。
存储:
二叉堆一般用数组来表示。
根节点在数组中的位置是0,第n个位置的子节点分别在2n+1和 2n+2;
位置k的叶子的父节点位置为(k-1)/2;
实现:
Java
代码:
/**
* @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;
}
Java代码 :
/***
* 用随机数测试二叉堆排序
* 测试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();
}
}
posted on 2013-01-10 14:01
飞猪一号
阅读(1486)
评论(0)
编辑
收藏
新用户注册
刷新评论列表
只有注册用户
登录
后才能发表评论。
网站导航:
博客园
IT新闻
知识库
C++博客
博问
管理
导航
BlogJava
首页
新随笔
联系
聚合
管理
<
2013年1月
>
日
一
二
三
四
五
六
30
31
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
31
1
2
3
4
5
6
7
8
9
统计
随笔 - 43
文章 - 0
评论 - 33
引用 - 0
常用链接
我的随笔
我的评论
我的参与
最新评论
留言簿
给我留言
查看公开留言
查看私人留言
随笔档案
2013年5月 (4)
2013年4月 (1)
2013年3月 (1)
2013年2月 (3)
2013年1月 (12)
2012年11月 (8)
2012年10月 (14)
友情链接
jxlazzw
东莞网站建设
天涯博客
段正淳
站长software8.co
站长网
(rss)
转印机
搜索
最新评论
1. re: spring mvc3中的addFlashAttribute方法[未登录]
6666666666
--66
2. re: spring mvc3中的addFlashAttribute方法[未登录]
看看了
--kk
3. re: spring mvc3中的addFlashAttribute方法
发放范围广
--凤飞飞
4. re: Java中SimpleDateFormat格式化日期用法
健康和健康
--假货
5. re: 基于JavaBean,JSP实现登录并显示分页信息的小系统
十分感谢啊!太有用了!
--kad
阅读排行榜
1. spring mvc3中的addFlashAttribute方法(9442)
2. Java中SimpleDateFormat格式化日期用法(5010)
3. JSON与JAVA的数据转换(2823)
4. java将html实体字符转换成正常字符(2703)
5. 为什么总是缺人(2695)
评论排行榜
1. 为什么总是缺人(4)
2. JSON与JAVA的数据转换(4)
3. spring mvc3中的addFlashAttribute方法(3)
4. Java多线程对耗时方法的同步问题(3)
5. java将html实体字符转换成正常字符(3)