java最小二叉ツリーの並べ替えを実現する例
java最小二叉スタックの順序付けを実現する例
前に書く:
目が覚めると、急に霊感が湧いてきました。
最小二叉山の定義:
二叉の山は完全な二元の木か、あるいはほぼ完全な二元の木です。一番小さい二叉の山は父の接合点のキーの値がいつも小さいか、或いはどのサブノードのキーの値の山より小さいです。
保存:
二叉山は普通行列で表します。
ルートノードの配列内の位置は0であり、n番目の位置のサブノードはそれぞれ2 n+1および2 n+2である。
位置kの葉の親ノードの位置は(k-1)/2である。
実装:
前に書く:
目が覚めると、急に霊感が湧いてきました。
最小二叉山の定義:
二叉の山は完全な二元の木か、あるいはほぼ完全な二元の木です。一番小さい二叉の山は父の接合点のキーの値がいつも小さいか、或いはどのサブノードのキーの値の山より小さいです。
保存:
二叉山は普通行列で表します。
ルートノードの配列内の位置は0であり、n番目の位置のサブノードはそれぞれ2 n+1および2 n+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();
}
}
疑問があれば、メッセージをお願いします。あるいは、当駅のコミュニティで交流して討論してください。ありがとうございます。