Java语言实现最大堆代码示例

2023-09-19 23:39:09 55

最大堆

最大堆的特点是父元素比子元素大，并且是一棵完全二叉树。

data[1]开始存，data[0]空着不用。也可以把data[0]当成size来用。

publicclassMaxHeap>{
	privateT[]data;
	privateintsize;
	privateintcapacity;
	publicMaxHeap(intcapacity){
		this.data=(T[])newComparable[capacity+1];
		size=0;
		this.capacity=capacity;
	}
	publicintsize(){
		returnthis.size;
	}
	publicBooleanisEmpty(){
		returnsize==0;
	}
	publicintgetCapacity(){
		returnthis.capacity;
	}
	/**
*@return查看最大根(只看不删,与popMax对比)
*/
	publicTseekMax(){
		returndata[1];
	}
	publicvoidswap(inti,intj){
		if(i!=j){
			Ttemp=data[i];
			data[i]=data[j];
			data[j]=temp;
		}
	}
	publicvoidinsert(Titem){
		size++;
		data[size]=item;
		shiftUp(size);
	}
	/**
*@return弹出最大根(弹出意味着删除,与seekMax对比)
*/
	publicTpopMax(){
		swap(1,size--);
		shiftDown(1);
		returndata[size+1];
	}
	/**
*@paramchild孩子节点下角标是child，父节点下角表是child/2
*/
	publicvoidshiftUp(intchild){
		while(child>1&&data[child].compareTo(data[child/2])>0){
			swap(child,child/2);
			child=child/2;
		}
	}
	/**
*@paramadata数组中某个元素的下角标
*@parambdata数组中某个元素的下角标
*@return哪个元素大就返回哪个的下角标
*/
	privateintmax(inta,intb){
		if(data[a].compareTo(data[b])<0){
			//如果data[b]大
			returnb;
			//返回b
		}else{
			//如果data[a]大
			returna;
			//返回a
		}
	}
	/**
*@paramadata数组中某个元素的下角标
*@parambdata数组中某个元素的下角标
*@paramcdata数组中某个元素的下角标
*@return哪个元素大就返回哪个的下角标
*/
	privateintmax(inta,intb,intc){
		intbiggest=max(a,b);
		biggest=max(biggest,c);
		returnbiggest;
	}
	/**
*@paramfather父节点下角标是father,左右两个孩子节点的下角表分别是：father*2和father*2+1
*/
	publicvoidshiftDown(intfather){
		while(true){
			intlchild=father*2;
			//左孩子
			intrchild=father*2+1;
			//右孩子
			intnewFather=father;
			//newFather即将更新，父、左、右三个结点谁大，newFather就是谁的下角标
			if(lchild>size){
				//如果该father结点既没有左孩子，也没有右孩子
				return;
			}elseif(rchild>size){
				//如果该father结点只有左孩子，没有右孩子
				newFather=max(father,lchild);
			}else{
				//如果该father结点既有左孩子，又有右孩子
				newFather=max(father,lchild,rchild);
			}
			if(newFather==father){
				//说明father比两个子结点都要大，表名已经是大根堆，不用继续调整了
				return;
			}else{
				//否则，还需要继续调整堆，直到满足大根堆条件为止
				swap(father,newFather);
				//值进行交换
				father=newFather;
				//更新father的值，相当于继续调整shiftDown(newFather)
			}
		}
	}
	publicstaticvoidmain(String[]args){
		//创建大根堆
		MaxHeapmaxHeap=newMaxHeap(100);
		//向堆里存
		for(inti=0;i<100;i++){
			maxHeap.insert((int)(Math.random()*100));
		}
		//创建数组
		Integer[]arr=newInteger[100];
		//从堆里取，放进数组里
		for(inti=0;i<100;i++){
			arr[i]=maxHeap.popMax();
			System.out.print(arr[i]+"");
		}
		System.out.println();
	}
}

最大堆：shiftDown()函数与上面不一样

publicclassMaxHeap>{
	privateT[]data;
	privateintsize;
	privateintcapacity;
	publicMaxHeap(intcapacity){
		data=(T[])newComparable[capacity+1];
		this.capacity=capacity;
		size=0;
	}
	publicintsize(){
		returnsize;
	}
	publicBooleanisEmpty(){
		returnsize==0;
	}
	publicvoidinsert(Titem){
		data[size+1]=item;
		size++;
		shiftUp(size);
	}
	/**
*@return弹出最大根(弹出意味着删除,与seekMax对比)
*/
	publicTpopMax(){
		Tret=data[1];
		swap(1,size);
		size--;
		shiftDown(1);
		returnret;
	}
	/**
*@return查看最大根(只看不删,与popMax对比)
*/
	publicTseekMax(){
		returndata[1];
	}
	publicvoidswap(inti,intj){
		if(i!=j){
			Ttemp=data[i];
			data[i]=data[j];
			data[j]=temp;
		}
	}
	publicvoidshiftUp(intk){
		while(k>1&&data[k/2].compareTo(data[k])<0){
			swap(k,k/2);
			k/=2;
		}
	}
	publicvoidshiftDown(intfather){
		while(2*father<=size){
			intnewFather=2*father;
			if(newFather+1<=size&&data[newFather+1].compareTo(data[newFather])>0){
				//data[j]data[j+1]两者取大的那个
				newFather=newFather+1;
			}
			if(data[father].compareTo(data[newFather])>=0){
				break;
			}else{
				swap(father,newFather);
				//值进行交换
				father=newFather;
				//newFather是(2*father)或者是(2*father+1),也就是继续shiftDown(newFather);
			}
		}
	}
	publicstaticvoidmain(String[]args){
		//创建大根堆
		MaxHeapmaxHeap=newMaxHeap(100);
		//向堆里存
		for(inti=0;i<100;i++){
			maxHeap.insert((int)(Math.random()*100));
		}
		//创建数组
		Integer[]arr=newInteger[100];
		//从堆里取，放进数组里
		for(inti=0;i<100;i++){
			arr[i]=maxHeap.popMax();
			System.out.print(arr[i]+"");
		}
		System.out.println();
	}
}

总结

以上就是本文关于Java语言实现最大堆代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

Java语言实现最大堆代码示例

热门推荐

随机推荐