最小二叉树堆排序怎么利用java实现
这篇文章给大家介绍最小二叉树堆排序怎么利用java 实现,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
创新互联公司专注为客户提供全方位的互联网综合服务,包含不限于成都网站设计、做网站、嵊泗网络推广、微信小程序、嵊泗网络营销、嵊泗企业策划、嵊泗品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;创新互联公司为所有大学生创业者提供嵊泗建站搭建服务,24小时服务热线:18982081108,官方网址:www.cdcxhl.com
最小二叉堆定义:
二叉堆是完全二元树或者是近似完全二元树,最小二叉堆是父结点的键值总是小于或等于任何一个子节点的键值的堆堆。
存储:
二叉堆一般用数组来表示。
根节点在数组中的位置是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 实现就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
分享文章:最小二叉树堆排序怎么利用java实现
本文网址:http://myzitong.com/article/peogih.html