最小堆、最大堆

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

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

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

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

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

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

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

0_131415207877s7

代码:

定义基本操作:

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;  
 }  
 }
comments powered by Disqus