What are the lesser known but useful data structures

Question

There are some data structures around that are really useful but are unknown to most programmers  Which ones are they   Everybody knows about linked lists  binary trees  and hashes  but what about Skip lists and Bloom filters for example  I would like to know more data structures that are not so common  but are worth knowing because they rely on great ideas and enrich a programmer s tool box   PS  I am also interested in techniques like Dancing links which make clever use of properties of a common data structure    EDIT  Please try to include links to pages describing the data structures in more detail  Also  try to add a couple of words on why a data structure is cool  as Jonas K  lker already pointed out    Also  try to provide one data-structure per answer  This will allow the better data structures to float to the top based on their votes alone

User · Answer

Disjoint Set Forests allow fast membership queries and union operations and are most famously used in Kruskal's Algorithm for minimum spanning trees.

The really cool thing is that both operations have amortized running time proportional to the inverse of the Ackermann Function, making this the "fastest" non-constant time data structure.

User · Answer

Splay Trees are cool  They reorder themselves in a way that moves the most often queried elements closer to the root

User · Answer

Counted unsorted balanced btrees   Perfect for text editor buffers   http   www chiark greenend org uk  sgtatham algorithms cbtree html

User · Answer

lt zvrba gt  Van Emde-Boas trees   I think it d be useful to know why they re cool   In general  the question  why  is the most important to ask     My answer is that they give you O log log n  dictionaries with  1  n  keys  independent of how many of the keys are in use   Just like repeated halving gives you O log n   repeated sqrting gives you O log log n   which is what happens in the vEB tree

User · Answer

Tries  also known as prefix-trees or crit-bit trees  have existed for over 40 years but are still relatively unknown   A very cool use of tries is described in  TRASH - A dynamic LC-trie and hash data structure   which combines a trie with a hash function

User · Answer

Binomial heap s have a lot of interesting properties  most useful of which is merging

User · Answer

Bootstrapped skew-binomial heaps by Gerth St  lting Brodal and Chris Okasaki   Despite their long name  they provide asymptotically optimal heap operations  even in a function setting     O 1  size  union  insert  minimum O log n  deleteMin    Note that union takes O 1  rather than O log n  time unlike the more well-known heaps that are commonly covered in data structure textbooks  such as leftist heaps  And unlike Fibonacci heaps  those asymptotics are worst-case  rather than amortized  even if used persistently   There are multiple implementations in Haskell    They were jointly derived by Brodal and Okasaki  after Brodal came up with an imperative heap with the same asymptotics

User · Answer

I think Disjoint Set is pretty nifty for cases when you need to divide a bunch of items into distinct sets and query membership   Good implementation of the Union and Find operations result in amortized costs that are effectively constant  inverse of Ackermnan s Function  if I recall my data structures class correctly

User · Answer

A corner-stitched data structure   From the summary      Corner stitching is a technique for   representing rectangular   two-dimensional objects  It appears to   be especially well-suited for   interactive editing systems for VLSI   layouts  The data structure has two   important features  first  empty space   is represented explicitly  and second    rectangular areas are stitched   together at their corners like a   patchwork quilt  This organization   results in fast algorithms  linear   time or better  for searching    creation  deletion  stretching  and   compaction  The algorithms are   presented under a simplified model of   VLSI circuits  and the storage   requirements of the structure are   discussed  Measurements indicate that   corner stitching requires   approximately three times as much   memory space as the simplest possible   representation

User · Answer

Burrows   Wheeler transform  block-sorting compression   Its essential algorithm for compression  Let say that you want to compress lines on text files  You would say that if you sort the lines  you lost information  But BWT works like this - it reduces entropy a lot by sorting input  keeping integer indexes to recover the original order

User · Answer

Bloom filter  Bit array of m bits  initially all set to 0    To add an item you run it through k hash functions that will give you k indices in the array which you then set to 1    To check if an item is in the set  compute the k indices and check if they are all set to 1    Of course  this gives some probability of false-positives  according to wikipedia it s about 0 61  m n  where n is the number of inserted items   False-negatives are not possible   Removing an item is impossible  but you can implement counting bloom filter  represented by array of ints and increment decrement

User · Answer

Splay Trees are cool  They reorder themselves in a way that moves the most often queried elements closer to the root

User · Answer

Environment tracking recursive structures      Compilers use a structure that is recursive but not like a tree   Inner scopes have a pointer to an enclosing scope so the nesting is inside-out   Verifying whether a variable is in scope is a recursive call from the inside scope to the enclosing scope   public class Env           HashMap lt String  Object gt  map      Env                     outer       Env                 outer   null          map   new HashMap               Env Env o                outer   o          map   new HashMap               void put String key  Object value                map put key  value              Object get String key                if  map containsKey key                         return map get key                     if  outer    null                        return outer get key                     return null             Env push                 return new Env this              Env pop                 return outer            I m not sure if this structure even has a name   I call it an inside-out list

User · Answer

PQ-Trees

User · Answer

Splash Tables are great   They re like a normal hash table  except they guarantee constant-time lookup and can handle 90  utilization without losing performance   They re a generalization of the Cuckoo Hash  also a great data structure    They do appear to be patented  but as with most pure software patents I wouldn t worry too much

User · Answer

I sometimes use Inversion LIsts to store ranges  and they are often used to store character classes in regular expressions  See for example http   www ibm com developerworks linux library l-cpinv html  Another nice use case is for weighted random decisions  Suppose you have a list of symbols and associated probabilites  and you want to pick them at random according to these probabilities      a    0 1    b    0 5    c    0 4   Then you do a running sum of all the probabilities       0 1  0 6  1 0    This is your inversion list  You generate a random number between 0 and 1  and find the index of the next higher entry in the list  You can do that with a binary search  because it s sorted  Once you ve got the index  you can look up the symbol in the original list   If you have n symbols  you have O n  preparation time  and then O log n   acess time for each randomly chosen symbol - independently of the distribution of weights   A variation of inversion lists uses negative numbers to indicate the endpoint of ranges  which makes it easy to count how many ranges overlap at a certain point  See http   www perlmonks org index pl node id 841368 for an example

User · Answer

PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric  D R Morrison  1968    A PATRICIA tree is related to a Trie  The problem with Tries is that when the set of keys is sparse  i e  when the actual keys form a small subset of the set of potential keys  as is very often the case  many  most  of the internal nodes in the Trie have only one descendant  This causes the Trie to have a high space-complexity   http   www csse monash edu au  lloyd tildeAlgDS Tree PATRICIA

User · Answer

Here are a few    Suffix tries   Useful for almost all kinds of string searching  http   en wikipedia org wiki Suffix trie Functionality    See also suffix arrays  they re not quite as fast as suffix trees  but a whole lot smaller  Splay trees  as mentioned above    The reason they are cool is threefold    They are small  you only need the left and right pointers like you do in any binary tree  no node-color or size information needs to be stored  They are  comparatively  very easy to implement They offer optimal amortized complexity for a whole host of  measurement criteria   log n lookup time being the one everybody knows    See http   en wikipedia org wiki Splay tree Performance theorems  Heap-ordered search trees  you store a bunch of  key  prio  pairs in a tree  such that it s a search tree with respect to the keys  and heap-ordered with respect to the priorities   One can show that such a tree has a unique shape  and it s not always fully packed up-and-to-the-left    With random priorities  it gives you expected O log n  search time  IIRC  A niche one is adjacency lists for undirected planar graphs with O 1  neighbour queries   This is not so much a data structure as a particular way to organize an existing data structure   Here s how you do it  every planar graph has a node with degree at most 6   Pick such a node  put its neighbors in its neighbor list  remove it from the graph  and recurse until the graph is empty   When given a pair  u  v   look for u in v s neighbor list and for v in u s neighbor list   Both have size at most 6  so this is O 1     By the above algorithm  if u and v are neighbors  you won t have both u in v s list and v in u s list   If you need this  just add each node s missing neighbors to that node s neighbor list  but store how much of the neighbor list you need to look through for fast lookup

User · Answer

Pairing heaps are a type of heap data structure with relatively simple implementation and excellent practical amortized performance

User · Answer

Fenwick Tree  It s a data structure to keep count of the sum of all elements in a vector  between two given subindexes i and j  The trivial solution  precalculating the sum since the begining doesn t allow to update a item  you have to do O n  work to keep up    Fenwick Trees allow you to update and query in O log n   and how it works is really cool and simple  It s really well explained in Fenwick s original paper  freely available here   http   www cs ubc ca local reading proceedings spe91-95 spe vol24 issue3 spe884 pdf  Its father  the RQM tree is also very cool  It allows you to keep info about the minimum element between two indexes of the vector  and it also works in O log n  update and query  I like to teach first the RQM and then the Fenwick Tree

User · Answer

Bloom filter  Bit array of m bits  initially all set to 0    To add an item you run it through k hash functions that will give you k indices in the array which you then set to 1    To check if an item is in the set  compute the k indices and check if they are all set to 1    Of course  this gives some probability of false-positives  according to wikipedia it s about 0 61  m n  where n is the number of inserted items   False-negatives are not possible   Removing an item is impossible  but you can implement counting bloom filter  represented by array of ints and increment decrement

User · Answer

Huffman trees - used for compression

User · Answer

I think Cycle Sort is a pretty neat sorting algorithm     It s a sorting algorithm used to minimize the total number of writes   This is particularly useful when you re dealing with flash memory where the life-span of the flash memory is proportional to the amount of writes   Here is the Wikipedia article  but I recommend going to the first link   nice visuals

User · Answer

I think the FM-index by Paolo Ferragina and Giovanni Manzini is really cool   Especially in bioinformatics   It s essentially a compressed full text index that utilizes a combination of a suffix array and a burrows-wheeler transform of the reference text   The index can be searched without decompressing the whole index

User · Answer

Disjoint Set Forests allow fast membership queries and union operations and are most famously used in Kruskal's Algorithm for minimum spanning trees.

The really cool thing is that both operations have amortized running time proportional to the inverse of the Ackermann Function, making this the "fastest" non-constant time data structure.

User · Answer

Fenwick trees  or binary indexed trees  are a worthy addition to ones toolkit  If you have an array of counters and you need to constantly update them while querying for cumulative counts  as in PPM compression   Fenwick trees will do all operations in O log n  time and require no extra space  See also this topcoder tutorial for a good introduction

User · Answer

I really really love Interval Trees  They allow you to take a bunch of intervals  ie start end times  or whatever  and query for which intervals contain a given time  or which intervals were  active  during a given period  Querying can be done in O log n  and pre-processing is O n log n

User · Answer

Splash Tables are great   They re like a normal hash table  except they guarantee constant-time lookup and can handle 90  utilization without losing performance   They re a generalization of the Cuckoo Hash  also a great data structure    They do appear to be patented  but as with most pure software patents I wouldn t worry too much

User · Answer

I stumbled on another data structure Cartesian Tree when i read about some algorithms related to RMQ and LCA  In a cartesian tree  the lowest common ancestor between two nodes is the minimum node between them  It is useful to convert a RMQ problem to LCA

User · Answer

Spatial Indices  in particular R-trees and KD-trees  store spatial data efficiently  They are good for geographical map coordinate data and VLSI place and route algorithms  and sometimes for nearest-neighbor search   Bit Arrays store individual bits compactly and allow fast bit operations

User · Answer

I personally find sparse matrix data structures to be very interesting   http   www netlib org linalg html templates node90 html  The famous BLAS libraries use these  And when you deal with linear systems that contain 100 000 s of rows and columns  it becomes critical to use these  Some of these also resemble the compact grid  basically like a bucket-sorted grid  which is common in computer graphics  http   www cs kuleuven be  ares publications LD08CFRGRT LD08CFRGRT pdf  Also as far as computer graphics is concerned  MAC grids are somewhat interesting  but only because they re clever  http   www seas upenn edu  cis665 projects Liquation 665 Report pdf

User · Answer

I like suffix tree and arrays for string processing  skip lists for balanced lists and splay trees for automatic balancing trees

User · Answer

Priority deque is cheaper than having to maintain 2 separate priority queues with different orderings  http   www alexandria ucsb edu middleware javadoc edu ucsb adl middleware PriorityDeque html http   cphstl dk Report Priority-deque cphstl-report-2001-14 pdf

User · Answer

Nested sets are nice for representing trees in the relational databases and running queries on them  For instance  ActiveRecord  Ruby on Rails  default ORM  comes with a very simple nested set plugin  which makes working with trees trivial

User · Answer

Arne Andersson trees are a simpler alternative to red-black trees  in which only right links can be red  This greatly simplifies maintenance  while keeping performance on par with red-black trees  The original paper gives a nice and short implementation for insertion and deletion

User · Answer

Priority deque is cheaper than having to maintain 2 separate priority queues with different orderings  http   www alexandria ucsb edu middleware javadoc edu ucsb adl middleware PriorityDeque html http   cphstl dk Report Priority-deque cphstl-report-2001-14 pdf

User · Answer

A corner-stitched data structure   From the summary      Corner stitching is a technique for   representing rectangular   two-dimensional objects  It appears to   be especially well-suited for   interactive editing systems for VLSI   layouts  The data structure has two   important features  first  empty space   is represented explicitly  and second    rectangular areas are stitched   together at their corners like a   patchwork quilt  This organization   results in fast algorithms  linear   time or better  for searching    creation  deletion  stretching  and   compaction  The algorithms are   presented under a simplified model of   VLSI circuits  and the storage   requirements of the structure are   discussed  Measurements indicate that   corner stitching requires   approximately three times as much   memory space as the simplest possible   representation

User · Answer

Delta list delta queue are used in programs like cron or event simulators to work out when the next event should fire  http   everything2 com title delta list  http   www cs iastate edu  cs554 lec notes delta clock pdf

User · Answer

Work Stealing Queue  Lock-free data structure for dividing the work equaly among multiple threads Implementation of a work stealing queue in C C

User · Answer

Scapegoat trees   A classic problem with plain binary trees is that they become unbalanced  e g  when keys are inserted in ascending order    Balanced binary trees  AKA AVL trees  waste a lot of time balancing after each insertion   Red-Black trees stay balanced  but require a extra bit of storage for each node   Scapegoat trees stay balanced like red-black trees  but don t require ANY additional storage   They do this by analyzing the tree after each insertion  and making minor adjustments   See http   en wikipedia org wiki Scapegoat tree

User · Answer

BK-Trees  or Burkhard-Keller Trees are a tree-based data structure which can be used to quickly find near-matches to a string

User · Answer

Kd-Trees  spatial data structure used  amongst others  in Real-Time Raytracing  has the downside that triangles that cross intersect the different spaces need to be clipped  Generally BVH s are faster because they are more lightweight  MX-CIF Quadtrees  store bounding boxes instead of arbitrary point sets by combining a regular quadtree with a binary tree on the edges of the quads  HAMT  hierarchical hash map with access times that generally exceed O 1  hash-maps due to the constants involved  Inverted Index  quite well known in the search-engine circles  because it s used for fast retrieval of documents associated with different search-terms    Most  if not all  of these are documented on the NIST Dictionary of Algorithms and Data Structures

User · Answer

Right-angle triangle networks  RTINs   Beautifully simple way to adaptively subdivide a mesh  Split and merge operations are just a few lines of code each

User · Answer

It s pretty domain-specific  but half-edge data structure is pretty neat  It provides a way to iterate over polygon meshes  faces and edges  which is very useful in computer graphics and computational geometry

User · Answer

Counted unsorted balanced btrees   Perfect for text editor buffers   http   www chiark greenend org uk  sgtatham algorithms cbtree html

User · Answer

Ternary Search Tree   Quick prefix search  for incremental autocomplete etc  Partial Matching  When you want to find all words within X hamming distance of a string  Wildcard Searches   Quite Easy to implement

User · Answer

Fenwick trees  or binary indexed trees  are a worthy addition to ones toolkit  If you have an array of counters and you need to constantly update them while querying for cumulative counts  as in PPM compression   Fenwick trees will do all operations in O log n  time and require no extra space  See also this topcoder tutorial for a good introduction

User · Answer

I m surprised no one has mentioned Merkle trees  ie  Hash Trees    Used in many cases  P2P programs  digital signatures  where you want to verify the hash of a whole file when you only have part of the file available to you

User · Answer

Fibonacci heaps  They re used in some of the fastest known algorithms  asymptotically  for a lot of graph-related problems  such as the Shortest Path problem   Dijkstra s algorithm runs in O E log V  time with standard binary heaps  using Fibonacci heaps improves that to O E   V log V   which is a huge speedup for dense graphs   Unfortunately  though  they have a high constant factor  often making them impractical in practice

User · Answer

PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric  D R Morrison  1968    A PATRICIA tree is related to a Trie  The problem with Tries is that when the set of keys is sparse  i e  when the actual keys form a small subset of the set of potential keys  as is very often the case  many  most  of the internal nodes in the Trie have only one descendant  This causes the Trie to have a high space-complexity   http   www csse monash edu au  lloyd tildeAlgDS Tree PATRICIA

User · Answer

Anyone with experience in 3D rendering should be familiar with BSP trees   Generally  it s the method by structuring a 3D scene to be manageable for rendering knowing the camera coordinates and bearing      Binary space partitioning  BSP  is a   method for recursively subdividing a   space into convex sets by hyperplanes    This subdivision gives rise to a   representation of the scene by means   of a tree data structure known as a   BSP tree       In other words  it is a method of   breaking up intricately shaped   polygons into convex sets  or smaller   polygons consisting entirely of   non-reflex angles  angles smaller than   180     For a more general description   of space partitioning  see space   partitioning       Originally  this approach was proposed   in 3D computer graphics to increase   the rendering efficiency  Some other   applications include performing   geometrical operations with shapes    constructive solid geometry  in CAD    collision detection in robotics and 3D   computer games  and other computer   applications that involve handling of   complex spatial scenes

User · Answer

I personally find sparse matrix data structures to be very interesting   http   www netlib org linalg html templates node90 html  The famous BLAS libraries use these  And when you deal with linear systems that contain 100 000 s of rows and columns  it becomes critical to use these  Some of these also resemble the compact grid  basically like a bucket-sorted grid  which is common in computer graphics  http   www cs kuleuven be  ares publications LD08CFRGRT LD08CFRGRT pdf  Also as far as computer graphics is concerned  MAC grids are somewhat interesting  but only because they re clever  http   www seas upenn edu  cis665 projects Liquation 665 Report pdf

User · Answer

Splay Trees are cool  They reorder themselves in a way that moves the most often queried elements closer to the root

User · Answer

Arne Andersson trees are a simpler alternative to red-black trees  in which only right links can be red  This greatly simplifies maintenance  while keeping performance on par with red-black trees  The original paper gives a nice and short implementation for insertion and deletion

User · Answer

I think lock-free alternatives to standard data structures i e lock-free queue  stack and list are much overlooked  They are increasingly relevant as concurrency becomes a higher priority and are much more admirable goal than using Mutexes or locks to handle concurrent read writes    Here s some links http   www cl cam ac uk research srg netos lock-free  http   www research ibm com people m michael podc-1996 pdf  Links to PDF  http   www boyet com Articles LockfreeStack html   Mike Acton s  often provocative  blog has some excellent articles on lock-free design and approaches

User · Answer

Bloom filter  Bit array of m bits  initially all set to 0    To add an item you run it through k hash functions that will give you k indices in the array which you then set to 1    To check if an item is in the set  compute the k indices and check if they are all set to 1    Of course  this gives some probability of false-positives  according to wikipedia it s about 0 61  m n  where n is the number of inserted items   False-negatives are not possible   Removing an item is impossible  but you can implement counting bloom filter  represented by array of ints and increment decrement

User · Answer

B  tree  It s a variety of B-tree that is efficient for searching at the cost of a more expensive insertion

User · Answer

Circular or ring buffer - used for streaming  among other things

User · Answer

Skip lists are pretty neat        Wikipedia   A skip list is a probabilistic data structure  based on multiple parallel  sorted linked lists  with efficiency comparable to a binary search tree  order log n average time for most operations     They can be used as an alternative to balanced trees  using probalistic balancing rather than strict enforcement of balancing    They are easy to implement and faster than say  a red-black tree  I think they should be in every good programmers toolchest   If you want to get an in-depth introduction to skip-lists here is a link to a video of MIT s Introduction to Algorithms lecture on them   Also  here is a Java applet demonstrating Skip Lists visually

User · Answer

A proper string data structure  Almost every programmer settles for whatever native support that a language has for the structure and that s usually inefficient  especially for building strings  you need a separate class or something else    The worst is treating a string as a character array in C and relying on the NULL byte for safety

User · Answer

One lesser known  but pretty nifty data structure is the Fenwick Tree  also sometimes called a Binary Indexed Tree or BIT   It stores cumulative sums and supports O log n   operations  Although cumulative sums might not sound very exciting  it can be adapted to solve many problems requiring a sorted log n  data structure    IMO  its main selling point is the ease with which can be implemented  Very useful in solving algorithmic problems that would involve coding a red-black avl tree otherwise

User · Answer

A min-max heap is a variation of a heap that implements a double-ended priority queue  It achieves this by by a simple change to the heap property  A tree is said to be min-max ordered if every element on even  odd  levels are less  greater  than all childrens and grand children  The levels are numbered starting from 1   http   internet512 chonbuk ac kr datastructure heap img heap8 jpg

User · Answer

Pairing heaps are a type of heap data structure with relatively simple implementation and excellent practical amortized performance

User · Answer

Delta list delta queue are used in programs like cron or event simulators to work out when the next event should fire  http   everything2 com title delta list  http   www cs iastate edu  cs554 lec notes delta clock pdf

User · Answer

Here are a few    Suffix tries   Useful for almost all kinds of string searching  http   en wikipedia org wiki Suffix trie Functionality    See also suffix arrays  they re not quite as fast as suffix trees  but a whole lot smaller  Splay trees  as mentioned above    The reason they are cool is threefold    They are small  you only need the left and right pointers like you do in any binary tree  no node-color or size information needs to be stored  They are  comparatively  very easy to implement They offer optimal amortized complexity for a whole host of  measurement criteria   log n lookup time being the one everybody knows    See http   en wikipedia org wiki Splay tree Performance theorems  Heap-ordered search trees  you store a bunch of  key  prio  pairs in a tree  such that it s a search tree with respect to the keys  and heap-ordered with respect to the priorities   One can show that such a tree has a unique shape  and it s not always fully packed up-and-to-the-left    With random priorities  it gives you expected O log n  search time  IIRC  A niche one is adjacency lists for undirected planar graphs with O 1  neighbour queries   This is not so much a data structure as a particular way to organize an existing data structure   Here s how you do it  every planar graph has a node with degree at most 6   Pick such a node  put its neighbors in its neighbor list  remove it from the graph  and recurse until the graph is empty   When given a pair  u  v   look for u in v s neighbor list and for v in u s neighbor list   Both have size at most 6  so this is O 1     By the above algorithm  if u and v are neighbors  you won t have both u in v s list and v in u s list   If you need this  just add each node s missing neighbors to that node s neighbor list  but store how much of the neighbor list you need to look through for fast lookup

User · Answer

Ternary Search Tree   Quick prefix search  for incremental autocomplete etc  Partial Matching  When you want to find all words within X hamming distance of a string  Wildcard Searches   Quite Easy to implement

User · Answer

Not really a data structure  more of a way to optimize dynamically allocated arrays  but the gap buffers used in Emacs are kind of cool

User · Answer

Here are a few    Suffix tries   Useful for almost all kinds of string searching  http   en wikipedia org wiki Suffix trie Functionality    See also suffix arrays  they re not quite as fast as suffix trees  but a whole lot smaller  Splay trees  as mentioned above    The reason they are cool is threefold    They are small  you only need the left and right pointers like you do in any binary tree  no node-color or size information needs to be stored  They are  comparatively  very easy to implement They offer optimal amortized complexity for a whole host of  measurement criteria   log n lookup time being the one everybody knows    See http   en wikipedia org wiki Splay tree Performance theorems  Heap-ordered search trees  you store a bunch of  key  prio  pairs in a tree  such that it s a search tree with respect to the keys  and heap-ordered with respect to the priorities   One can show that such a tree has a unique shape  and it s not always fully packed up-and-to-the-left    With random priorities  it gives you expected O log n  search time  IIRC  A niche one is adjacency lists for undirected planar graphs with O 1  neighbour queries   This is not so much a data structure as a particular way to organize an existing data structure   Here s how you do it  every planar graph has a node with degree at most 6   Pick such a node  put its neighbors in its neighbor list  remove it from the graph  and recurse until the graph is empty   When given a pair  u  v   look for u in v s neighbor list and for v in u s neighbor list   Both have size at most 6  so this is O 1     By the above algorithm  if u and v are neighbors  you won t have both u in v s list and v in u s list   If you need this  just add each node s missing neighbors to that node s neighbor list  but store how much of the neighbor list you need to look through for fast lookup

User · Answer

Getting away from all these graph structures  I just love the simple Ring-Buffer    When properly implemented you can seriously reduce your memory footprint while maintaining performance and sometimes even improving it

User · Answer

I think lock-free alternatives to standard data structures i e lock-free queue  stack and list are much overlooked  They are increasingly relevant as concurrency becomes a higher priority and are much more admirable goal than using Mutexes or locks to handle concurrent read writes    Here s some links http   www cl cam ac uk research srg netos lock-free  http   www research ibm com people m michael podc-1996 pdf  Links to PDF  http   www boyet com Articles LockfreeStack html   Mike Acton s  often provocative  blog has some excellent articles on lock-free design and approaches

User · Answer

Binary decision diagram is one of my favorite data structures  or in fact Reduced Ordered Binary Decision Diagram  ROBDD    These kind of structures can for instance be used for    Representing sets of items and performing very fast logical operations on those sets  Any boolean expression  with the intention of finding all solutions for the expression   Note that many problems can be represented as a boolean expression  For instance the solution to a suduku can be expressed as a boolean expression  And building a BDD for that boolean expression will immediately yield the solution s

User · Answer

The Region Quadtree   quoted from Wikipedia      The region quadtree represents a partition of space in two dimensions by decomposing the region into four equal quadrants  subquadrants  and so on with each leaf node containing data corresponding to a specific subregion  Each node in the tree either has exactly four children  or has no children  a leaf node     Quadtrees like this are good for storing spatial data  e g  latitude and longitude or other types of coordinates   This was by far my favorite data structure in college   Coding this guy and seeing it work was pretty cool   I highly recommend it if you re looking for a project that will take some thought and is a little off the beaten path   Anyway  it s a lot more fun than the standard BST derivatives that you re usually assigned in your data structures class   In fact  as a bonus  I ve found the notes from the lecture leading up to the class project  from Virginia Tech  here  pdf warning

User · Answer

A proper string data structure  Almost every programmer settles for whatever native support that a language has for the structure and that s usually inefficient  especially for building strings  you need a separate class or something else    The worst is treating a string as a character array in C and relying on the NULL byte for safety

User · Answer

Ball Trees   Just because they make people giggle   A ball tree is a data structure that indexes points in a metric space   Here s an article on building them    They are often used for finding nearest neighbors to a point or accelerating k-means

User · Answer

I had good luck with WPL Trees before   A tree variant that minimizes the weighted path length of the branches   Weight is determined by node access  so that frequently-accessed nodes migrate closer to the root   Not sure how they compare to splay trees  as I ve never used those

User · Answer

I like treaps -  for the simple  yet effective idea of superimposing a heap structure with random priority over a binary search tree in order to balance it

User · Answer

Bucket Brigade  They are used extensively in Apache  Basically they are a linked list that loops around on itself in a ring  I am not sure if they are used outside of Apache and Apache modules but they fit the bill as a cool yet lesser known data structure  A bucket is a container for some arbitrary data and a bucket brigade is a collection of buckets  The idea is that you want to be able to modify and insert data at any point in the structure    Lets say that you have a bucket brigade that contains an html document with one character per bucket  You want to convert all the  lt  and  gt  symbols into  amp lt  and  amp gt  entities  The bucket brigade allows you to insert some extra buckets in the brigade when you come across a  lt  or  gt  symbol in order to fit the extra characters required for the entity  Because the bucket brigade is in a ring you can insert backwards or forwards  This is much easier to do  in C  than using a simple buffer    Some reference on bucket brigades below   Apache Bucket Brigade Reference  Introduction to Buckets and Brigades

User · Answer

Spatial Indices  in particular R-trees and KD-trees  store spatial data efficiently  They are good for geographical map coordinate data and VLSI place and route algorithms  and sometimes for nearest-neighbor search   Bit Arrays store individual bits compactly and allow fast bit operations

User · Answer

Persistent Data Structures

User · Answer

Zobrist Hashing is a hash function generally used for representing a game board position  like in Chess  but surely has other uses   One nice things about it is that is can be incrementally updated as the board is updated

User · Answer

How about splay trees   Also  Chris Okasaki s purely functional data structures come to mind

User · Answer

Van Emde-Boas trees   I have even a C   implementation of it  for up to 2 20 integers

User · Answer

Right-angle triangle networks  RTINs   Beautifully simple way to adaptively subdivide a mesh  Split and merge operations are just a few lines of code each

User · Answer

lt zvrba gt  Van Emde-Boas trees   I think it d be useful to know why they re cool   In general  the question  why  is the most important to ask     My answer is that they give you O log log n  dictionaries with  1  n  keys  independent of how many of the keys are in use   Just like repeated halving gives you O log n   repeated sqrting gives you O log log n   which is what happens in the vEB tree

User · Answer

I like treaps -  for the simple  yet effective idea of superimposing a heap structure with random priority over a binary search tree in order to balance it

User · Answer

I like treaps -  for the simple  yet effective idea of superimposing a heap structure with random priority over a binary search tree in order to balance it

User · Answer

2-3 Finger Trees by Hinze and Paterson are a great functional data structure swiss-army knife with great asymptotics for a wide range of operations  While complex  they are much simpler than the imperative structures by Persistent lists with catenation via recursive slow-down by Kaplan and Tarjan that preceded them   They work as a catenable deque with O 1  access to either end  O log min n m   append  and provide O log min n length - n   indexing with direct access to a monoidal prefix sum over any portion of the sequence   Implementations exist in Haskell  Coq  F   Scala  Java  C  Clojure  C  and other languages   You can use them to implement priority search queues  interval maps  ropes with fast head access  maps  sets  catenable sequences or pretty much any structure where you can phrase it as collecting a monoidal result over a quickly catenable indexable sequence   I also have some slides describing their derivation and use

User · Answer

Rope  It s a string that allows for cheap prepends  substrings  middle insertions and appends  I ve really only had use for it once  but no other structure would have sufficed  Regular strings and arrays prepends were just far too expensive for what we needed to do  and reversing everthing was out of the question

User · Answer

Anyone with experience in 3D rendering should be familiar with BSP trees   Generally  it s the method by structuring a 3D scene to be manageable for rendering knowing the camera coordinates and bearing      Binary space partitioning  BSP  is a   method for recursively subdividing a   space into convex sets by hyperplanes    This subdivision gives rise to a   representation of the scene by means   of a tree data structure known as a   BSP tree       In other words  it is a method of   breaking up intricately shaped   polygons into convex sets  or smaller   polygons consisting entirely of   non-reflex angles  angles smaller than   180     For a more general description   of space partitioning  see space   partitioning       Originally  this approach was proposed   in 3D computer graphics to increase   the rendering efficiency  Some other   applications include performing   geometrical operations with shapes    constructive solid geometry  in CAD    collision detection in robotics and 3D   computer games  and other computer   applications that involve handling of   complex spatial scenes

User · Answer

Circular or ring buffer - used for streaming  among other things

User · Answer

I m surprised no one has mentioned Merkle trees  ie  Hash Trees    Used in many cases  P2P programs  digital signatures  where you want to verify the hash of a whole file when you only have part of the file available to you

User · Answer

Rope  It s a string that allows for cheap prepends  substrings  middle insertions and appends  I ve really only had use for it once  but no other structure would have sufficed  Regular strings and arrays prepends were just far too expensive for what we needed to do  and reversing everthing was out of the question

User · Answer

Spatial Indices  in particular R-trees and KD-trees  store spatial data efficiently  They are good for geographical map coordinate data and VLSI place and route algorithms  and sometimes for nearest-neighbor search   Bit Arrays store individual bits compactly and allow fast bit operations

User · Answer

I think the FM-index by Paolo Ferragina and Giovanni Manzini is really cool   Especially in bioinformatics   It s essentially a compressed full text index that utilizes a combination of a suffix array and a burrows-wheeler transform of the reference text   The index can be searched without decompressing the whole index

User · Answer

Left Leaning Red-Black Trees  A significantly simplified implementation of red-black trees by Robert Sedgewick published in 2008   half the lines of code to implement    If you ve ever had trouble wrapping your head around the implementation of a Red-Black tree  read about this variant   Very similar  if not identical  to Andersson Trees

User · Answer

A queue implemented using 2 stacks is pretty space efficient  as opposed to using a linked list which will have at least a 1 extra pointer reference overhead    How to implement a queue using two stacks   This has worked well for me when the queues are huge  If I save 8 bytes on a pointer  it means that queues with a million entries save about 8MB of RAM

User · Answer

Fast Compact tries    Judy arrays  Very fast and memory efficient ordered sparse dynamic arrays for bits  integers and strings  Judy arrays are faster and more memory efficient than any binary-search-tree  HAT-trie  A Cache-conscious Trie-based Data Structure for Strings B-tries for Disk-based String Management

User · Answer

Nested sets are nice for representing trees in the relational databases and running queries on them  For instance  ActiveRecord  Ruby on Rails  default ORM  comes with a very simple nested set plugin  which makes working with trees trivial

User · Answer

How about splay trees   Also  Chris Okasaki s purely functional data structures come to mind

User · Answer

Tries  also known as prefix-trees or crit-bit trees  have existed for over 40 years but are still relatively unknown   A very cool use of tries is described in  TRASH - A dynamic LC-trie and hash data structure   which combines a trie with a hash function

User · Answer

A queue implemented using 2 stacks is pretty space efficient  as opposed to using a linked list which will have at least a 1 extra pointer reference overhead    How to implement a queue using two stacks   This has worked well for me when the queues are huge  If I save 8 bytes on a pointer  it means that queues with a million entries save about 8MB of RAM

User · Answer

You can use a min-heap to find the minimum element in constant time  or a max-heap to find the the maximum element  But what if you wanted to do both operations  You can use a Min-Max to do both operations in constant time  It works by using min max ordering  alternating between min and max heap comparison between consecutive tree levels

User · Answer

How about splay trees   Also  Chris Okasaki s purely functional data structures come to mind

User · Answer

lt zvrba gt  Van Emde-Boas trees   I think it d be useful to know why they re cool   In general  the question  why  is the most important to ask     My answer is that they give you O log log n  dictionaries with  1  n  keys  independent of how many of the keys are in use   Just like repeated halving gives you O log n   repeated sqrting gives you O log log n   which is what happens in the vEB tree

User · Answer

Someone else already proposed Burkhard-Keller-Trees  but I thought I might mention them again in order to plug my own implementation      http   well-adjusted de mspace py index html  There are faster implementations around  see ActiveState s Python recipes or implementations in other languages   but I think hope my code helps to understand these data structures   By the way  both BK and VP trees can be used for much more than searching for similar strings  You can do similarity searches for arbitrary objects as long as you have a distance function that satisfies a few conditions  positivity  symmetry  triangle inequality

User · Answer

Kd-Trees  spatial data structure used  amongst others  in Real-Time Raytracing  has the downside that triangles that cross intersect the different spaces need to be clipped  Generally BVH s are faster because they are more lightweight  MX-CIF Quadtrees  store bounding boxes instead of arbitrary point sets by combining a regular quadtree with a binary tree on the edges of the quads  HAMT  hierarchical hash map with access times that generally exceed O 1  hash-maps due to the constants involved  Inverted Index  quite well known in the search-engine circles  because it s used for fast retrieval of documents associated with different search-terms    Most  if not all  of these are documented on the NIST Dictionary of Algorithms and Data Structures

User · Answer

BK-Trees  or Burkhard-Keller Trees are a tree-based data structure which can be used to quickly find near-matches to a string

User · Answer

Tries  also known as prefix-trees or crit-bit trees  have existed for over 40 years but are still relatively unknown   A very cool use of tries is described in  TRASH - A dynamic LC-trie and hash data structure   which combines a trie with a hash function

User · Answer

An interesting variant of the hash table is called Cuckoo Hashing  It uses multiple hash functions instead of just 1 in order to deal with hash collisions  Collisions are resolved by removing the old object from the location specified by the primary hash  and moving it to a location specified by an alternate hash function  Cuckoo Hashing allows for more efficient use of memory space because you can increase your load factor up to 91  with only 3 hash functions and still have good access time

User · Answer

One lesser known  but pretty nifty data structure is the Fenwick Tree  also sometimes called a Binary Indexed Tree or BIT   It stores cumulative sums and supports O log n   operations  Although cumulative sums might not sound very exciting  it can be adapted to solve many problems requiring a sorted log n  data structure    IMO  its main selling point is the ease with which can be implemented  Very useful in solving algorithmic problems that would involve coding a red-black avl tree otherwise

User · Answer

Van Emde-Boas trees   I have even a C   implementation of it  for up to 2 20 integers

User · Answer

Binary decision diagram is one of my favorite data structures  or in fact Reduced Ordered Binary Decision Diagram  ROBDD    These kind of structures can for instance be used for    Representing sets of items and performing very fast logical operations on those sets  Any boolean expression  with the intention of finding all solutions for the expression   Note that many problems can be represented as a boolean expression  For instance the solution to a suduku can be expressed as a boolean expression  And building a BDD for that boolean expression will immediately yield the solution s

User · Answer

You can use a min-heap to find the minimum element in constant time  or a max-heap to find the the maximum element  But what if you wanted to do both operations  You can use a Min-Max to do both operations in constant time  It works by using min max ordering  alternating between min and max heap comparison between consecutive tree levels

User · Answer

I like treaps -  for the simple  yet effective idea of superimposing a heap structure with random priority over a binary search tree in order to balance it

User · Answer

I think Cycle Sort is a pretty neat sorting algorithm     It s a sorting algorithm used to minimize the total number of writes   This is particularly useful when you re dealing with flash memory where the life-span of the flash memory is proportional to the amount of writes   Here is the Wikipedia article  but I recommend going to the first link   nice visuals

User · Answer

An interesting variant of the hash table is called Cuckoo Hashing  It uses multiple hash functions instead of just 1 in order to deal with hash collisions  Collisions are resolved by removing the old object from the location specified by the primary hash  and moving it to a location specified by an alternate hash function  Cuckoo Hashing allows for more efficient use of memory space because you can increase your load factor up to 91  with only 3 hash functions and still have good access time

User · Answer

Zippers - derivatives of data structures that modify the structure to have a natural notion of  cursor  -- current location  These are really useful as they guarantee indicies cannot be out of bound -- used  e g  in the xmonad window manager to track which window has focused    Amazingly  you can derive them by applying techniques from calculus to the type of the original data structure

User · Answer

XOR Linked List uses two XOR d pointers to lessen the storage requirements for doubly-linked list  Kind of obscure but neat

User · Answer

Binomial heap s have a lot of interesting properties  most useful of which is merging

User · Answer

There is a clever Data-structure out there that uses Arrays to save the Data of the Elements  but the Arrays are linked together in an Linked-List Array   This does have the advantage that the iteration over the elements is very fast  faster than a pure linked-list approach  and the costs for moving the Arrays with the Elements around in Memory and or  de- allocation are at a minimum   Because of this this data-structure is usefull for Simulation stuff    I know about it from here   http   software intel com en-us blogs 2010 03 26 linked-list-verses-array       and that an additional array is allocated and linked in to the cell list of arrays of particles   This is similar in some respects to how TBB implemented its concurrent container   it is about ther Performance of Linked Lists vs  Arrays

User · Answer

Per the Bloom Filter mentions  Deletable Bloom Filters  DlBF  are in some ways better than basic counting variants   See http   arxiv org abs 1005 0352

User · Answer

I like Cache Oblivious datastructures   The basic idea is to lay out a tree in recursively smaller blocks so that caches of many different sizes will take advantage of blocks that convenient fit in them   This leads to efficient use of caching at everything from L1 cache in RAM to big chunks of data read off of the disk without needing to know the specifics of the sizes of any of those caching layers

User · Answer

Skip lists are pretty neat        Wikipedia   A skip list is a probabilistic data structure  based on multiple parallel  sorted linked lists  with efficiency comparable to a binary search tree  order log n average time for most operations     They can be used as an alternative to balanced trees  using probalistic balancing rather than strict enforcement of balancing    They are easy to implement and faster than say  a red-black tree  I think they should be in every good programmers toolchest   If you want to get an in-depth introduction to skip-lists here is a link to a video of MIT s Introduction to Algorithms lecture on them   Also  here is a Java applet demonstrating Skip Lists visually

User · Answer

Someone else already proposed Burkhard-Keller-Trees  but I thought I might mention them again in order to plug my own implementation      http   well-adjusted de mspace py index html  There are faster implementations around  see ActiveState s Python recipes or implementations in other languages   but I think hope my code helps to understand these data structures   By the way  both BK and VP trees can be used for much more than searching for similar strings  You can do similarity searches for arbitrary objects as long as you have a distance function that satisfies a few conditions  positivity  symmetry  triangle inequality

User · Answer

Enhanced hashing algorithms are quite interesting  Linear hashing is neat  because it allows splitting one  bucket  in your hash table at a time  rather than rehashing the entire table  This is especially useful for distributed caches  However  with most simple splitting policies  you end up splitting all buckets in quick succession  and the load factor of the table oscillates pretty badly   I think that spiral hashing is really neat too  Like linear hashing  one bucket at a time is split  and a little less than half of the records in the bucket are put into the same new bucket  It s very clean and fast  However  it can be inefficient if each  bucket  is hosted by a machine with similar specs  To utilize the hardware fully  you want a mix of less- and more-powerful machines

User · Answer

Binary decision diagram  my very favorite data structure  good for representing boolean equations  and solving them  Effective for a great lot of things  Heaps  a tree where the parent of a node always maintains some relation to the children of the node  for instance  the parent of a node is always greater than each of it s children  max-heap    Priority Queues  really just min-heaps and max-heaps  good for maintaining order of a lot of elements there the e g  the item with the highest value is supposed to be removed first  Hash tables   with all kinds of lookup strategies  and bucket overflow handling  Balanced binary search trees  Each of these have their own advantages    RB-trees  overall good  when inserting  lookup  removing and iterating in an ordered fashion  Avl-trees  faster for lookup than RB  but otherwise very similar to RB  Splay-trees  faster for lookup when recently used nodes are likely to be reused  Fusion-tree  Exploiting fast multiplication for getting even better lookup times  B Trees  Used for indexing in databases and file systems  very efficient when latency to read write from to the index is significant    Spatial indexes   Excellent for querying for whether points circles rectangles lines cubes is in close proximity to or contained within each other    BSP tree Quadtree Octree Range-tree Lots of similar but slightly different trees  and different dimensions  Interval trees  good finding overlapping intervals  linear  Graphs   adjacency list  basically a list of edges  adjacency matrix  a table representing directed edges of a graph with a single bit per edge  Very fast for graph traversal     These are the ones i can come to think of  There are even more on wikipedia about data structures

User · Answer

Half edge data structure and winged edge for polygonal meshes   Useful for computational geometry algorithms

User · Answer

Left Leaning Red-Black Trees  A significantly simplified implementation of red-black trees by Robert Sedgewick published in 2008   half the lines of code to implement    If you ve ever had trouble wrapping your head around the implementation of a Red-Black tree  read about this variant   Very similar  if not identical  to Andersson Trees

User · Answer

Fenwick Tree  It s a data structure to keep count of the sum of all elements in a vector  between two given subindexes i and j  The trivial solution  precalculating the sum since the begining doesn t allow to update a item  you have to do O n  work to keep up    Fenwick Trees allow you to update and query in O log n   and how it works is really cool and simple  It s really well explained in Fenwick s original paper  freely available here   http   www cs ubc ca local reading proceedings spe91-95 spe vol24 issue3 spe884 pdf  Its father  the RQM tree is also very cool  It allows you to keep info about the minimum element between two indexes of the vector  and it also works in O log n  update and query  I like to teach first the RQM and then the Fenwick Tree

User · Answer

XOR Linked List uses two XOR d pointers to lessen the storage requirements for doubly-linked list  Kind of obscure but neat

User · Answer

How about splay trees   Also  Chris Okasaki s purely functional data structures come to mind

User · Answer

Enhanced hashing algorithms are quite interesting  Linear hashing is neat  because it allows splitting one  bucket  in your hash table at a time  rather than rehashing the entire table  This is especially useful for distributed caches  However  with most simple splitting policies  you end up splitting all buckets in quick succession  and the load factor of the table oscillates pretty badly   I think that spiral hashing is really neat too  Like linear hashing  one bucket at a time is split  and a little less than half of the records in the bucket are put into the same new bucket  It s very clean and fast  However  it can be inefficient if each  bucket  is hosted by a machine with similar specs  To utilize the hardware fully  you want a mix of less- and more-powerful machines

User · Answer

DAWGs are a special kind of Trie where similar child trees are compressed into single parents  I extended modified DAWGs and came up with a nifty data structure called ASSDAWG  Anagram Search Sorted DAWG   The way this works is whenever a string is inserted into the DAWG  it is bucket-sorted first and then inserted and the leaf nodes hold an additional number indicating which permutations are valid if we reach that leaf node from root  This has 2 nifty advantages    Since I sort the strings before insertion and since DAWGs naturally collapse similar sub trees  I get high level of compression  e g   eat    ate    tea  all become 1 path a-e-t with a list of numbers at the leaf node indicating which permutations of a-e-t are valid   Searching for anagrams of a given string is super fast and trivial now as a path from root to leaf holds all the valid anagrams of that path at the leaf node using permutation-numbers

User · Answer

Huffman trees - used for compression

User · Answer

An unrolled linked list is a variation on the linked list which stores multiple elements in each node  It can drastically increase cache performance  while decreasing the memory overhead associated with storing list metadata such as references  It is related to the B-tree   record node       node next          reference to next node in list     int numElements    number of elements in this node  up to maxElements     array elements     an array of numElements elements  with space allocated for maxElements elements

User · Answer

Spatial Indices  in particular R-trees and KD-trees  store spatial data efficiently  They are good for geographical map coordinate data and VLSI place and route algorithms  and sometimes for nearest-neighbor search   Bit Arrays store individual bits compactly and allow fast bit operations

User · Answer

Have a look at Finger Trees  especially if you re a fan of the previously mentioned purely functional data structures  They re a functional representation of persistent sequences supporting access to the ends in amortized constant time  and concatenation and splitting in time logarithmic in the size of the smaller piece    As per the original article      Our functional 2-3 finger trees are an instance of a general design technique in- troduced by Okasaki  1998   called implicit recursive slowdown  We have already noted that these trees are an extension of his implicit deque structure  replacing pairs with 2-3 nodes to provide the flexibility required for efficient concatenation and splitting    A Finger Tree can be parameterized with a monoid  and using different monoids will result in different behaviors for the tree  This lets Finger Trees simulate other data structures

User · Answer

Per the Bloom Filter mentions  Deletable Bloom Filters  DlBF  are in some ways better than basic counting variants   See http   arxiv org abs 1005 0352

User · Answer

Pairing heaps are a type of heap data structure with relatively simple implementation and excellent practical amortized performance

User · Answer

I think Disjoint Set is pretty nifty for cases when you need to divide a bunch of items into distinct sets and query membership   Good implementation of the Union and Find operations result in amortized costs that are effectively constant  inverse of Ackermnan s Function  if I recall my data structures class correctly

User · Answer

Burrows   Wheeler transform  block-sorting compression   Its essential algorithm for compression  Let say that you want to compress lines on text files  You would say that if you sort the lines  you lost information  But BWT works like this - it reduces entropy a lot by sorting input  keeping integer indexes to recover the original order

User · Answer

Bucket Brigade  They are used extensively in Apache  Basically they are a linked list that loops around on itself in a ring  I am not sure if they are used outside of Apache and Apache modules but they fit the bill as a cool yet lesser known data structure  A bucket is a container for some arbitrary data and a bucket brigade is a collection of buckets  The idea is that you want to be able to modify and insert data at any point in the structure    Lets say that you have a bucket brigade that contains an html document with one character per bucket  You want to convert all the  lt  and  gt  symbols into  amp lt  and  amp gt  entities  The bucket brigade allows you to insert some extra buckets in the brigade when you come across a  lt  or  gt  symbol in order to fit the extra characters required for the entity  Because the bucket brigade is in a ring you can insert backwards or forwards  This is much easier to do  in C  than using a simple buffer    Some reference on bucket brigades below   Apache Bucket Brigade Reference  Introduction to Buckets and Brigades

User · Answer

I stumbled on another data structure Cartesian Tree when i read about some algorithms related to RMQ and LCA  In a cartesian tree  the lowest common ancestor between two nodes is the minimum node between them  It is useful to convert a RMQ problem to LCA

User · Answer

Bootstrapped skew-binomial heaps by Gerth St  lting Brodal and Chris Okasaki   Despite their long name  they provide asymptotically optimal heap operations  even in a function setting     O 1  size  union  insert  minimum O log n  deleteMin    Note that union takes O 1  rather than O log n  time unlike the more well-known heaps that are commonly covered in data structure textbooks  such as leftist heaps  And unlike Fibonacci heaps  those asymptotics are worst-case  rather than amortized  even if used persistently   There are multiple implementations in Haskell    They were jointly derived by Brodal and Okasaki  after Brodal came up with an imperative heap with the same asymptotics

User · Answer

Skip lists are actually pretty awesome       http   en wikipedia org wiki Skip list

User · Answer

Van Emde-Boas trees   I have even a C   implementation of it  for up to 2 20 integers

User · Answer

Here are a few    Suffix tries   Useful for almost all kinds of string searching  http   en wikipedia org wiki Suffix trie Functionality    See also suffix arrays  they re not quite as fast as suffix trees  but a whole lot smaller  Splay trees  as mentioned above    The reason they are cool is threefold    They are small  you only need the left and right pointers like you do in any binary tree  no node-color or size information needs to be stored  They are  comparatively  very easy to implement They offer optimal amortized complexity for a whole host of  measurement criteria   log n lookup time being the one everybody knows    See http   en wikipedia org wiki Splay tree Performance theorems  Heap-ordered search trees  you store a bunch of  key  prio  pairs in a tree  such that it s a search tree with respect to the keys  and heap-ordered with respect to the priorities   One can show that such a tree has a unique shape  and it s not always fully packed up-and-to-the-left    With random priorities  it gives you expected O log n  search time  IIRC  A niche one is adjacency lists for undirected planar graphs with O 1  neighbour queries   This is not so much a data structure as a particular way to organize an existing data structure   Here s how you do it  every planar graph has a node with degree at most 6   Pick such a node  put its neighbors in its neighbor list  remove it from the graph  and recurse until the graph is empty   When given a pair  u  v   look for u in v s neighbor list and for v in u s neighbor list   Both have size at most 6  so this is O 1     By the above algorithm  if u and v are neighbors  you won t have both u in v s list and v in u s list   If you need this  just add each node s missing neighbors to that node s neighbor list  but store how much of the neighbor list you need to look through for fast lookup

User · Answer

Skip lists are actually pretty awesome       http   en wikipedia org wiki Skip list

User · Answer

I sometimes use Inversion LIsts to store ranges  and they are often used to store character classes in regular expressions  See for example http   www ibm com developerworks linux library l-cpinv html  Another nice use case is for weighted random decisions  Suppose you have a list of symbols and associated probabilites  and you want to pick them at random according to these probabilities      a    0 1    b    0 5    c    0 4   Then you do a running sum of all the probabilities       0 1  0 6  1 0    This is your inversion list  You generate a random number between 0 and 1  and find the index of the next higher entry in the list  You can do that with a binary search  because it s sorted  Once you ve got the index  you can look up the symbol in the original list   If you have n symbols  you have O n  preparation time  and then O log n   acess time for each randomly chosen symbol - independently of the distribution of weights   A variation of inversion lists uses negative numbers to indicate the endpoint of ranges  which makes it easy to count how many ranges overlap at a certain point  See http   www perlmonks org index pl node id 841368 for an example

User · Answer

The Region Quadtree   quoted from Wikipedia      The region quadtree represents a partition of space in two dimensions by decomposing the region into four equal quadrants  subquadrants  and so on with each leaf node containing data corresponding to a specific subregion  Each node in the tree either has exactly four children  or has no children  a leaf node     Quadtrees like this are good for storing spatial data  e g  latitude and longitude or other types of coordinates   This was by far my favorite data structure in college   Coding this guy and seeing it work was pretty cool   I highly recommend it if you re looking for a project that will take some thought and is a little off the beaten path   Anyway  it s a lot more fun than the standard BST derivatives that you re usually assigned in your data structures class   In fact  as a bonus  I ve found the notes from the lecture leading up to the class project  from Virginia Tech  here  pdf warning

User · Answer

Ball Trees   Just because they make people giggle   A ball tree is a data structure that indexes points in a metric space   Here s an article on building them    They are often used for finding nearest neighbors to a point or accelerating k-means

User · Answer

I am not sure if this data structure has a name  but the proposed tokenmap data structure for inclusion into Boost is kind of interesting  It is a dynamically resizable map where look-ups are not only O 1   they are simple array accesses  I wrote most of the background material on this data structure which describes the fundamental principle behind how it works   Something like a tokenmap is used by operating systems to map file or resource handles to data structures representing the file or resource

User · Answer

2-3 Finger Trees by Hinze and Paterson are a great functional data structure swiss-army knife with great asymptotics for a wide range of operations  While complex  they are much simpler than the imperative structures by Persistent lists with catenation via recursive slow-down by Kaplan and Tarjan that preceded them   They work as a catenable deque with O 1  access to either end  O log min n m   append  and provide O log min n length - n   indexing with direct access to a monoidal prefix sum over any portion of the sequence   Implementations exist in Haskell  Coq  F   Scala  Java  C  Clojure  C  and other languages   You can use them to implement priority search queues  interval maps  ropes with fast head access  maps  sets  catenable sequences or pretty much any structure where you can phrase it as collecting a monoidal result over a quickly catenable indexable sequence   I also have some slides describing their derivation and use

User · Answer

Kd-Trees  spatial data structure used  amongst others  in Real-Time Raytracing  has the downside that triangles that cross intersect the different spaces need to be clipped  Generally BVH s are faster because they are more lightweight  MX-CIF Quadtrees  store bounding boxes instead of arbitrary point sets by combining a regular quadtree with a binary tree on the edges of the quads  HAMT  hierarchical hash map with access times that generally exceed O 1  hash-maps due to the constants involved  Inverted Index  quite well known in the search-engine circles  because it s used for fast retrieval of documents associated with different search-terms    Most  if not all  of these are documented on the NIST Dictionary of Algorithms and Data Structures

User · Answer

Environment tracking recursive structures      Compilers use a structure that is recursive but not like a tree   Inner scopes have a pointer to an enclosing scope so the nesting is inside-out   Verifying whether a variable is in scope is a recursive call from the inside scope to the enclosing scope   public class Env           HashMap lt String  Object gt  map      Env                     outer       Env                 outer   null          map   new HashMap               Env Env o                outer   o          map   new HashMap               void put String key  Object value                map put key  value              Object get String key                if  map containsKey key                         return map get key                     if  outer    null                        return outer get key                     return null             Env push                 return new Env this              Env pop                 return outer            I m not sure if this structure even has a name   I call it an inside-out list

User · Answer

Persistent Data Structures

User · Answer

I had good luck with WPL Trees before   A tree variant that minimizes the weighted path length of the branches   Weight is determined by node access  so that frequently-accessed nodes migrate closer to the root   Not sure how they compare to splay trees  as I ve never used those

User · Answer

An unrolled linked list is a variation on the linked list which stores multiple elements in each node  It can drastically increase cache performance  while decreasing the memory overhead associated with storing list metadata such as references  It is related to the B-tree   record node       node next          reference to next node in list     int numElements    number of elements in this node  up to maxElements     array elements     an array of numElements elements  with space allocated for maxElements elements

User · Answer

DAWGs are a special kind of Trie where similar child trees are compressed into single parents  I extended modified DAWGs and came up with a nifty data structure called ASSDAWG  Anagram Search Sorted DAWG   The way this works is whenever a string is inserted into the DAWG  it is bucket-sorted first and then inserted and the leaf nodes hold an additional number indicating which permutations are valid if we reach that leaf node from root  This has 2 nifty advantages    Since I sort the strings before insertion and since DAWGs naturally collapse similar sub trees  I get high level of compression  e g   eat    ate    tea  all become 1 path a-e-t with a list of numbers at the leaf node indicating which permutations of a-e-t are valid   Searching for anagrams of a given string is super fast and trivial now as a path from root to leaf holds all the valid anagrams of that path at the leaf node using permutation-numbers

User · Answer

Zobrist Hashing is a hash function generally used for representing a game board position  like in Chess  but surely has other uses   One nice things about it is that is can be incrementally updated as the board is updated

User · Answer

Zippers - derivatives of data structures that modify the structure to have a natural notion of  cursor  -- current location  These are really useful as they guarantee indicies cannot be out of bound -- used  e g  in the xmonad window manager to track which window has focused    Amazingly  you can derive them by applying techniques from calculus to the type of the original data structure

User · Answer

B  tree  It s a variety of B-tree that is efficient for searching at the cost of a more expensive insertion

User · Answer

Take a look at the sideways heap  presented by Donald Knuth   http   stanford-online stanford edu seminars knuth 071203-knuth-300 asx

User · Answer

Have a look at Finger Trees  especially if you re a fan of the previously mentioned purely functional data structures  They re a functional representation of persistent sequences supporting access to the ends in amortized constant time  and concatenation and splitting in time logarithmic in the size of the smaller piece    As per the original article      Our functional 2-3 finger trees are an instance of a general design technique in- troduced by Okasaki  1998   called implicit recursive slowdown  We have already noted that these trees are an extension of his implicit deque structure  replacing pairs with 2-3 nodes to provide the flexibility required for efficient concatenation and splitting    A Finger Tree can be parameterized with a monoid  and using different monoids will result in different behaviors for the tree  This lets Finger Trees simulate other data structures

User · Answer

Work Stealing Queue  Lock-free data structure for dividing the work equaly among multiple threads Implementation of a work stealing queue in C C

User · Answer

Take a look at the sideways heap  presented by Donald Knuth   http   stanford-online stanford edu seminars knuth 071203-knuth-300 asx

User · Answer

I am not sure if this data structure has a name  but the proposed tokenmap data structure for inclusion into Boost is kind of interesting  It is a dynamically resizable map where look-ups are not only O 1   they are simple array accesses  I wrote most of the background material on this data structure which describes the fundamental principle behind how it works   Something like a tokenmap is used by operating systems to map file or resource handles to data structures representing the file or resource

User · Answer

Half edge data structure and winged edge for polygonal meshes   Useful for computational geometry algorithms

User · Answer

Bloom filter  Bit array of m bits  initially all set to 0    To add an item you run it through k hash functions that will give you k indices in the array which you then set to 1    To check if an item is in the set  compute the k indices and check if they are all set to 1    Of course  this gives some probability of false-positives  according to wikipedia it s about 0 61  m n  where n is the number of inserted items   False-negatives are not possible   Removing an item is impossible  but you can implement counting bloom filter  represented by array of ints and increment decrement

User · Answer

Pairing heaps are a type of heap data structure with relatively simple implementation and excellent practical amortized performance

User · Answer

Splay Trees are cool  They reorder themselves in a way that moves the most often queried elements closer to the root

User · Answer

Kd-Trees  spatial data structure used  amongst others  in Real-Time Raytracing  has the downside that triangles that cross intersect the different spaces need to be clipped  Generally BVH s are faster because they are more lightweight  MX-CIF Quadtrees  store bounding boxes instead of arbitrary point sets by combining a regular quadtree with a binary tree on the edges of the quads  HAMT  hierarchical hash map with access times that generally exceed O 1  hash-maps due to the constants involved  Inverted Index  quite well known in the search-engine circles  because it s used for fast retrieval of documents associated with different search-terms    Most  if not all  of these are documented on the NIST Dictionary of Algorithms and Data Structures

User · Answer

Binary decision diagram  my very favorite data structure  good for representing boolean equations  and solving them  Effective for a great lot of things  Heaps  a tree where the parent of a node always maintains some relation to the children of the node  for instance  the parent of a node is always greater than each of it s children  max-heap    Priority Queues  really just min-heaps and max-heaps  good for maintaining order of a lot of elements there the e g  the item with the highest value is supposed to be removed first  Hash tables   with all kinds of lookup strategies  and bucket overflow handling  Balanced binary search trees  Each of these have their own advantages    RB-trees  overall good  when inserting  lookup  removing and iterating in an ordered fashion  Avl-trees  faster for lookup than RB  but otherwise very similar to RB  Splay-trees  faster for lookup when recently used nodes are likely to be reused  Fusion-tree  Exploiting fast multiplication for getting even better lookup times  B Trees  Used for indexing in databases and file systems  very efficient when latency to read write from to the index is significant    Spatial indexes   Excellent for querying for whether points circles rectangles lines cubes is in close proximity to or contained within each other    BSP tree Quadtree Octree Range-tree Lots of similar but slightly different trees  and different dimensions  Interval trees  good finding overlapping intervals  linear  Graphs   adjacency list  basically a list of edges  adjacency matrix  a table representing directed edges of a graph with a single bit per edge  Very fast for graph traversal     These are the ones i can come to think of  There are even more on wikipedia about data structures

User · Answer

There is a clever Data-structure out there that uses Arrays to save the Data of the Elements  but the Arrays are linked together in an Linked-List Array   This does have the advantage that the iteration over the elements is very fast  faster than a pure linked-list approach  and the costs for moving the Arrays with the Elements around in Memory and or  de- allocation are at a minimum   Because of this this data-structure is usefull for Simulation stuff    I know about it from here   http   software intel com en-us blogs 2010 03 26 linked-list-verses-array       and that an additional array is allocated and linked in to the cell list of arrays of particles   This is similar in some respects to how TBB implemented its concurrent container   it is about ther Performance of Linked Lists vs  Arrays

User · Answer

Not really a data structure  more of a way to optimize dynamically allocated arrays  but the gap buffers used in Emacs are kind of cool

User · Answer

I really really love Interval Trees  They allow you to take a bunch of intervals  ie start end times  or whatever  and query for which intervals contain a given time  or which intervals were  active  during a given period  Querying can be done in O log n  and pre-processing is O n log n

User · Answer

It s pretty domain-specific  but half-edge data structure is pretty neat  It provides a way to iterate over polygon meshes  faces and edges  which is very useful in computer graphics and computational geometry

User · Answer

I like suffix tree and arrays for string processing  skip lists for balanced lists and splay trees for automatic balancing trees

User · Answer

PQ-Trees

User · Answer

A min-max heap is a variation of a heap that implements a double-ended priority queue  It achieves this by by a simple change to the heap property  A tree is said to be min-max ordered if every element on even  odd  levels are less  greater  than all childrens and grand children  The levels are numbered starting from 1   http   internet512 chonbuk ac kr datastructure heap img heap8 jpg

User · Answer

Tries  also known as prefix-trees or crit-bit trees  have existed for over 40 years but are still relatively unknown   A very cool use of tries is described in  TRASH - A dynamic LC-trie and hash data structure   which combines a trie with a hash function

User · Answer

I like Cache Oblivious datastructures   The basic idea is to lay out a tree in recursively smaller blocks so that caches of many different sizes will take advantage of blocks that convenient fit in them   This leads to efficient use of caching at everything from L1 cache in RAM to big chunks of data read off of the disk without needing to know the specifics of the sizes of any of those caching layers

User · Answer

Getting away from all these graph structures  I just love the simple Ring-Buffer    When properly implemented you can seriously reduce your memory footprint while maintaining performance and sometimes even improving it

User · Answer

Van Emde-Boas trees   I have even a C   implementation of it  for up to 2 20 integers

User · Answer

Fibonacci heaps  They re used in some of the fastest known algorithms  asymptotically  for a lot of graph-related problems  such as the Shortest Path problem   Dijkstra s algorithm runs in O E log V  time with standard binary heaps  using Fibonacci heaps improves that to O E   V log V   which is a huge speedup for dense graphs   Unfortunately  though  they have a high constant factor  often making them impractical in practice

User · Answer

Scapegoat trees   A classic problem with plain binary trees is that they become unbalanced  e g  when keys are inserted in ascending order    Balanced binary trees  AKA AVL trees  waste a lot of time balancing after each insertion   Red-Black trees stay balanced  but require a extra bit of storage for each node   Scapegoat trees stay balanced like red-black trees  but don t require ANY additional storage   They do this by analyzing the tree after each insertion  and making minor adjustments   See http   en wikipedia org wiki Scapegoat tree

User · Answer

Fast Compact tries    Judy arrays  Very fast and memory efficient ordered sparse dynamic arrays for bits  integers and strings  Judy arrays are faster and more memory efficient than any binary-search-tree  HAT-trie  A Cache-conscious Trie-based Data Structure for Strings B-tries for Disk-based String Management

User · Answer

lt zvrba gt  Van Emde-Boas trees   I think it d be useful to know why they re cool   In general  the question  why  is the most important to ask     My answer is that they give you O log log n  dictionaries with  1  n  keys  independent of how many of the keys are in use   Just like repeated halving gives you O log n   repeated sqrting gives you O log log n   which is what happens in the vEB tree

[language-agnostic] What are the lesser known but useful data structures?

Examples related to language-agnostic

Examples related to data-structures

Examples related to computer-science