先进的数据结构在实践中
在编程的10年中，我可以统计一下我使用的数据结构的数量：数组，链表（我正在堆栈和排队）和字典。 考虑到几乎所有我写的应用程序都属于数据格式/ CRUD类别，这并不奇怪。
我从来不需要使用过去50年来研究过的红黑树，跳过列表，双端队列，循环链表，优先级队列，堆，图或任何几十种奇特的数据结构。 我觉得我错过了。
这是一个开放式的问题，但在实践中这些“异国情调”的数据结构在哪里？ 有没有人有使用这些数据结构来解决特定问题的实际经验？
一些例子。 他们含糊不清，因为他们是为雇主工作的：
获得前N名的堆会导致Google风格的搜索。 （从索引中的候选人开始，通过线性遍历它们，筛选出最大大小为N的最小堆）。这是一个图像搜索原型。
布隆过滤器将某些数据的大小减少到了几百万用户看到的数量，这些数据适合现有的服务器（为了提高速度，这些数据都必须在RAM中）; 原来的设计将需要许多新的服务器，仅用于该数据库。
三角形阵列表示将推荐引擎的密集对称阵列的大小减半（出于同样的原因再次使用RAM）。
用户必须根据某些关联进行分组; union-find使得这个过程简单，快速，准确，而不是慢，哈克和近似。
根据附近人们驾车时间选择零售网站的应用程序使用Dijkstra最短路径和优先级队列。 其他GIS工作利用了四叉树和Morton索引。
了解数据结构中的内容 - 土地派上用场 - “实验室中的数周可以为您节省数小时的时间”。 bloom-filter案例仅仅因为规模而值得：如果问题出现在创业公司而不是雅虎公司，那么我会使用一个普通的旧hashtable。 我认为其他的例子在任何地方都是合理的（尽管现在你不太可能自己编写它们）。
B树在数据库中。
R树是用于地理搜索的（例如，如果我有10000个形状，每个形状都有一个围绕二维平面散布的边界框，这些形状中的哪一个与任意边界框B相交？）
C ++ STL中的形式的deques是可生成的向量（比链表更具有内存效率，并且可以在中间不断查看任意元素）。 据我所知，我从来没有完全使用过双端队列（从两端插入/删除），但它足够普遍，您可以将它用作堆栈（从一端插入/删除）或队列（插入到另一端，从另一端删除），并且具有高性能访问权限以查看中间的任意元素。
我刚读完Java泛型和集合 - “泛型”部分伤了我的头，但集合部分是有用的，他们指出了跳过列表和树之间的一些区别（都可以实现地图/集合）：skip列表为您提供了从一个元素到下一个元素的内置恒定时间迭代（树是O（log n）），并且在多线程情况下实现无锁算法非常简单。
优先级队列用于调度等（这里是简要讨论应用程序的网页）; 堆通常用于实现它们。 我也发现堆（至少对我来说）是O（n log n）类中最容易理解和实现的。
他们经常在图书馆的幕后使用。 例如，一个有序的字典数据结构（即一个关联数组，它允许按键遍历遍历）很可能不会使用红黑树实现。
许多数据结构（浮现树想到的）在某些情况下（在张开树的情况下是参考的时间局部性）对于它们的最佳行为是有趣的，因此它们主要与在这些情况下使用有关。 在大多数情况下，对这些数据结构的实际操作知识的真正好处是能够在合理的情况下在合理理解其行为的情况下使用它们。
以分拣为例，例如：
在大多数情况下，快速排序或修改后的快速排序在单个段足够小时会降至另一种方法，通常是大多数情况下最快的排序算法。 但是，快速排序往往会在近似排序的数据上显示不理想的行为。
堆排序的主要优点在于它可以在最小的中间存储空间内就地完成，这使它非常适合在内存受限的系统中使用。 虽然它平均速度较慢（尽管仍然是log（n）），但它不会受到quicksort糟糕的最坏情况性能的影响。
第三个例子是合并排序，它可以顺序完成，使它成为排序比主内存大得多的数据集的最佳选择。 另一个名称是'外部排序'，这意味着您可以使用外部存储（磁盘或磁带）对中间结果进行排序。