最小堆、最大堆
参考: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;
}
}