我想实现能够快速插入并在每次插入后保持数据排序而不重复的数据结构。
我考虑过二项式堆，但我对该结构的理解是，在插入过程中它无法判断特定元素是否还在堆中。另一方面，有 AVL 树，它非常适合我的情况，但老实说，当时对我来说实施起来太难了。
所以我的问题是：是否有可能编辑二项式堆插入算法以跳过重复项？也许任何人都可以建议另一种结构？
问候:)
问问题
847 次
5 回答
2
在 C++ 中，有std::set. 它在内部是红黑树的实现。因此，它会在您输入数据时进行排序。您可以查看它以供参考。
于 2015-06-27T12:26:56.760 回答
1
O(log(n))一个很好的数据结构是用于插入的红黑树。你说你想实现一个数据结构来做到这一点。这里给出了如何实现的一个很好的解释，以及一个开源可用的库。
于 2015-06-27T15:19:44.117 回答
0
如果您关心线程安全，也可以使用跳过列表。在这种情况下，平衡二叉搜索树的性能将比跳跃列表更差，因为跳跃列表不需要重新平衡，并且跳跃列表本身也像 BST 一样排序。所需的内存量有一个缺点（因为在技术上使用了多个链表），但从理论上讲它很合适。
您可以在本教程中阅读有关跳过列表的更多信息。
如果您有大量元素，您也可以考虑只使用双向链表并在插入所有项目后对列表进行排序。这具有易于实现和插入时间的好处。
然后，您需要实现排序算法。选择排序或插入排序比归并排序、堆排序或快速排序算法更慢但更容易实现。另一方面，后三个实施起来也不是很困难。唯一需要注意的是不要溢出堆栈，因为这些算法通常是使用递归实现的。您可以创建自己的堆栈实现（不难）并迭代地实现它们，根据需要将值推送和弹出到您的堆栈中。有关我所指的示例，请参阅迭代快速排序。
于 2015-06-27T14:18:58.170 回答
0
如果您可以使用库，您可以查看 libavl Here 该库还实现了一些其他种类的二叉树。
于 2015-06-27T15:09:34.993 回答
-1
如果您正在寻找快速插入和简单的实现，为什么不使用链表（单或双）。 插入：推头/推尾 - O(1) 移除：弹出头/弹出尾 - O(1) 唯一的但“查找”将在 O(n) 中
于 2015-06-27T13:19:49.950 回答