Met*_*est 0 c sorting data-structures
可能重复: 如何在添加数据时对数据进行排序,而不是以后？
我需要动态排序数据.基本上我有一个数组将插入元素.每次插入后,都应对数据进行排序.实现这一目标的最快方法是什么？
Fre*_*Foo 6
实现此目的的最快方法是删除数组并使用二叉搜索树代替O(lg n)排序插入.使用数组时,由于需要平均移动n/2个元素,因此总是会遇到线性时间插入问题.
编辑:您也可以使用堆而不是BST; 可以用数组实现.但是,对于二进制堆,迭代将花费O(n lg n),而在线程BST中,可以在O(n)时间内使用O(1)额外内存完成迭代.
归档时间：
13 年，10 月 前
查看次数：
1086 次
最近记录：