堆的特性∶
1.它是完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满。
2.它通常用数组来实现。
具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子结点的子结点则分别在位置4,5,6和7，以此类推。
如果一个结点的位置为k，则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。这样，在不
使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动︰从ak]向上一层，就令k等于k/2,向下一层就令k等于2k或2k+1。
3.每个结点都大于等于它的两个子结点。这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，跟我们之前学习的二叉查找树是有区别的。
（1）如果 往堆中新插入元素，只需要不断的比较新结点a[k]和它的父结点a[k/2]的大小，然后根据结果完成数据元素的交换 ，就可以完成堆的有序调整。（如果父节点的值比当前结点的值小，则交换位置 ）
（2）如果 往堆中删除最大元素 ，第一个元素就是最大元素，删除掉后。将最后一个元素放到索引1处，然后不断的拿 当前节点a[k]和它的子节点a[2k]和a[2k+1]中较大者交换位置 。
//堆代码 public class Heap<T extends Comparable<T>>{ //存储堆中的元素 private T[] items; //记录堆中元素的个数 private int N; public Heap(int capacity){ this.items = (T[]) new Comparable[capacity+1]; //因为数组下标0没有使用 this.N = 0; } //判断堆中索引i处的元素是否小于索引j处的元素 private boolean less(int i, int j){ return items[i].compareTo(items[j])<0; } // 交换堆中i索引和j索引处的值 private void exch(int i, int j){ T temp = items[i]; items[i] = items[j]; items[j] = temp; } // 往堆中插入一个元素 public void insert(T t){ //因为一开始N=0，这样第一个插入的元素就在items[1]， items[++N]=t; //需要调整元素位置，让堆有序（每个结点都大于其两个子结点） swim(N); } // 使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置 // 不断和父节点比较 private void swim(int k){ //如果父节点的值比当前结点的值小，则交换位置 while(k>1){ if(less(k/2,k)){ exch(k/2,k); }else{ break; } k = k/2; } } // 删除堆中最大的元素，并返回这个最大元素 public T delMax(){ //删除最大元素，其实就是删除根结点 T max = items[1]; //交换到索引结尾处 exch(1, N); items[N]=null; N--; sink(1); return max; } // 使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置 // 当前节点a[k]和它的子节点a[2k]和a[2k+1]中较大者交换位置 private void sink(int k){ //如果当前已经是最低层了，则不用循环 while(2*k<=N){ int max; //暂存较大的子节点 //<=N 说明存在叶子节点 if (2*k+1<=N){ if(less(2*k,2*k+1)){ max = 2*k + 1; }else{ max = 2*k; } }else{//不存在右子结点 max = 2*k; } if(!less(k,max)){ break; } exch(k,max); //变化k的值 k = max; //下一次循环 } } }
下面是堆排序:
