简单_二叉堆
堆是一种比较有用的数据结构，是二叉树的一种数组的表示形式。
最大堆和最小堆是二叉堆的两种形式。
最大堆：根结点的键值是所有堆结点键值中最大者。
最小堆：根结点的键值是所有堆结点键值中最小者。
而最大-最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。
最大-最小堆是最大层和最小层交替出现的二叉树，即最大层结点的儿子属于最小层，最小层结点的儿子属于最大层。
以最大（小）层结点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。
堆的实现代码如下：
package sunfa;import java.util.Arrays;import java.util.Random;/** * 堆的性质： 在起始索引为 0 的“堆”中： <br> * 1) 堆的根节点将存放在位置 0 <br> * 2) 节点 i 的左子节点在位置 2 * i + 1 <br> * 3) 节点 i的右子节点在位置 2 * i + 2 <br> * 4) 节点 i 的父节点在位置 floor( (i - 1) / 2 ) : 注 floor 表示“取整”操作 * * 在起始索引为 1 的“堆”中： <br> * 1) 堆的根节点将存放在位置 1 <br> * 2) 节点 i 的左子节点在位置 2 * i <br> * 3) 节点 i 的右子节点在位置 2 *i + 1 <br> * 4) 节点 i 的父节点在位置 floor( i / 2 ) : 注 floor 表示“取整”操作 * * 以起始索引为1的堆比较好算 * * 可以参考：http://wxg6203.iteye.com/blog/668968 */public class MyHeap2 {private Integer[] heap;private int size = 0;private int DEFAULT_SIZE = 10;public MyHeap2(int n) {if (n > DEFAULT_SIZE) {DEFAULT_SIZE = n;}heap = new Integer[DEFAULT_SIZE];}/** * 对整个堆进行堆化 */public void heapify() {for (int i = size / 2; i >= 1; i--) {fixDown(i);}}/** 获取根节点 */public Integer first() {return heap[1];}/** 获取最后一个节点 ,不保证最后一个节点是最大的,只能保证根节点是最大或最小的 */public Integer last() {return heap[size];}public int removeFirst() {int f = heap[1];heap[1] = heap[size];heap[size--] = null;fixDown(1);return f;}/** * 下移 * * @param k * 目标节点的索引 */private void fixDown(int k) {int j;// 目标节点的(左/右)子节点索引while ((j = k << 1) <= size && j > 0) {// 如果目标节点k的左子节点大于目标节点k的右子节点，那么重置子节点索引为较小的那个if (j < size && heap[j] > heap[j + 1])j++;if (heap[k] <= heap[j])break;swap(heap, k, j);k = j;// 非递归式下移搜索}}private void swap(Integer[] a, int i, int j) {Integer tmp = a[i];a[i] = a[j];a[j] = tmp;}// 向堆中添加元素,堆的根节点的索引是从1开始的public void add(Integer o) {if (size + 1 == heap.length)heap = Arrays.copyOf(heap, heap.length << 1);heap[++size] = o;// 堆根节点的索引从1开始,保留数组的第一个值为NULL// 每次新增元素后可能会破坏堆的性质，所以要进行上移操作。// 如果当前新增的元素比它的父节点要大，那么就要把当前元素和它的父节点进行交换，这么反复的直到根节点位置。这就是上移。fixUp(size);}/** * 上移:即我们把该节点移动到它的父节点的位置，而让它的父节点到它的位置上，然后我们继续判断该节点，直到该节点不再大于它的父节点为止才停止“上移”。 * * @param k * 父节点的位置 */private void fixUp(int k) {while (k > 1) {int j = k >> 1;// 根据堆的性质，每次根据当前节点的索引得到父节点的索引if (heap[j] <= heap[k])break;swap(heap, k, j);k = j;// 非递归式上移搜索}}public static void main(String[] args) {Random ran = new Random();int n = 20;Integer[] arr = new Integer[n];for (int i = 0; i < n; i++) {arr[i] = ran.nextInt(100);}System.out.println("arr:" + Arrays.toString(arr));MyHeap2 myheap2 = new MyHeap2(arr.length);for (int i = 0; i < arr.length; i++) {myheap2.add(arr[i]);System.out.println(Arrays.toString(myheap2.heap) + ",i:" + arr[i]+ ",size:" + myheap2.size);}System.out.println("removeFirst:");while (myheap2.size > 0) {System.out.println("remove:" + myheap2.removeFirst() + ",heap:"+ Arrays.toString(myheap2.heap));}}}