数据结构快速插入/缺失与分类 [英] Data structure for fast insertion/deletion with sorting

问题描述

我拼命寻找一种数据结构，让我完成一个良好的数额插入的，几乎同样多的缺失（幅度大概相同的顺序）和最高（或最低的一个非常快速的查找，可以住在一起或者） 值。 缺失永远只会影响最大（或再次，最低）值。 问题是，这些值必须被排序，并在任何时刻，我可以插入打算在另外两个之间的任何点的元件。我想读（和删除）很快，在任意点的唯一值是最大（或，再次，最小值）。

I'm desperately looking for a data structure allowing me to perform a good amount of insertions, almost as many deletions (probably same order of magnitude) and a very quick lookup of the highest (or the lowest, can live with either) value. The deletion will always only affect the highest (or, again, lowest) value. The problem is that the values have to be sorted and at any moment I could insert an element going at any point between other two. The only value I want to read (and delete) quickly, at any point is the maximum (or, again, minimum).

你有什么建议？

请给算法的复杂性分析，你提出的答案。

Please give algorithmic complexity analysis for your proposed answers.

推荐答案

一个堆是你想要的。这里有一个简单的实现二进制堆。无论是最大堆或最小堆取决于你传递给它的比较功能：的 http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=789

A heap is what you want. Here's a simple implementation of a binary heap. Whether it's a max heap or min heap depends on the comparison function you pass to it: http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=789

请注意，一个二元堆是不建堆的唯一途径。但它可能是最容易构建，它执行不够好，在大多数情况下。

Note that a binary heap isn't the only way to build a heap. But it's likely the easiest to build, and it performs well enough in most situations.

在堆中的项目不排序，虽然他们订购。唯一的保证是，最高（最低）项目是在堆的顶部，当你问下一个项目将是一个检索。

The items in the heap are not sorted, although they're ordered. The only guarantee is that the highest (lowest) item is at the top of the heap and will be the one retrieved when you ask for the next item.

您正在构建的声音，像一个优先级队列。有实现优先级队列的其他方式。举例来说，我已经看到了跳过列表基于优先级的队列优于基于堆的优先级队列

What you're building sounds like a priority queue. There are other ways to implement a priority queue. For example, I've seen a skip list based priority queue that outperforms a heap-based priority queue.

如果你真的需要O（1）插入，然后寻找到类似的斐波那契堆

If you really need O(1) insertion, then look into something like the Fibonacci heap.

这篇关于数据结构快速插入/缺失与分类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！