Java 최소 이진 트리 힙 정렬 구현 방법

이 글은 주로 최소 이진 트리 힙 정렬을 구현하는 Java 예제에 대한 관련 정보를 소개합니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

Java는 최소 이진 트리 힙 정렬의 예제를 구현합니다

Written in Previous:

깨어나자마자 문득 영감이 떠올랐다...

최소 바이너리 힙 정의:

바이너리 힙은 완전한 이진 트리 또는 대략 완전한 이진 트리, 최소 A 바이너리 힙은 상위 노드의 키 값이 항상 하위 노드의 키 값보다 작거나 같은 힙입니다.

저장:

이진 힙은 일반적으로 배열로 표현됩니다.

배열에서 루트 노드의 위치는 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 최소 이진 트리 힙 정렬 구현 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!