- 浏览: 33464 次
- 性别:
- 来自: 北京
最新评论
-
cjf068:
LuckYes 写道楼主如果用最小堆的话,最好用调整堆的方式来 ...
求最小的k个数问题 -
LuckYes:
楼主如果用最小堆的话,最好用调整堆的方式来构建堆,这样效率更高 ...
求最小的k个数问题 -
cjf068:
这个算法的基本思路, ...
大数乘法 -
liujunsong:
这个算法的基本思路,是小学3年级的 算法,就是简单的把乘法运算 ...
大数乘法 -
shuidexiongdi:
去年我也写了一个http://shuidexiongdi.it ...
大数乘法
固定容量的二叉堆实现,可用于快速求top k 问题。如要求一个数组中top k的元素,则建立一个容量为k的大根堆,一次遍历数组add进该堆,遍历完毕,堆中的元素即为top k的所有元素。
固定容量大根堆代码
固定长度小根堆代码
固定容量大根堆代码
package org.jf.alg; public class BigHeadFixedBinHeap <T extends Comparable> { private Object array[]; private int current_size = 0; public BigHeadFixedBinHeap(int size) { array = new Object[size+1]; } /** * 往堆中添加一个元素 * *分两种情况: *1.当前堆未满,直接添加到末尾,回溯保持堆性质 *2.当前堆已满,则找出最后一层中最大元素并与当前元素比较,若当前元素小,则替换,否则什么也不做 * * @param data */ public void add(T data) { int comp_begin = current_size/2+1;//求最小值的起始位置 int indx = 1;//记录当前新插入的元素索引 if(current_size<array.length-1)//堆未满 直接将新元素插入末尾 { array[++current_size]=data; indx = current_size; } else//堆已满 查找最后一层中的最大值 { int min_indx = comp_begin; T min = (T) array[min_indx]; int i=comp_begin; while(i<array.length) { if(min.compareTo((T)array[i])>0) { min_indx = i; min = (T) array[min_indx]; } i++; } if(min.compareTo(data)<0) { indx = min_indx; array[indx] = data;//当前的最小值被删除了 } else { indx = 1;//不替换 } } //向上检测 while(indx>1) { //当前元素与其父节点比较 若小,则交换 indx = indx/2 //否则 break int pdx = indx/2; if(((T)array[indx]).compareTo(((T)array[pdx]))>0) { Object tmp = array[indx]; array[indx] = array[pdx]; array[pdx]=tmp; indx = pdx; }else { break; } } } /** * 删除堆顶元素 * 删除堆顶,用最后一个元素代替堆顶,向下检测保持堆性质 * * @return */ public T remove() { T data = null; if(current_size==0) return null; data = (T) array[1]; array[1] = array[current_size]; array[current_size] = null; current_size -- ; //根节点与左右子节点中最小元素交换 int indx = 1; int min_indx =indx; Object tmp = null; while((min_indx=getMaxIndx(indx))!=indx) { //indx 与 min_indx元素交换 tmp = array[indx]; array[indx]=array[min_indx]; array[min_indx]=tmp; indx = min_indx; } return data; } private int getMaxIndx(int indx) { T left = null; T right = null; if(indx*2>this.current_size)//没有子节点 return indx; if(indx*2==this.current_size) left = (T)array[indx*2]; else { left = (T)array[indx*2]; right =(T)array[indx*2+1]; } if(right==null) { if(left.compareTo((T)array[indx])>0) indx = indx*2; }else { if(left.compareTo((T)array[indx])>0) { indx = indx*2; if(right.compareTo((T)array[indx])>0) indx = indx+1; } else if(right.compareTo((T)array[indx])>0) { indx = indx*2+1; } } return indx; } public T peek() { if(this.current_size>0) return (T) array[1]; return null; } public int capacity() { return array.length-1; } void printArray() { for(int i=1;i<=this.current_size;i++) { System.out.print(array[i].toString()+" "); } System.out.println("\n"); } public Object [] getAll() { Object[] newArray = new Object[this.current_size]; System.arraycopy(array, 1, newArray, 0, current_size); return newArray; } }
固定长度小根堆代码
package org.jf.alg; /** * 定长小根堆 * 数组存储,数组第一个元素留空 * * 第k个元素的左儿子为 a[2k],右儿子为a[2k+1] * * 第k个元素的父节点为a[k/2] * * k从1记起 * * @author chenjf * * */ public class LittleHeadFixedBinHeap<T extends Comparable> { private Object array[]; private int current_size = 0; /** * * @param size 堆大小 */ public LittleHeadFixedBinHeap(int size) { array = new Object[size+1]; } /** * 往堆中添加一个元素 * *分两种情况: *1.当前堆未满,直接添加到末尾,回溯保持堆性质 *2.当前堆已满,则找出最后一层中最大元素并与当前元素比较,若当前元素小,则替换,否则什么也不做 * * @param data */ public void add(T data) { int comp_begin = current_size/2+1;//求最大值的起始位置 int indx = 1;//记录当前新插入的元素索引 if(current_size<array.length-1)//堆未满 直接将新元素插入末尾 { array[++current_size]=data; indx = current_size; } else//堆已满 查找最后一层中的最大值 { int max_indx = comp_begin; T max = (T) array[max_indx]; int i=comp_begin; while(i<array.length) { if(max.compareTo((T)array[i])<0) { max_indx = i; max = (T) array[max_indx]; } i++; } if(max.compareTo(data)>0) { indx = max_indx; array[indx] = data;//当前的最大值被删除了 } else { indx = 1;//不替换 } } //向上检测 while(indx>1) { //当前元素与其父节点比较 若小,则交换 indx = indx/2 //否则 break int pdx = indx/2; if(((T)array[indx]).compareTo(((T)array[pdx]))<0) { Object tmp = array[indx]; array[indx] = array[pdx]; array[pdx]=tmp; indx = pdx; }else { break; } } } /** * 删除堆顶元素 * 删除堆顶,用最后一个元素代替堆顶,向下检测保持堆性质 * * @return */ public T remove() { T data = null; if(current_size==0) return null; data = (T) array[1]; array[1] = array[current_size]; array[current_size] = null; current_size -- ; //根节点与左右子节点中最小元素交换 int indx = 1; int min_indx =indx; Object tmp = null; while((min_indx=getMinIndx(indx))!=indx) { //indx 与 min_indx元素交换 tmp = array[indx]; array[indx]=array[min_indx]; array[min_indx]=tmp; indx = min_indx; } return data; } private int getMinIndx(int indx) { T left = null; T right = null; if(indx*2>this.current_size)//没有子节点 return indx; if(indx*2==this.current_size) left = (T)array[indx*2]; else { left = (T)array[indx*2]; right =(T)array[indx*2+1]; } if(right==null) { if(left.compareTo((T)array[indx])<0) indx = indx*2; }else { if(left.compareTo((T)array[indx])<0) { indx = indx*2; if(right.compareTo((T)array[indx])<0) indx = indx+1; } else if(right.compareTo((T)array[indx])<0) { indx = indx*2+1; } } return indx; } public T peek() { if(this.current_size>0) return (T) array[1]; return null; } public int capacity() { return array.length-1; } void printArray() { for(int i=1;i<=this.current_size;i++) { System.out.print(array[i].toString()+" "); } System.out.println("\n"); } public Object [] getAll() { Object[] newArray = new Object[this.current_size]; System.arraycopy(array, 1, newArray, 0, current_size); return newArray; } }
发表评论
-
中文数字到阿拉伯数字转换
2012-04-24 10:18 1849昨天博客上看到一童鞋 ... -
布隆过滤器
2012-04-23 15:39 925package org.jf.alg; import ... -
基本的排序算法
2012-04-21 21:07 713插入排序 选择排序 快速排序 。。。。 后续补充 pack ... -
日期计算
2012-04-19 23:04 833简单日期计算类: 日期大小比较 日期之间天数计算 pack ... -
判断数组中是否存在两个元素之和等于给定数值
2012-04-06 22:58 1951已知int数组a按升序排列,要求用线性时间复杂的算法,判断是否 ... -
求最大子数组之和
2012-04-06 22:51 1275求最大子数组之和的线性解法:本算法受编程珠玑中提示而得 /** ... -
LRUCache
2012-03-15 14:35 1577MyLRUCache 缓存类 package org.jf ... -
求变位词组合
2012-03-13 22:53 824public class CharComp { ... -
计算24点
2012-03-13 21:49 1193计算n个数的全排列 package org.jf.alg. ... -
表达式计算
2012-03-10 23:02 876中缀表达式转后缀 后缀表达式计算 支持整型 分数计算,只支持 ... -
Many2One缓冲
2012-03-06 12:35 903多线程并发操作中,为了尽量减少同步锁的开销,一般都会尽可能减少 ... -
红黑树
2012-03-03 21:47 1178红黑树 规则 * 1.每个 ... -
行文件分组统计
2012-03-02 22:57 806有些情况下,对于一个结构化的以行为记录的文本文件,需要按列分组 ... -
简单LRU缓存实现
2012-02-09 21:12 1053链表保存键值,由于没有权值策略,简单的将当前访问过的节点放到链 ... -
大根堆
2012-02-08 22:23 1390大根堆,可用于优先级队列 package org.jf.a ... -
大数乘法
2012-02-07 00:16 2820论坛看到的一个面试题,实现任意大整数字符串相乘,返回结果字符串 ...
相关推荐
个人实现的最小权重的二叉堆实现,效率很高,适合任意场合下的临时列表排序。 直接执行该文件会执行文件中的测试样例 使用时在头部如此声明 ...bh = BinaryHeap(heap_size) # heap_size为容量,bh为二叉堆对象
二叉堆(最小堆)+二项堆+斐波那契堆 根基算法导论C++实现
c++实现的二叉堆,很好的编程规范,可以学到模板、inline函数、引用的实际应用。代码写的很简洁
二叉堆的C++实现,包含二叉堆的构造,插入,删除,销毁等操作
PHP对于二叉堆的操作,以及个人的理解,可进行插入、删除操作等
易语言二叉堆源码,二叉堆,加入二叉,减出二叉,寻找数值
由两部分组成,my_map.cpp用OpenCV实现读取地图等图像处理操作,main.cpp实现A*算法。二叉堆为类,格子为结构体。生成结果后进行优化,使原本只能走8个方向的结果优化为任意角度和方向,也就是真正的全局最短路径。
个人实现的最小权重的二叉堆实现,效率很高,适合任意场合下的临时列表排序。 可在外部写脚本对该文件进行测试 需要继承Tuple类实现排序对象类型,并实现Tuple的抽象方法weight()来反映排序对象权重
dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告
使用c++实现最小堆。提供常见操作,如堆化数组,插入,删除,堆排序,遍历堆。
4.binaryHeap 二叉堆 支持排序,父子之间只有一种大小关系。孩子大于父,或者小于父。 二叉堆不支持合并。 实现了各种增删查改算法。
基于二叉堆的AStar算法演示程序,简单高效。使用VS2010+MFC演示,算法与平台无关,可以任意使用。
本人做的一个二叉堆的课件,附带STL中的priority_queue
C# 二叉堆 压出最小值比较快
使用C++实现了A星算法,使用二叉堆优化。仅供新手学习。
使用c++实现最大堆。提供常见操作,如插入、删除、堆化数组、堆排序、上下调整、向下调整。
本源代码借助标准C++ STL中的vector,list和heap等已封装的数据结构,优化了A星算法搜索地图、检索开始列表过程,减小了程序的时间和空间花费。经检验,检索20000*20000的随机障碍物地图时,程序在规划路径部分的平均...
二叉堆的相关代码.zip二叉堆的学习与思考
二叉堆、并查集和树状数组 刘汝佳 绝对经典巧妙的讲解和解答
二叉堆的概念及其应用,里面包含果子合并、堆排序、鱼塘钓鱼、最小函数值、Sequence等重要题型的详细解析