一，二叉树的顺序存储(实现堆的必备知识)
1.存储方式
使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。
一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。
这种方式的主要用法就是堆的表示
2.下标关系（自己可以借助数组进行推导）
已知双亲(parent)的下标，则：
左孩子(left)下标 = 2 * parent + 1;
右孩子(right)下标 = 2 * parent + 2;
已知孩子（不区分左右）(child)下标，则：
双亲(parent)下标 = (child - 1) / 2;
二，堆
1.概念
- 堆逻辑上是一棵完全二叉树
- 堆物理上是保存在数组中
- 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆
- 反之，则是小堆，或者小根堆，或者最小堆
2.向下调整
前提：左右子树必须已经是一个堆，才能调整。
说明：
1.array 代表存储堆的数组
2. size 代表数组中被视为堆数据的个数
3. index 代表要调整位置的下标
4. parent 代表 父节点
5. child代表 孩子节点
过程（以建小堆为例）：
1.index指向父节点
2.通过父节点找到左子树的位置
3.找到当前父节点的左右子树中较小的与父节点交换
4.重复向下执行
代码:
//向下调整
//通过size指定array中哪些元素是有效的堆元素
//index表示从哪个位置的下标开始调整
//左右子树都是堆才能进行调整
public static void shiftDown(int[] array, int size,int index ){
int parent = index;
int child = 2 * parent + 1;//通过parent找到child的下标
while(child < size){
//比较左右子树找到较小值
if(child + 1 < size && array[child+1] < array[child] ){
child = child + 1;
}
//经过上面的比较已经不知道child是左子树，还是右子树了
//但是child下标一定对应左右子树中的较小值下标
//拿child位置元素与parent位置元素比较
if(array[child] < array[parent]){ //不符合就交换父子节点
int temp = array[child];
array[child] = array[parent];
array[parent] = temp;
} else {
//调整完毕，不需要再调整
break;
}
//更新parent和child节点，处理下一层数据
parent = child;
child = 2 * parent + 1;
}
}3.向上调整
说明
1.array 代表存储堆的数组
2. size 代表数组中被视为堆数据的个数
3. index 代表要调整位置的下标
4. parent 代表 父节点
5. child代表 孩子节点
过程：
1.index指向孩子节点，即刚开始要调整的位置元素
2.通过比较child与parent，如果不满足条件就交换位置
3.重复向上执行
代码：
private static void shiftUp(int[] array,int index){
int child = index;
int parent = (child - 1)/2;
while(child > 0){
if(array[parent] < array[child]){
//当前不符合大堆结构，就进行调整
int temp = array[parent];
array[parent] = array[child];
array[child] = temp;
} else{
break;//发现当前父节点比子节点大，这时说明整个数组已经符合堆的要求了
}
child = parent;
parent = (child-1)/2;
}
}4.建堆
此处以小堆为例（使用向下调整）
import java.util.Arrays;
public class Heap {
//向下调整
//通过size指定array中哪些元素是有效的堆元素
//index表示从哪个位置的下标开始调整
//左右子树都是堆才能进行调整
public static void shiftDown(int[] array, int size,int index ){
int parent = index;
int child = 2 * parent + 1;//通过parent找到child的下标
while(child < size){
//比较左右子树找到较小值
if(child + 1 < size && array[child+1] < array[child] ){
child = child + 1;
}
//经过上面的比较已经不知道child是左子树，还是右子树了
//但是child下标一定对应左右子树中的较小值下标
//拿child位置元素与parent位置元素比较
if(array[child] < array[parent]){ //不符合就交换父子节点
int temp = array[child];
array[child] = array[parent];
array[parent] = temp;
} else {
//调整完毕，不需要再调整
break;
}
//更新parent和child节点，处理下一层数据
parent = child;
child = 2 * parent + 1;
}
}
//建堆
public static void creatHeap(int[] array, int size){
for(int i = (size - 1 - 1)/2; i >= 0; i --){
shiftDown(array,size,i);
}
}
public static void main(String[] args) {
int[] array = {9,5,2,7,3,6,8};
creatHeap(array,array.length);
System.out.println(Arrays.toString(array));
}
}运行结果：
转载：https://blog.csdn.net/qq_45691220/article/details/105940703
查看评论