最小堆、最大堆

参考：https://blog.csdn.net/hrn1216/article/details/51465270

https://blog.csdn.net/bbewx/article/details/24127779

最小堆：一颗完全二叉树，非叶子结点的值大于不大于左孩子和右孩子的值。

构建：先按照完全二叉树的方式将数字填入，然后从最后一个数字开始，每次对比自身与父节点，如果发生交换则往下递归。

插入：插入到最后一个元素，并按照最小堆的定义，自底向上递归调整。

删除：把该节点与根节点交换，并删除。然后按照最小堆的定义，对根节点自顶向下递归调整。

对于最小堆和最大堆而言，删除是针对于根节点而言。

代码：

定义基本操作：

public swap(int[] array, int i, int j) {  
 array[i] = array[i] + array[j];  
 array[j] = array[i] – array[j];  
 array[i] = array[i] – array[j];  
 }

最小堆插入：

public int[] addNumber(int[] array, int num) {  
 int len = array.length();  
 int[] newArray = new int[len + 1];  
 for (int i = 0; i < len; i++) {  
 newArray[i] = array[i];  
 }  
 newArray[len] = num;  
 int i = len – 1;  
 int j = (i – 1)/2;//j’s parent  
 while(j >= 0 && i >= 0) {  
 if (newArray[i] < newArray[j]) {  
 break;  
 }  
 swap(newArray, i, j);  
 i = j;  
 j = (i – 1)/2;  
 }  
 return newArray;  
 }

最小堆删除：

public int[] deleteNumber(int[] array, int length) {  
 swap(array, 0, length – 1);  
 int[] newArray = new int[length – 1];  
 for (int i = 0; i < len – 1; i++) {  
 newArray[i] = array[i];  
 }  
 int i = 0;  
 int j = (i + 1) * 2 – 1;  
 while(j < length – 1) {  
 if( j + 1 < length -1 && newArray[j] > newArray[j + 1]) {  
 j++;  
 }  
 if (newArray[i] > newArray[j]) {  
 swap(newArray, i, j)  
 }  
 i = j;  
 j = (i + 1) * 2 – 1;  
 }  
 }