Java实现最大二叉堆中找min<=x

程序员文章站 2022-07-10 22:35:11

...

写在前面：
定义见上一篇文章
代码：

/**
	 * @description 最大二叉树中找a<=x<b的x
	 * @param min
	 * @param max
	 * @param array
	 * @return
	 * 
	 * @author LynnWong
	 */
	private int[] getX(int min,int max,int[] array){
		int rootSite = 0;
		int n = 0;
		int [] XArray = new int[array.length];
		while(rootSite<array.length-1){
			int root = array[rootSite];
			if(root>min||root==min){
				if((rootSite*2+1<array.length-1)&&(min==array[rootSite*2+1]||min<array[rootSite*2+1])&&array[rootSite*2+1] <max){
					XArray[n++]=array[rootSite*2+1];
				}
				if((rootSite*2+1<array.length-1)&&(min==array[rootSite*2+2]||min<array[rootSite*2+2])&&array[rootSite*2+2] <max){
					XArray[n++]=array[rootSite*2+2];
				}
			}else
				break;
			rootSite++;
		}
		
		return XArray;
	}

/**
	 * @description 元素添加到末尾，和它的父节点比，如果比它大就交换
	 * @param array
	 * 
	 * @author LynnWong
	 */
	private int[] getMaxBinaryHeap(int[] array){
		int N = array.length;
		int maxBinaryHeap[] = new int[N];
		int root;//根的值
		int heapSize = 0;//记录插入位置
		for(int num : array){
			maxBinaryHeap[heapSize]=num;
			++heapSize;
			int pointer = heapSize-1;//当前指向的数组元素位置
			while(pointer!=0){
				int leafPointer = pointer;//叶子节点位置
				pointer = (pointer-1)/2;//根节点位置
				root = maxBinaryHeap[pointer];//根节点
				if(num<=maxBinaryHeap[pointer]){//永远把当前数组元素看成叶子与其根比较或者换位
					break;
				}//如果根比叶子小 就交换位置
				maxBinaryHeap[pointer] = num;
				maxBinaryHeap[leafPointer] = root;
				
			}
		}
		return maxBinaryHeap;
		
	}

/**
 * 我就喜欢测10遍！
 */
public void text(){
	for(int i=0;i<10;i++){  
        Random rnd = new Random();   
        int [] lala = {rnd.nextInt(8),rnd.nextInt(8),rnd.nextInt(8),rnd.nextInt(8),rnd.nextInt(8),rnd.nextInt(8)};  
	int array[] = 
			this.getMaxBinaryHeap(lala);
//		{5,2,0,0,2,0};
	int result[] = this.getX(3, 6, array);
	 System.out.print("输入：");  
        for(int a : array){  
            System.out.print(a+" ");  
        }  
        System.out.print(" 条件： 3<=x<6");
        System.out.println();  
        System.out.print("输出：");  
        for(int a : result){  
            System.out.print(a+" ");  
        }  
        System.out.println(); 
	}
}

完成！
*******************分割线啊分割线*********************
完成它，共用了10分钟。听的背景音乐：《好男人》张赫宣
lysh 你也听听啊!

相关标签： java 算法

上一篇： 近期关于CI/CD策略以及git分支模型的思考

下一篇： bootstrap用dropdown-menu实现上下文菜单

推荐阅读

• Java实现最大二叉堆中找min<=x

• Java实现最大二叉堆中找min<=x