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

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

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

写在前面：

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

最小二叉堆定义：

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

存储：

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

根节点在数组中的位置是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();

}

}

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。