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

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

写在前面：

一觉醒来，我就突然有灵感了......

最小二叉堆定义：

二叉堆是完全二元树或者是近似完全二元树,最小二叉堆是父结点的键值总是小于或等于任何一个子节点的键值的堆堆。

存储：

二叉堆一般用数组来表示。

根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2；

位置k的叶子的父节点位置为（k-1）/2；

实现：

/** 
 * @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; 
   
}

/*** 
 * 用随机数测试二叉堆排序 
 * 测试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(); 
  } 
}

如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# java # 实现最小二叉树与堆排序 # 二叉树及堆排序 # C语言植物大战数据结构二叉树堆 # C++中二叉堆排序详解 # 小二 # 键值 # 我就 # 随机数 # 如有 # 希望能 # 堆堆 # 或者是 # 任何一个 # 谢谢大家 # 组中 # 疑问请 # 强迫症 # 写在前面 # 分别在 # param # brush # description # LynnWong # private

返回目录在线咨询

上一篇：如何通过SEO排名工具进行网站审核_SEO优化教程
下一篇：PHP中如何判断字符串是否只包含一个单词

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

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

您的项目需求