Implementation method of Java minimum binary tree heap sorting-javaTutorial-php.cn

Implementation method of Java minimum binary tree heap sorting

黄舟

Release： 2017-09-22 11:14:14

Original

1774 people have browsed it

This article mainly introduces relevant information about the implementation of minimum binary tree heap sorting in java. I hope this article can help everyone. Friends in need can refer to

java implementation of minimum binary heap Examples of sorting

are written in front:

As soon as I woke up, I suddenly had inspiration...

Minimum binary heap definition:

A binary heap is a complete binary tree or an approximately complete binary tree. A minimum binary heap is one where the key value of the parent node is always less than or equal to any child. A heap of node key values.

Storage:

Binary heaps are generally represented by arrays.

The position of the root node in the array is 0, and the child nodes at the nth position are at 2n+1 and 2n+2 respectively;

The leaves at position k The position of the parent node is (k-1)/2;

Implementation:

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

Copy after login

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

Copy after login

The above is the detailed content of Implementation method of Java minimum binary tree heap sorting. For more information, please follow other related articles on the PHP Chinese website!