一、堆
1.概念:它时完全二叉树,处理最后一层节点不需要满,其他的从左到右都是满的 (底层用数组实现);
2.特性: 1)如果一个节点位置为k,那么它的父节点的位置为k/2,而他的两个子节点的位置分别为2*k和2*k+1;
2)每个节点都大于它的子节点那么这个堆为大根堆
3)每个节点都小于它的子节点那么这个堆为大根堆
3。大根堆基本实现
1)插入:先将要插入的元素插入到最后的位置。
用上浮的方法进行排序:让插入的新结点k,与父节点2*k进行比较,如果小则不用移动,如果大,则于父节点进行交换,交换之后再与其现在的父节点比较,以此类推。
2)删除堆中最大元素:大根堆的最大元素就是根节点,首先让根节点与最后个叶子节点k互换,然后再删除最大索引处的值
用下浮的方法,让k与它的左右子节点中大一个进行比较,如果k大则交换,小则不用移动。
public class Heap<T extends Comparable<T>> { //存储堆中的元素 private T[] items; //元素个数 int N; public Heap(int capacity) { //废弃数组中的第0个位置,从第1个位置开始存储 this.items= (T[]) new Comparable[capacity+1]; this.N=0; } //判断索引i处的元素是否小于j处的元素 public boolean less(int i, int j){ return items[i].compareTo(items[j])<0; } //交换堆中i索引和j索引处的值 public void exch(int i,int j){ T temp=items[i]; items[i]=items[j]; items[j]=temp; } //向堆中插入一个元素 public void insert(T t){ items[++N]=t; swim(N); } //使用上浮算法,使索引k处的元素再堆中处于一个正确的位置 private void swim(int k){ //让当前节点域大的父节点相比,大于则交换,小于就不用移动 //根节点的索引为1,当k等于1时候已经为根节点的位置就不用移动 while (k>1){ if( less(k/2, k)) { exch(k / 2, k); } k=k/2; } } //删除堆中最大的元素,返回这个元素 public T delete(){ if (N==0){ return null; } T max=items[1]; //交换根元素和最大索引处的元素 exch(1,N); //删除最大索引处的元素 items[N]=null; //元素-1 N--; sink(1); return max; } //使用下沉算法,使索引处的元素再堆中处于一个正确位置 private void sink(int k){ //通过循环不断对比k于左子节点(2*k)右子节点(2*k+1)中最大比较,小则交换,大则不用交换 while (2*k<=N){ //获取当前节点的左右子节点中较大一个 int max=0; if (2*k+1<=N){ if (less(2*k,2*k+1)){ max=2*k+1; }else { max=2*k; } }else { //该节点无右节点 max=2*k; } //比较k和max的值 if (!less(k,max)){ break; } exch(k,max); k=max; } } }