1免费建站网站,想做电商从哪里入手,广州代理记账,宁波网络推广优化什么是最小堆#xff1a; 堆是一种二叉树#xff0c;最小堆中所有父亲节点的值都要比自己的子节点的值要小。而根节点称为堆顶。根据定义我们可以得到堆中最小元素就在堆顶。#xff08;节点左上角是编号#xff0c;内部是元素值#xff09; 假设该图中的堆顶元素是24呢 堆是一种二叉树最小堆中所有父亲节点的值都要比自己的子节点的值要小。而根节点称为堆顶。根据定义我们可以得到堆中最小元素就在堆顶。节点左上角是编号内部是元素值 假设该图中的堆顶元素是24呢显然不符合最小堆的定义那么我们要怎么处理呢 假设7号节点的值是1呢显然不符合最小堆的定义那么我们要怎么处理呢 如何调整堆 在该图中我们先让 24 与左孩子的值比较发现 左孩子比自己小再看右孩子发现右孩子比左孩子还小于是1号节点值和3号节点值交换。然后再看3号节点的左孩子和右孩子值都比 24 小但是6号节点值更小所以3号节点值24和6号节点值交换完成最小堆的向下调整。 该图我们先让7号节点与3号节点比较发现5 比 1大 然后交换两个节点的值3号节点再和1号节点比较发现2比1大然后交换节点的值完成了最小堆的向上调整。 如果忘记了怎么存储二叉树参考这篇博文树------二叉树-CSDN博客 具体代码
void down(int i)//i为需要调整的节点编号。 { int t, flag 0; while (2 * i n flag 0)//判断当前节点是否有左子树。 { if (arr[i] arr[2 * i]) t 2 * i; else t i;//如果左子树比本节点小记录该节点下标否则记录该节点下标。 if (2 * i 1 n)//如果有右子树。 if (arr[2 * i 1] arr[t]) t 2 * i 1;//确定最终交换值的节点下标。 if (t ! i) { swap(i, t); i t; }//如果最终交换值的下标不等于本节点证明需要交换值。 else flag 1;//如果没有交换证明本节点调整完毕退出循环。 } } void up(int i)//向上调整函数。 { int flag 0; if (i 1)//如果已经在堆顶不需要调整。 return; while (i ! 1 flag 0) { if (arr[i] arr[i / 2]) swap(i, i / 2);//如果本节点小于父亲节点交换值负责退出循环。 else flag 1; i / 2;//节点编号调整为父亲节点。 } } void swap(int i, int j) { int k arr[i]; arr[i] arr[j]; arr[j] k; }//交换函数。 注意点 最大堆和最小堆差不多最大堆定义是任何父亲节点都要比子节点要大至于如何调整可以改变以上代码的大小判断符号。 另外关于昨天的 Bellman-Ford算法的优化的答案博文因为某些原因今天无法更新其实是我忘记写了。。。。。。明天再为大家呈上。该算法博文链接如下。 图论------贝尔曼-福德Bellman-Ford算法-CSDN博客
