数据结构之堆 堆是什么？堆是一种特殊的完全二叉树，就像下面这棵树一样 最小堆的特点：所有父节点的值都比子节点要小！相反 最大堆得特点：所有父节点的值都比子节点要大！
如何构造堆呢？ 99,5,36,7,22,17,46,12,2,19,25,28,1,92 对于这样一串数字来说，首先建立一个数组a，长度为15,（a[0]不存数字，从下标1开始） 首先所有的叶子节点都是满足最小堆的条件的，因为他们没有子节点，因此应该从n/2开始（n为数字的个数，而不是数组的长度，这里等于14），判断是否满足堆得性质，如果不满足，则调整，Java代码如下：
public class Heap { public static void main(String[] args) { int[] a=new int[]{0,99,5,36,7,22,17,46,12,2,19,25,28,1,92}; for(int i=14/2;i>=1;i--) topToDown(a, i); for(int i=1;i<a.length;i++) System.out.print(a[i]+" "); } public static void topToDown(int[] a,int index){ if(index>=a.length||2*index>=a.length) return ; if(2*index+1>=a.length){ if(a[index]<a[2*index]) return ; else{ int temp=a[2*index]; a[2*index]=a[index]; a[index]=temp; topToDown(a, 2*index); } }else{ if(a[index]<a[2*index]&&a[index]<a[2*index+1]) return ; else{ int temp; if(a[2*index]>a[2*index+1]){ temp=a[2*index+1]; a[2*index+1]=a[index]; a[index]=temp; topToDown(a, 2*index+1); }else{ temp=a[2*index]; a[2*index]=a[index]; a[index]=temp; topToDown(a, 2*index); } } } } }如何利用堆呢？ 堆可以用来求最大最小值，也可以排序数组，下面举个例子
题目描述 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。 求最小的K个数，解题过程如下：利用数组的前K个数构造一个堆，并且维护成为最大堆，然后遍历数组的第k+1个数，如果比堆顶元素大，则丢弃，继续遍历k+2个数，如果比堆顶元素小，则将堆顶元素置换为这个数，并且维护堆的性质，再遍历k+2个数。这样依次这样依次下去，当数组遍历完的时候，堆中的元素就是最小的K个数！ Java代码实现如下
public class Heap { public static void main(String[] args) { int[] a=new int[]{4,5,1,6,2,7,3,8}; int[] heap=new int[5]; for(int i=0;i<4;i++){ heap[i+1]=a[i]; } for(int i=8/2;i>=1;i--) maxHeap(heap, i); for(int i=4;i<a.length;i++){ if(a[i]<heap[1]){ heap[1]=a[i]; maxHeap(heap, 1); } } for(int i=1;i<heap.length;i++) System.out.print(heap[i]+" "); } public static void maxHeap(int[] heap,int index){ if(index>=heap.length||2*index>=heap.length) return ; if(2*index+1>=heap.length){ if(heap[index]<heap[2*index]){ int temp=heap[2*index]; heap[2*index]=heap[index]; heap[index]=temp; maxHeap(heap, 2*index); }else{ return ; } }else{ if(heap[index]>heap[2*index]&&heap[index]>heap[2*index+1]) return ; else{ int temp; if(heap[2*index]>heap[2*index+1]){ temp=heap[2*index]; heap[2*index]=heap[index]; heap[index]=temp; maxHeap(heap, 2*index); }else{ temp=heap[2*index+1]; heap[2*index+1]=heap[index]; heap[index]=temp; maxHeap(heap, 2*index+1); } } } } }