java堆的创建与基础代码解析（图文）

一.大根堆的创建

创建大根堆，以下是前置基础代码。（array 是需要被调整为大根堆的数组，elem 是用来展现array被调整之后为大根堆的数组）

    public int[] elem;public int usedsize;public Heap(){this.elem = new int[10];}public void init(int[] array){for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedsize ++;}}

 创建大根堆的思想是：我们通过 （usedsize -1-1）/2 来找到 parent 节点，再通过 parent 节点来找到 child 节点，通过比较下标为 child 和 child+1 两个节点，来找到值较大的节点和 parent 节点来比较，比较之后再来确定要不要对节点来进行交换，比如：我有一个数组{4，2，3，1，5，6，7}以下的3就是我们找到的 parent 节点，6就是我们找到的 child 节点。如图所示 child 节点是比child+1 节点要小的，所以我们让 child+1 节点和 parent 节点比较， child+1 节点要大于 parent 节点，进行更换之后如图二

图一

 图二就是进行交换之后的状态，此时 7，6，3，构成一个小的大根堆，按代码，我们需要让parent--，并且重新找child节点，如图三：

 图二

 对图三中我们继续进行比较和更换操作得到图四：

                              图三                                                                             图四

在图四的基础上，parent-- ，重复比较和更换的操作，我们可以发现，图五已经结束，但整个堆并不是大根堆，对顶上进行调整之后，其他地方也发生了改变，接下来我们需要进行的操作就是向下 调整，由于是 4 和 7 两个交换了值，所以交换之后，我们需要对 4 节点重新进行调整，让 parent = child+1 节点，重新找child 节点，重新进行调整，调整之后就会发现我们已经完成了创建大根堆的操作。

                          图五                                                                                  图六

代码展示：

    public void GreatHeap(){for (int parent =( usedsize -1-1)/2; parent >= 0; parent--) {siftmaxHeap(parent,usedsize);}}public void siftmaxHeap(int parent,int usedsize){int child = 2*parent + 1;while(child < usedsize){if(child +1 < usedsize && elem[child+1] > elem[child]){child++;}//elem[child] 跟 elem[parent] 进行比较，交换。if(elem[child] > elem[parent]){swap(elem,parent,child);parent = child;child = 2*parent +1;}else {break;}}}public void swap(int[] elem,int parent,int child){int k = elem[parent];elem[parent] = elem[child];elem[child] = k;}public void printf(){for (int i = 0; i < elem.length; i++) {System.out.print(elem[i]);}}
}

Test测试：

public class Test {public static void main(String[] args) {int[] array= {4,2,3,1,5,6,7};Heap ret = new Heap();ret.init(array);ret.GreatHeap();ret.printf();}
}

运行结果：  与预期结果相符

二.大根堆的插入

大根堆的插入我们需要用到向上调整，将插入的数值塞入到数组的最后一个位置，找到此位置的parent 节点，通过不断地循环比较，慢慢的将新数组调整为大根堆的形态。

代码：

    public void offer(int val){if(elem.length == usedsize){elem = Arrays.copyOf(elem,2*elem.length);}elem[usedsize] = val;usedsize++;siftup(usedsize);}public void siftup(int size){int parent = (size-1-1)/2;int child = size-1;while (parent >= 0){if (elem[child] > elem[parent]){swap(elem,parent,child);child = parent;parent = (child-1)/2;}else {break;}}}

 test测试：

public class Test {public static void main(String[] args) {int[] array= {4,2,3,1,5,6,7};Heap ret = new Heap();ret.init(array);ret.GreatHeap();ret.printf();System.out.println();ret.offer(9);ret.printf();}
}

 运行结果：   可以看到是符合预期结果的。

三.大根堆的删除

删除其中某个节点，以下代码提供的是删除节点的下标，如需删除某个值，可以先求出下标再删除，本文直接提供下标。我们将要删除的节点与数组的最后一个节点相交换，让usedsizie--，然后以删除的下标节点为主，进行向下调整，调整之后就可以实现大根堆的删除操作。

代码展示：

public void poll(int set){swap(elem,set,usedsize-1);usedsize--;siftmaxHeap(set,usedsize);}

text测试：

public class Test {public static void main(String[] args) {int[] array= {4,2,3,1,5,6,7};Heap ret = new Heap();ret.init(array);ret.GreatHeap();ret.printf();System.out.println();ret.poll(3);ret.printf();}
}

运行结果：符合预期（由于我们已经让usedsize--，数组空间为10固定不变，所以展现出来的结果只用看前六位即可）

四.tops-k问题

这个问题意思是，给你 n 个数据，让你来求这 n 个数据的前 k 个最大/最小的问题，这边以求前 k 个最小的值为例。我们将数组的前 k 个元素组成大根堆，然后将其余 n-k 个元素依次与堆顶的元素进行比较，如果小于堆顶的值，我们就将堆顶的值 poll 掉，并且将新的值添加进堆中（offer 代码在值添加进堆的时候，会对堆重新进行一次大根堆排列），以此类推下去，最后堆里面剩下的 k 个值就是我们要求的前 k 个最小值。 如果想求最大值的话，我们需要按此方式来对前 k 个元素创立小根堆。

    public void smallestk(int[] count,int k){for (int i = 0; i < k; i++) {offer(count[i]);}for (int i = k; i < count.length; i++) {int cur = peek();if (cur > count[i]){poll(0);offer(count[i]);}}}

测试：

        int[] count = {5,6,7,8,4,3,2,1};ret.smallestk(count,3);ret.printf();}

运行结果：  符合预期

关于 tops-k 问题，还有其余解法，例如通过冒泡排序来求前 k 个最小的值，通过建立小根堆，每次对堆顶的值进行记录并且 poll ，然后对余下的值继续排列小根堆，重复 k 次 也可以实现此问题。