服务器之家

服务器之家 > 正文

java 实现最小二叉树堆排序的实例

时间:2021-01-08 11:58     来源/作者:lynnlysh

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

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部