堆 （自己写）

堆也是基于数组的哦，所以在创建的时候，请先要考虑好数组的大小了

堆的介绍 

堆是一种树，由他实现的优先级队列的插入和删除的时间复杂度都是N

尽管这样的删除的时间变慢了一些，但是插入的时间快了很多了。当速度非常重要的时候，且有很多插入操作时，可以选择堆来实现优先级队列

这里的堆是一种特殊的二叉树，是完全二叉树，不要和java和C++等程序语言里的堆混合在一起，后者指的是程序员用new能够得到的计算机内存的

可以用的部分

堆是有如下特点的二叉树

1.它完全是完全二叉树，这也就是，除了树的最后一层是不需要满的，其他的每一层从左到右都是完全满的的

2、它常常用一个数组实现的。

3.堆中的没一个都满足堆的条件，也就是说，每一个节点的关键字都大于或者等于它的子节点，

     主要是关键词，不是我们所保持的数据的大小（那么可以想下，关键字最最大的那个就是我们的根同志了）

     

     堆在数组中的表示的---按照从上到下，从左到右的顺序来的

     堆的完全二叉树的事实也说明了表示堆的数组没有洞，从下标0到N-1，每一个数据单元都有数据项。

    

    

    弱序

    堆和二叉树搜索树相比是弱序的，在二叉搜索树中所有节点的左子孙的关键字都小于右边子孙的节点的关键字的值，

    这说明了在一个二叉搜索树中通过一个简单的算法就可以按序遍历节点。

        在对堆中，按序遍历节点是困难的，这是因为堆的组织规则比二叉树搜索树的组织规则弱。对于堆来说，只要求

        沿着从根到叶子的每一条叶子的每一条路径上，节点都是按序下降的即可。

            由于堆的弱序性，所以一些操作是困难的或者是不可能的，除了不支持遍历以外，也不能在堆上便利的查找指定的关键词，

            因为在查找过程中，没有足够的信息来决定信息来决定通过两个节点中哪一个节点。

            

            因此堆这种几乎接近无序的数据结构，不过，对于快速移除最大节点的操作以及快速的插入新的节点的操作，这种顺序是

            已经足够了的。这些操作使用的堆作为优先级队列时所需的全部操作。

 

 

下面的代码是用于理论的，整体的代码在最后会给出了的

 

//package endual;
//
//public class Heap {
//	int currentSize;
//	Node[] heapAArray;
//	/**
//	 * 插入
//	 * 插入节点也是恨容易的，插入使用向上帅选，而不是向下。节点初始时插入到数组最后第一个空着的单元
//	 * 中，数组容量大小不一。
//	 * 
//	 * heapArray[N] = newNode ;
//	 * N++ ;
//	 * 
//	 * 向上刷选可能破坏堆的平衡吧，所以要向上刷选选择一个新的节点然后交换
//	 * 直到它在一个大于它的节点之下，在小于它的节点智商的这么一个位子
//	 * 
//	 * @param nd
//	 */
//	
//	public void insert(int key) {
//
//		//插入是向上的的
//		if(currentSize == maxSize) { // 如果array is full了
//			return null ;
//		}
//		Node newNode = new Node(key) ; //对于传入进来的key值创建一个新的节点
//		
//		heapAArray[currentSize] = newNode ; //新的节点要挂到当前最大值的后面，这是因为从0开始的嘛，所以currentSize不用+1
//		/**
//		 * 插入以后调用trickleUp。找个这个位子的父节点，然后把这个节点保存在一个名为bottom的变量中。在while循环内部，变量
//		 * index沿着路径朝根的方向上行，依次的指向每一个节点。只要没有达到根，且index的父节点的关键字小于这个新的节点，while
//		 * 就一直执行下去
//		 *    
//		 */
//		trickleUp(currentSize++) ; //trick it up 向上刷新自己的位子
//		return null ;
//		
//	}
//
//	private void trickleUp(int i) {
//		
//		int parent = (i-1) / 2 ;//父亲节点的位子
//		Node bottom = this.heapAArray[i] ; //当前的节点的位子，就是刚刚插入的位子的节点
//		
//		while(i > 0 && this.heapAArray[parent].getKey() < bottom.getKey()) {
//		
//			this.heapAArray[i] = this.heapAArray[parent] ;
//			i = parent ;
//			parent = (parent - 1) / 2 ;
//		} // end while
//		
//		this.heapAArray[i] = bottom ;
//		
//	}
//
//	/**
//	 * 移除
//	 * 移除是说要删除掉关键字最大的节点，这个节点总是根节点，所以移除是相对而言比较简单的
//	 * 因为根在书中中的位子总是在第一个，那么只有移除第一个就可以了
//	 * maxNode = heapArray[0] ;
//	 * 
//	 * 问题是一旦移除了根节点，树就不完全了；怎么办呢，数组里面就有一个空的数据单元。这个
//	 * 洞必须要填上，可以把数组中所有数据项都忘前面移动一个单元，但是还有快的多的方法就是下面介绍的
//	 * 
//	 * 移除最大关键词根节点的方法：
//	 * 1.移走根
//	 * 2.把最后一个根节点移动到根的位子。
//	 * 3.一直向下刷选（其实就是遍历这个树的每一个节点了，先比较下下面的子节点和孙子节点，找到这样的节点就交换位子，让出这个root位子）
//	 *    这个节点，直到它在一个大于它的节点之下，有小于它的节点之上停止。
//	 * 最后一个节点是树的最底层的最右边的数据项，它对应于数组中最后一个填入的数据单元。
//	 * 
//	 * 如果数组中的节点的所以是X，那么它在
//	 * 父节点上的下标的位子应该是（x-1） / 2
//	 * 它的左子节点的下标为2x+1
//	 * 它的右子节点的下标为2x+2
//	 *             
//	 * 
//	 * 
//	 * @return
//	 */
//	public Node remove() {
//		// TODO Auto-generated method stub
//		return null;
//	}
//		
//	
//}
//
///**
// * priorityQueue类中的方法简单的封装了内部的Heap类的方法，它们的功能相同。这个例子在概念上清楚地表明了优先级
// * 队列是一个可以用不同的方法实现的ADT，而堆是一种更为基础的数据结构。
// * 这个程序是为了简单起见，用的是没有分装在优先级队列中的堆方法。
// * @author Endual
// *
// */
//	 class PriorityQueue {
//
//		private Heap theHeap ;
//
//		public void insert(Node nd) {
//			theHeap.insert(nd) ;
//		}
//		
//		public Node remove() {
//			
//			return theHeap.remove() ;
//		}
//	 }

 

 

堆的整体的的代码（貌似还有点问题）

你可以复制到自己的代码中 研读下 改改哦

package endual;

/**
 * 在堆的节点中，使用了一个iData的变量来保存关键字
 * 实际的使用中，有其他的数据。
 * @author Endual
 *
 */
public class Node {

	private int iData ; //节点的关键词

	public Node(int iData) {
		super();
		this.iData = iData;
	}

	public int getiData() {
		return iData;
	}

	public void setiData(int iData) {
		this.iData = iData;
	}
	
	
	
}

 

 

 

    Heap的代码

 

package endual;

public class Heap {

	private Node[] heapArray ; //节点的数组
	private int maxSize ; //该栈最大能容多少
	private int currentSize ; //当前栈有多少数据了
	//private Node noNode ;
	
	public Heap(int maxSize) {
		super();
		this.maxSize = maxSize; //设置了对该对的最大的容量
		this.heapArray = new Node[this.maxSize] ; //创建一堆的对象
		this.currentSize = 0; //当前堆中有多少个数据项了
		//noNode = new Node(-1) ;
	}
	//判断是不是为空
	public boolean isEmplay() {
		
		if (this.currentSize == 0) 
			return true; 
		
		return false ;
		
	}
	
	//判断不是为满的
	public boolean isFull() {
		
		if (this.currentSize == this.maxSize) {
			
			return true ;
		}
		
		return false ;
		
	}
	
	//插入数据
	public void insert(int iData) {
	
		//插入数据是从最后面的向上寻找位子的
	     //最先是挂在数组的最后面的位子
		//第一步，创建一个要插入的Node
		Node newNode = new Node(iData) ; 
		//第二步判断这个堆不是是满了
		if(this.isFull()) {
			System.out.println("无法插入 " + iData+" ,堆已经满了");
			return ;
		}
		
		//如果没满，第三步就是插入到堆中去
		this.heapArray[this.currentSize] = newNode ; //添加进去
		trickUp(this.currentSize) ; //向上寻找最佳的位子 ,加入进去的是当前添加node的位子
		this.currentSize++ ; //对了一个数据，所以当前的记录要增加1个
		return ;
	
	}
	//当插入数据，在这里重新寻找到合适的位子
	private void trickUp(int currentSize) {
       //重新排列this.heapArray
	   int parent = (currentSize - 1) / 2 ; //找到当前的插入数据项的父亲节点在数组中的下标的位子是多少
       Node bottom = new Node(currentSize) ;
	   //1.如果我们找到的父亲的的关键字小于自己的关键字那么就停止我们的操作
	   //2.如果父亲节点是0,那么将跳出while直接和根节点进行交换了
	   while(parent > 0 && this.heapArray[parent].getiData()< bottom.getiData()) {
		  
		   this.heapArray[currentSize] = this.heapArray[parent] ; //将上面的一下来
		   this.heapArray[parent] = null ; //将父亲节点复制给当前节点，将父亲节点留空
		   //当前的节点就是向上爬一级，变成了父亲节点了 
		   currentSize = parent ;
		   //那就找parent的parent
		   parent = (parent - 1) / 2 ;
		        
	   }
	   //父亲节点和孩子节点进行交换
       this.heapArray[currentSize] = bottom ;
	
	}
	
	//得到最大的值
	public int getMax() {
		//就是第一个节点的关键词了
		if(this.isEmplay()) {
			return (Integer) null ;
		}
		
		return this.heapArray[0].getiData() ;
	}
	
	//删除掉最大的值
	public int remove() {
		
		if (this.isEmplay()) {
			return (Integer) null ;
		}
		
		int res = this.heapArray[0].getiData() ;
		this.heapArray[0] = this.heapArray[this.currentSize-1] ;//现在就相当于删掉了头，用数组的最后一个节点来代替
		this.heapArray[this.currentSize-1] = null ; //将最后一个位子滞空
		this.currentSize-- ; //数组的总数减去一个
		//下面就来进行向下寻找合适的位
		trickDown(0) ; //向上寻找最佳的位子 ,加入进去的是当前添加node的位子
		return res ;
		
	}
	
	//重新排列我们的数组喽
	private void trickDown(int i) {
		
		int largeChild ;
		Node top = this.heapArray[i] ; 
		
		while (i < currentSize / 2) {
			
			int leftChild = i * 2 + 1 ;
			int rightChild = leftChild + 1 ;
			
			if (rightChild < currentSize 
					&& this.heapArray[leftChild].getiData() 
					< this.heapArray[rightChild].getiData()) {
				largeChild = rightChild ;
			}
			else {
				largeChild = leftChild ;
			}
			
			if (top.getiData() >= this.heapArray[largeChild].getiData()) {
				i = largeChild ;
			}
			
		} // end while
		this.heapArray[i] = top ;
	}//end trickDown
	
	
  public void disPlay(){
	  
	  System.out.println("----" + this.heapArray[0].getiData()) ;
	  
  }
}

 

测试的类

 

 

package endual;

public class HeapApp {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Heap heap = new Heap(4) ;
		heap.insert(1) ;
		heap.insert(4) ;
		heap.insert(2) ;
		heap.insert(3) ;
		heap.insert(6) ;
		heap.insert(63) ;
		
		heap.disPlay() ;
		
	}

}