为了账号安全,请及时绑定邮箱和手机立即绑定

请教一个数据结构

/ 猿问

请教一个数据结构

ibeautiful 2018-11-21 05:02:40

<P>我向某个数据结构中随机加入以下一组3,1,4,5,数据,使得其排序为升序,</P> <P>如果我再加入一个数据2,该结构马上在内部排序为1,2,3,4,5,也就是说加入的数据,立刻找到自己的位置,</P> <P>以便于我在</P> <P>while(list.count!=0)</P> <P>{</P> <P>&nbsp;&nbsp;&nbsp; list[0]总是最小的数&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</P> <P>}</P> <P>感觉这个思路很糟糕,我的具体应用场景如下,在前面一贴,讨论过的合并数据问题,我想实现,</P> <P>当两个文件的大小(KB)小于某个设定值时,两个文件就合并,这样一直合并下去,</P> <P>因此我想到的策略是,取出文件的大小和文件名,按文件大小升序排列,将符合要求的文件合并,并将这些文件从队列中去除,加新生成的文件加入,这就要求有个自动的排序的要求了,</P> <P>&nbsp;</P> <P>高手来说说&nbsp;</P> <P>&nbsp;</P> <P>&nbsp;</P>

查看完整描述

2 回答

?
拉风的咖菲猫

1、如果只需要list[0]是最值点,堆就再好不过了,O(logN)的时间插入,实现也很简单,但是缺点就是只有list[0]是最值点。 2、如果需要每个元素都有序,只有线性表了,每次插入元素先二分查找,然后插入之,时间复杂度是O(logN+N) 如Gray Zhang朋友所说,SortedList可以达到第二种功能。 至于LZ的实例,我觉得可以这样实现: 将所有文件建立一个小顶堆(堆顶总是最小元素),和一个缓冲区; 设缓冲区里总文件大小是buffer,堆顶文件大小是top; 如果buffer + top <= max_file_size,就把top弹出到buffer,并且维护堆(下文中凡是涉及到堆的操作后都必须维护堆); 如果buffer + top > max_file_size,就把当前的buffer全部合并,然后压入堆; 知道buffer为空,且top > max_file_size的时候,说明合并完毕。 这里的堆就是优先队列 总体时间复杂度为O(N*logN)

查看完整回答
反对 2018-11-22
?
陪伴而非守候

最简单的数据结构就是插入排序,你可以看数据结构书中相关介绍。 或者用平衡二叉树,不过这种数据结构插入时调整非常耗时。 如果数据量不大,而且对效率要求不是特别高,最简单方法就是每次插入后 调用Array.Sort() 或者 list.Sort() 排下序。 如果数据量巨大,可以考虑采用B+树,大型数据库系统一般都采用这种 数据结构或其变种构建索引。

查看完整回答
反对 2018-11-22
  • 2 回答
  • 0 关注
  • 281 浏览

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信