动力节点首页 全国咨询热线:400-8080-105

绑定手机号,登录
手机号

验证码

微信登录
手机号登录
手机号

验证码

30天自动登录
微信登录与注册
微信扫码登录与注册

扫码关注微信公众号完成登录与注册
手机号登录
首页 > 文章

数据结构堆的实现

08-03 10:53 345浏览
举报 T字号
  • 大字
  • 中字
  • 小字

符合以下规则:

1.元素可比较性:数据集中的元素可以进行比较,就是要实现Comparable接口;。

2.节点最大/最小性:每个节点的元素必须大于或小于该节点的孩子节点的元素;

3.堆是一棵完全二叉树。

堆有两种:最大堆和最小堆。

最小堆中每个节点的优先级小于或者等于它的子节点;最大堆则相反,每个节点的优先级都大于或者等于它的子节点。

如下图:

本文只着重讲最大堆吧,最小堆是一样的。

堆的大小是提前知道的,在java集合中堆是通过ArrayList数组实现的:

1.根节点位置:根节点的数据总是在数组的位置[0]

2.节点的父节点位置:假设一个非根节点的数据在数组中的位置[i],那么它的父节点总是在位置[(i-1)/2]

3.节点的孩子节点位置:假设一个节点的数据在数组中的位置为[i],那么它的孩子(如果有)总是在下面的这两个位置:左孩子在[2*i+1],右孩子在[2*i+2]

在堆中主要是插入和删除节点的操作,这两种操作无论是哪一种,完成之后都还是一个堆,操作时要进行堆的调整,使其是个新堆。

添加一个新节点:(不断地和父节点比较)

插入的思路是这样的:当插入一个元素时,先将这个元素插入到队列尾,然后将这个新插入的元素和它的父节点进行优先权的比较,如果比父节点的优先权要大,则和父节点呼唤位置,然后再和新的父节比较,直到比新的父节点优先权小为止

删除一个节点(不断比较左右孩子节点大小,大的上移)

从堆中删除优先权最大的元素的思路是将队列尾的元素值赋给根节点,队列为赋值为null。然后检查新的根节点的元素优先权是否比左右子节点的元素的优先权大,如果比左右子节点的元素的优先权小,就交换位置,重复这个过程,直到秩序正常。

heap.java实现

//最大堆
import java.util.ArrayList;
public class Heap<E extends Comparable>{
	private ArrayList<E> list=new ArrayList<E>();//用数组实现堆	
    public Heap(){}
    public Heap(E[] objects){
    	for(int i=0;i<objects.length;i++){
    		add(objects[i]);
    	}
    }    
    public void add(E newObject){//添加一个元素
    	list.add(newObject);
    	int currentIndex=list.size()-1;    	
    	while(currentIndex>0){
    		int parentIndex=(currentIndex-1)/2;//找到该结点的父结点
    		if(list.get(currentIndex).compareTo(list.get(parentIndex))>0){//与父节点比较
    			//如果当前结点的值大于父结点就交换位置
    			E temp=list.get(currentIndex);
    			list.set(currentIndex, list.get(parentIndex));
    			list.set(parentIndex, temp);   			
    		}
    		else
    			break;
    		currentIndex=parentIndex;
    	}    	
    }    
    public E remove(){//删除并返回根结点,堆的特点是移除了根结点后还是堆
    	if(list.size()==0) return null;    	
    	E removeObject=list.get(0);
    	list.set(0, list.get(list.size()-1));//把最后一个结点放在根结点的位置
    	list.remove(list.size()-1);    	
    	int currentIndex=0;
    	while(currentIndex<list.size()){
    		int leftChildIndex=2*currentIndex+1;
    		int rightChildIndex=2*currentIndex+2;//左右孩子结点的坐标    		
    		if(leftChildIndex>=list.size())break;
    		//比较左右孩子的值,使maxIndex指向值大的结点
    		 int maxIndex=leftChildIndex;
    		 if(rightChildIndex<list.size()){
    			 if(list.get(maxIndex).compareTo(list.get(rightChildIndex))<0){
    				 maxIndex=rightChildIndex;
    			 }
    		 }
    		 //如果当前结点的值小于其左右孩子中的大的值,就交换两个结点
    		 if(list.get(currentIndex).compareTo(list.get(maxIndex))<0){
    	          E temp=list.get(maxIndex);
    	          list.set(maxIndex, list.get(currentIndex));
    	          list.set(currentIndex, temp);
    	          currentIndex=maxIndex;
    	    	}
    		 else
    			 break;
    	}    	
    	return removeObject;   	
    	
    }    
    public int getSize(){
    	return list.size();
    }    
}

动力节点在线课程涵盖零基础入门,高级进阶,在职提升三大主力内容,覆盖Java从入门到就业提升的全体系学习内容。全部Java视频教程免费观看,相关学习资料免费下载!对于火爆技术,每周一定时更新!如果想了解更多相关技术,可以到动力节点在线免费观看数据结构视频教程哦!

0人推荐
共同学习,写下你的评论
0条评论
代码小兵345
程序员代码小兵345

44篇文章贡献168626字

相关课程 更多>

作者相关文章更多>

推荐相关文章更多>

Java面试题及答案整理

代码小兵66904-21 20:01

6道经典算法面试题

杨晶珍05-12 16:39

简述Spring MVC的核心组件

代码小兵49806-11 16:26

SpringMVC 中的组件

代码小兵49806-11 16:28

Spring常见面试题

代码小兵92504-17 16:07

发评论

举报

0/150

取消