大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
本篇内容主要讲解“编程中如何实现堆的插入和删除操作”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“编程中如何实现堆的插入和删除操作”吧!
咸阳ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联建站的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:028-86922220(备注:SSL证书合作)期待与您的合作!
//向最大堆中插入元素, heap:存放堆元素的数组 public static void insert(Listheap, int value) { //在数组的尾部添加 if(heap.size()==0) heap.add(0);//数组下标为0的位置不放元素 heap.add(value); //开始上升操作 // heapUp2(heap, heap.size() - 1); heapUp(heap, heap.size() - 1); } //上升,让插入的数和父节点的数值比较,当大于父节点的时候就和父节点的值相交换 public static void heapUp(List heap, int index) { //注意由于数值是从下标为1开始,当index = 1的时候,已经是根节点了 if (index > 1) { //求出父亲的节点 int parent = index / 2; //获取相应位置的数值 int parentValue = (Integer) heap.get(parent); int indexValue = (Integer) heap.get(index); //如果父亲节点比index的数值小,就交换二者的数值 if (parentValue < indexValue) { //交换数值 swap(heap, parent, index); //递归调用 heapUp(heap, parent); } } }
/** * 删除堆中位置是index处的节点 * 操作原理是:当删除节点的数值时,原来的位置就会出现一个孔 * 填充这个孔的方法就是,把最后的叶子的值赋给该孔,最后把该叶子删除 * @param heap */ public static void delete(Listheap,int index) { //把最后的一个叶子的数值赋值给index位置 heap.set(index, heap.get(heap.size() - 1)); //下沉操作 //heapDown2(heap, index); heapDown(heap, index); //把最后一个位置的数字删除 heap.remove(heap.size() - 1); } /** * 递归实现 * 删除堆中一个数据的时候,根据堆的性质,应该把相应的位置下移,才能保持住堆性质不变 * @param heap 保持堆元素的数组 * @param index 被删除的那个节点的位置 */ public static void heapDown(List heap, int index) { //因为第一个位置存储的是空值,不在考虑之内 int n = heap.size() - 2; //记录最大的那个儿子节点的位置 int child = -1; //2*index>n说明该节点没有左右儿子节点了,那么就返回 if (2 * index > n) { return; } //如果左右儿子都存在 else if (2 * index < n) { //定义左儿子节点 child = 2 * index; //如果左儿子小于右儿子的数值,取右儿子的下标 if ((Integer) heap.get(child) < (Integer) heap.get(child + 1)) { child++; } }//如果只有一个儿子(左儿子节点) else if (2 * index == n) { child = 2 * index; } if ((Integer) heap.get(child) > (Integer) heap.get(index)) { //交换堆中的child,和index位置的值 swap(heap, child, index); //完成交换后递归调用,继续下降 heapDown(heap, child); } }
到此,相信大家对“编程中如何实现堆的插入和删除操作”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!