1.简介
最小堆是一棵完全二叉树，非叶子结点的值不大于左孩子和右孩子的值。本文以图解的方式，说明最小堆的构建、插入、删除的过程。搞懂最小堆的相应知识后，最大堆与此类似。堆在优先级队列的各种实现中，是最高效的一种数据结构
假定在各个数据记录（或元素）中存在一个能够标识数据记录（或元素）的数据项，并将依据该数据项对数据进行组织，则可数据项成为关键码（key）
如果有一个关键码的集合K = {k0 , k1 , k2 , … , kn-1},把它的所有元素按完全二叉树的顺序存储存放在一个一维数组中。并且满足：
ki <= 2Ki+1 且 ki <= 2Ki+2 或者（ki >= 2Ki+1 且 ki >= 2Ki+2）i = 0 , 1 , … , [(n - 2) / 2]
则称这个集合为最小堆（或最大堆）
image.png
由于堆存储在下标从0开始计数的数组中，因此，在堆中给定下标为i的结点时：
如果 i = 0，结点 i 是根结点，无父结点；否则结点 i 的父结点为结点 [(i - 2) / 2] 向上取整
如果 2i + 1 > n - 1，则结点 i 无左子女；否则结点 i 的左子女为结点 2i + 1
如果 2i + 2 > n - 1，则结点 i 无右结点；否则结点 i 的右子女为结点 2i + 2
2.最小堆示例
image.png
3.最小堆的构建
初始数组为：9,3,7,6,5,1,10,2
按照完全二叉树，将数字依次填入。填入后，找到最后一个结点（本示例为数字2的节点），从它的父节点（本示例为数字6的节点）开始调整。根据性质，小的数字往上移动；至此，第1次调整完成。注意，被调整的节点，还有子节点的情况，需要递归进行调整。第二次调整，是数字6的节点数组下标小1的节点（比数字6的下标小1的节点是数字7的节点），用刚才的规则进行调整。以此类推，直到调整到根节点。
以下是本示例的图解：
image.png
image.png
image.png
image.png
注意：数字9的节点 将和 数字1的节点 发生对调，对调后，需要递归进行调整，请一定注意。
image.png
image.png
4.最小堆的元素插入
以上个最小堆为例，插入数字0。数字0的节点首先加入到该二叉树最后的一个节点，依据最小堆的定义，自底向上，递归调整。
以下是插入操作的图解：
image.png
image.png
image.png
image.png
5.最小堆的节点删除
对于最小堆和最大堆而言，删除是针对于根节点而言。对于删除操作，将二叉树的最后一个节点替换到根节点，然后自顶向下，递归调整。
以下是图解：
image.png
image.png
image.png
image.png
image.png
假如有一个父结点比两个子节点都要大，按照最小堆的话，就选择两个子结点中较小的与当前根结点进行交换
总结：根据最后的节点找父节点，开始第一次调整，之后变换调整的位置，并做递归判断，有右节点的需要找出左节点和右节点中最小的那个和父节点进行比较。
找父节点的方法： (数组最后的下标-1)/2 向下取整 或者 (数组最后的下标-2)/2 向上取整
<?php
$arr = [9,3,7,6,5,1,10,2];
$count = count($arr);//元素个数
$end_sign = $count-1;//最后下标
//最小堆排序 建堆 调整堆
//最初调整的位置
$start = floor(($end_sign-1)/2);
while($start>=0){
siftdown($start,$end_sign,$arr);
$start--;
}
siftinsert(0,$arr);
function siftdown($start,$end,&$arr){
$i = $start;
$j = 2*$i+1; //左节点
$tmp = $arr[$i]; //当前父节点值
while($j<=$end){
//判断是否有右节点 并且比左节点小 有则切换
if($j<$end && $arr[$j]>$arr[$j+1]){
$j=$j+1;
}
//判断左/右节点 与父节点值大小
if($tmp<=$arr[$j]){
break;
}else{
$arr[$i]=$arr[$j];
$i=$j;
$j=2*$j+1;
}
}
$arr[$i]=$tmp;
}
function siftinsert($value,&$arr){
array_push($arr,$value);
$count = count($arr);
$end_sign = $count-1; //插入元素所在的下标
$i=$end_sign; //操作插入元素位置
$j=floor(($i-1)/2); //其父节点
$tmp=$arr[$i]; //插入元素值
while($j>=0){
if($arr[$j]>$tmp){
$arr[$i]=$arr[$j];
$i=$j;
$j=floor(($i-1)/2);
}else{
break;
}
}
$arr[$i]=$tmp;
}
网友评论