用java实现堆

1、堆是一种特殊的二叉树

堆总是一颗完全二叉树（即除最底层外，其它层节点都被元素填满，且最底层从左向右尽可能填满结点）

2、分为最大堆和最小堆，最大堆中某结点的值总是不大于其父节点的值，最小堆中某结点的值总是不小于其父节点的值

3、堆的实现：  用数组实现    构造二叉树     

ArrayList<Integer> array=new ArrayList<Integer>(); //ArrayList<Integer> array=new ArrayList<Integer>(capacity);

数组是按层次存放堆这棵二叉树中的结点值的

数组中的元素并不是按从大到小的顺序排列的，从堆中取出元素只能取出堆顶元素，即只能获得最大值或最小值

4、index为数组中当前元素的索引，则该元素的父节点在数组中的索引为(index-1)/2，该元素的左孩子在数组中的索引为2*index+1，该元素的右孩子在数组中的索引为2*index+2

5、以最大堆为例

（1）向堆中添加元素：

时间复杂度：O(logn)

将该元素先添加到数组的尾部（即充当最底层的最后一个叶结点），然后将该元素与其父节点进行大小比较，若大于其父节点则与父节点进行交换，继续与上一层父节点进行比较，如此重复，直至小于等于父节点为止

//向堆中添加元素 public void addValue(ArrayList<Integer> array,int value) { if(array==null) return; array.add(value); int i=array.size()-1; while(i>=1&&value>array.get((i-1)/2)) { array.set(i,array.get((i-1)/2)); array.set((i-1)/2,value); i=(i-1)/2; } }

（2）删除堆顶元素：

时间复杂度：O(logn)

将堆顶元素A与最后一个元素B交换后（即数组的首尾元素互换），删除A，从堆顶元素开始比较其与左右孩子的大小，若同时小于左右孩子，则与左右孩子中的较大者交换，否则与大于其的孩子交换，继续与下一层左右孩子进行比较，如此重复，直至大于等于左右孩子为止

removeValue=swap+sift

//删除堆顶元素 public void removeValue(ArrayList<Integer> array) { if(array==null||array.size()==0) return; array.set(0,array.get(array.size()-1)); array.remove(array.size()-1); int i=0; while(2*i+1<array.size()) { int value=array.get(i); int a=array.get(2*i+1); int max=a; int index=2*i+1; //左右孩子都存在 if(2*i+2<array.size()) { int b=array.get(2*i+2); if(b>a) { max=b; index=2*i+2; } } if(value<max) { array.set(i,max); array.set(index,value); i=index; } else break; } }

（3）返回堆中的元素个数

return array.size();

（4）判断堆是否为空

return array.isEmpty();

（5）返回数组索引

//返回父节点在数组中的索引 return (index-1)/2; //返回左孩子在数组中的索引 return 2*index+1; //返回右孩子在数组中的索引 return 2*index+2;

（6）替换：将堆顶元素替换为其他元素

         时间复杂度：O(logn)

removeValue()+addValue()

（7）Heapify：将任意数组转化为堆的形状

时间复杂度：O(n)

将数组看成一棵完全二叉树，从最后一个叶节点的父节点开始，到根节点结束，依次判断各节点与其左右孩子的大小关系并进行调整

0~array.size()-1/2进行sift

public void heapify(ArrayList<Integer> array) { int y=array.size()-1; int i=(y-1)/2; for(int j=i;j>=0;j--) sift(array,j); return; } public void sift(ArrayList<Integer> array,int i) { while(2*i+1<array.size()) { int value=array.get(i); int a=array.get(2*i+1); int max=a; int index=2*i+1; //左右孩子都存在 if(2*i+2<array.size()) { int b=array.get(2*i+2); if(b>a) { max=b; index=2*i+2; } } if(value<max) { array.set(i,max); array.set(index,value); i=index; } else break; } }

将n个元素插入一个空堆中，时间复杂度为O(nlogn)

6、优先队列具有最高优先级先出的特点，所以采用最大堆数据结构

      java.util.PriorityQueue类底层就是通过优先级堆实现的