瓷砖 中企动力 网站建设,广州开发区新兴产业投资基金管理有限公司,企业网站有哪些企业,什么网站可以用视频做背景1.大顶堆和小顶堆原理 什么是堆 堆#xff08;Heap#xff09;是计算机科学中一类特殊的数据结构#xff0c;通常是一个可以被看作一颗完全二叉树的数组对象。 完全二叉树 只有最下面两层节点的度可以小于2#xff0c;并且最下层的叶节点集中在靠左连续的边界 只允许最后…1.大顶堆和小顶堆原理 什么是堆 堆Heap是计算机科学中一类特殊的数据结构通常是一个可以被看作一颗完全二叉树的数组对象。 完全二叉树 只有最下面两层节点的度可以小于2并且最下层的叶节点集中在靠左连续的边界 只允许最后一层有空缺结点且空缺在右边完全二叉树需保证最后一个节点之前的节点都齐全 对任一结点如果其右子树的深度为j则其左子树的深度必为j或j1 什么是大顶堆最大堆 大顶堆是一种完全二叉树其每个父节点的值都大于或等于其子节点的值即根节点的值最大。每个节点的两个子节点顺序没做要求和之前的二叉查找树不一样。 什么是小顶堆最小堆 小顶堆是一种完全二叉树其每个父节点的值都小于或等于其子节点的值即根节点的值最小。 每个节点的两个子节点顺序没做要求和之前的二叉查找树不一样 存储原理 一般升序采用大顶堆降序采用小顶堆。堆是一种非线性结构用数组来存储完全二叉树是非常节省空间的把堆看作一个数组。 方便操作一般数组的下标0不存储直接从1节点存储。 堆其实就是利用完全二叉树的结构来维护一个数组数据下表为k的节点 左子节点下标为2*k的节点。右子节点就是下表为2*k1的节点。父节点就是下标为k/2取证的节点。 公式描述一下堆的定义 大顶堆arr[k] arr[2k1] arr[k] arr[2k]小顶堆arr[k] arr[2k1] arr[k] arr[ak] 小顶堆动画效果演示 往堆中插入新元素就是往数组中从索引0或1开始依次存放数据但是顺序需要满足堆的特性
如何让堆满足 不断比较新节点 arr[k]和对应父节点arr[k/2]的大小根据情况交互元素位置直到找到的父节点比当前新增节点大则结束 2.大顶堆构编码实现 大顶堆最大堆 大顶堆是一种完全二叉树其每个父节点的值都大于或等于其子节点的值即根节点的值最大 编码实现
public class Heap {//用数组存储堆中的元素private int[] items;//堆中元素的个数private int num;public Heap(int capacity) {//数组下标0不存储数据所以容量1this.items new int[capacity 1];this.num 0;}/*** 判断堆中 items[left] 元素是否小于 items[right] 的元素*/private boolean rightBig(int left, int right) {return items[left] items[right];}/*** 交换堆中的两个元素位置*/private void swap(int i, int j) {int temp items[i];items[i] items[j];items[j] temp;}/*** 往堆中插入一个元素默认是最后面num先执行然后进行上浮判断操作*/public void insert(int value) {items[num] value;up(num);}/*** 使用上浮操作新增元素后重新堆化* 不断比较新节点 arr[k]和对应父节点arr[k/2]的大小根据情况交互元素位置* 直到找到的父节点比当前新增节点大则结束* p* 数组中下标为 k 的节点* 左子节点下标为 2*k 的节点* 右子节点就是下标 为 2*k1 的节点* 父节点就是下标为 k/2 取整的节点*/private void up(int k) {//父节点 在数组的下标是1下标大于1都要比较while (k 1) {//比较 父结点 和 当前结点 大小if (rightBig(k / 2, k)) {//当前节点大则和父节点交互位置swap(k / 2, k);}// 往上一层比较当前节点变为父节点k k / 2;}}/*** 删除堆中最大的元素,返回这个最大元素*/public int delMax() {int max items[1];//交换索引 堆顶的元素数组索引1的和 最大索引处的元素放到完全二叉树中最右侧的元素方便后续变为临时根结点// 为啥不能直接删除顶部元素因为删除后会断裂成为森林所以需要先交互再删除swap(1, num);//最大索引处的元素删除掉, num--是后执行元素个数需要减少1items[num--] 0;//通过下浮调整堆重新堆化down(1);return max;}/*** 使用下沉操作堆顶和最后一个元素交换后重新堆化* 不断比较 节点 arr[k]和对应 左节点arr[2*k] 和 右节点arr[2*k1]的大小如果当前结点小则需要交换位置* 直到找到 最后一个索引节点比较完成 则结束* 数组中下标为 k 的节点* 左子节点下标为 2*k 的节点* 右子节点就是下标 为 2*k1 的节点* 父节点就是下标为 k/2 取整的节点*/private void down(int k) {//最后一个节点下标是numwhile (2 * k num) {//记录当前结点的左右子结点中较大的结点int maxIndex;if (2 * k 1 num) { //2 * k 1 num 是判断 确保有右节点//比较当前结点下的左右子节点哪个大if (rightBig(2 * k, 2 * k 1)) {maxIndex 2 * k 1;} else {maxIndex 2 * k;}} else {maxIndex 2 * k;}//比较当前结点 和 较大结点的值, 如果当前节点较大则结束if (items[k] items[maxIndex]) {break;} else {//否则往下一层比较当前节点k索引 变换为 子节点中较大的值swap(k, maxIndex);//变换k的值k maxIndex;}}}public static void main(String[] args) {Heap heap new Heap(20);heap.insert(42);heap.insert(48);heap.insert(93);heap.insert(21);heap.insert(90);heap.insert(9);heap.insert(3);heap.insert(40);heap.insert(32);int top;System.out.println(输出堆);while ((top heap.delMax()) ! 0) {System.out.print(top );}}
}
