周围有一些数据结构非常有用，但大多数程序员都不知道。他们是哪一个？
每个人都知道链表、二叉树和散列，但比如Skip列表和Bloom过滤器。我想知道更多不太常见但值得了解的数据结构，因为它们依赖于伟大的想法，丰富了程序员的工具箱。
PS：我还对舞蹈链接等技术感兴趣，这些技术巧妙地利用了通用数据结构的财产。
编辑：请尝试包含更详细描述数据结构的页面链接。此外，试着补充几句关于数据结构为什么很酷的话（正如乔纳斯·Kölker已经指出的那样）。此外，尝试为每个答案提供一个数据结构。这将允许更好的数据结构仅根据其投票结果浮到顶部。
当前回答
Gerth Stølting Brodal和Chris Okasaki的自助倾斜二项式堆：
尽管它们的名字很长，但即使在函数设置中，它们也提供了渐近最优的堆操作。
O（1）尺寸，接头，插入件，最小值O（log n）删除最小值
注意，union需要O（1）而不是O（log n）时间，这与数据结构教科书中通常包含的更为知名的堆（如左派堆）不同。与斐波那契堆不同，这些渐近线是最坏的情况，而不是摊销，即使持续使用！
Haskell中有多种实现。
在Brodal提出了一个具有相同渐近线的命令堆之后，它们由Brodal和Okasaki共同导出。
其他回答
任何有3D渲染经验的人都应该熟悉BSP树。通常，这是一种通过构造3D场景来进行渲染的方法，该方法可以在知道相机坐标和方位的情况下进行管理。
二进制空间分区（BSP）是一种递归细分a的方法通过超平面将空间划分为凸集。该细分产生通过方法表示场景树数据结构的BSP树。换句话说，这是一种方法形状复杂的破碎多边形转化为凸集，或更小多边形完全由非反射角（小于180°). 更一般的描述空间分区，请参见空间分区。最初，提出了这种方法在3D计算机图形方面渲染效率。其他一些应用程序包括执行具有形状的几何操作（构造实体几何），机器人和3D中的碰撞检测计算机游戏和其他计算机涉及处理的应用程序复杂的空间场景。
PATRICIA-检索字母数字编码信息的实用算法，D.R.Morrison（1968）。
PATRICIA树与Trie相关。Tries的问题是，当密钥集稀疏时，即当实际密钥形成潜在密钥集的一个子集时，Trie中的许多（大多数）内部节点只有一个后代，这是非常常见的情况。这导致Trie具有较高的空间复杂性。
http://www.csse.monash.edu.au/~合金/瓷砖AlgdS/树/PATRICIA/
空间索引，特别是R-树和KD树，有效地存储空间数据。它们适用于地理地图坐标数据和VLSI位置和路线算法，有时也适用于最近邻搜索。
位阵列紧凑地存储单个位，并允许快速位操作。
二进制决策图是我最喜欢的数据结构之一，或者实际上是降序二进制决策图（ROBDD）。
例如，此类结构可用于：
表示项目集合并对这些集合执行非常快速的逻辑运算。任何布尔表达式，旨在查找表达式的所有解
注意，许多问题可以用布尔表达式表示。例如，suduku的解可以表示为布尔表达式。为该布尔表达式构建BDD将立即生成解决方案。
远离所有这些图形结构，我只喜欢简单的环形缓冲区。
如果实施得当，您可以在保持性能的同时，甚至可以提高性能，从而大大减少内存占用。
