Comparison of data structures
This is a comparison of the performance of notable data structures, as measured by the complexity of their logical operations. For a more comprehensive listing of data structures, see List of data structures. The comparisons in this article are organized by abstract data type. As a single concrete data structure may be used to implement many abstract data types, some data structures may appear in multiple comparisons (for example, a hash map can be used to implement an associative array or a set).
Lists
A list or sequence is an abstract data type that represents a finite number of ordered values, where the same value may occur more than once. Lists generally support the following operations:
- peek: access the element at a given index.
- insert: insert a new element at a given index. When the index is zero, this is called prepending; when the index is the last index in the list it is called appending.
- delete: remove the element at a given index.
| Linked list | Array | Dynamic array | Balanced tree | Random access list | Hashed array tree | |
|---|---|---|---|---|---|---|
| Indexing | Θ(n) | Θ(1) | Θ(1) | Θ(log n) | Θ(log n)[1] | Θ(1) |
| Insert/delete at beginning | Θ(1) | N/A | Θ(n) | Θ(log n) | Θ(1) | Θ(n) |
| Insert/delete at end | Θ(1) when last element is known; Θ(n) when last element is unknown |
N/A | Θ(1) amortized | Θ(log n) | Θ(log n) updating | Θ(1) amortized |
| Insert/delete in middle | search time + Θ(1)[2][3] | N/A | Θ(n) | Θ(log n) | Θ(log n) updating | Θ(n) |
| Wasted space (average) | Θ(n) | 0 | Θ(n)[4] | Θ(n) | Θ(n) | Θ(√n) |
Maps
Maps store a collection of (key, value) pairs, such that each possible key appears at most once in the collection. They generally support three operations:[5]
- Insert: add a new (key, value) pair to the collection, mapping the key to its new value. Any existing mapping is overwritten. The arguments to this operation are the key and the value.
- Remove: remove a (key, value) pair from the collection, unmapping a given key from its value. The argument to this operation is the key.
- Lookup: find the value (if any) that is bound to a given key. The argument to this operation is the key, and the value is returned from the operation.
Unless otherwise noted, all data structures in this table require O(n) space.
| Data structure | Lookup, removal | Insertion | Ordered | ||
|---|---|---|---|---|---|
| average | worst case | average | worst case | ||
| Association list | O(n) | O(n) | O(1) | O(1) | No |
| B-tree[6] | O(log n) | O(log n) | O(log n) | O(log n) | Yes |
| Hash table | O(1) | O(n) | O(1) | O(n) | No |
| Unbalanced binary search tree | O(log n) | O(n) | O(log n) | O(n) | Yes |
Integer keys
Some map data structures offer superior performance in the case of integer keys. In the following table, let m be the number of bits in the keys.
| Data structure | Lookup, removal | Insertion | Space | ||
|---|---|---|---|---|---|
| average | worst case | average | worst case | ||
| Fusion tree | O(log m n) | O(n) | |||
| Van Emde Boas tree | O(log log m) | O(log log m) | O(log log m) | O(log log m) | O(m) |
| X-fast trie | O(n log m)[lower-alpha 1] | O(log log m) | O(log log m) | O(n log m) | |
| Y-fast trie | O(log log m)[lower-alpha 1] | O(log log m)[lower-alpha 1] | O(n) | ||
Priority queues
A priority queue is an abstract data-type similar to a regular queue or stack. Each element in a priority queue has an associated priority. In a priority queue, elements with high priority are served before elements with low priority. Priority queues support the following operations:
- insert: add an element to the queue with an associated priority.
- find-max: return the element from the queue that has the highest priority.
- delete-max: remove the element from the queue that has the highest priority.
Priority queues are frequently implemented using heaps.
Heaps
A (max) heap is a tree-based data structure which satisfies the Template:Dfni: for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C.
In addition to the operations of an abstract priority queue, the following table lists the complexity of two additional logical operations:
- increase-key: updating a key.
- meld: joining two heaps to form a valid new heap containing all the elements of both, destroying the original heaps.
Here are time complexities[7] of various heap data structures. Function names assume a min-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.
| Operation | find-min | delete-min | insert | decrease-key | meld |
|---|---|---|---|---|---|
| Binary[7] | Θ(1) | Θ(log n) | O(log n) | O(log n) | Θ(n) |
| Leftist | Θ(1) | Θ(log n) | Θ(log n) | O(log n) | Θ(log n) |
| Binomial[7][8] | Θ(1) | Θ(log n) | Θ(1)[lower-alpha 1] | Θ(log n) | O(log n)[lower-alpha 2] |
| Fibonacci[7][9] | Θ(1) | O(log n)[lower-alpha 1] | Θ(1) | Θ(1)[lower-alpha 1] | Θ(1) |
| Pairing[10] | Θ(1) | O(log n)[lower-alpha 1] | Θ(1) | o(log n)[lower-alpha 1][lower-alpha 3] | Θ(1) |
| Brodal[13][lower-alpha 4] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
| Rank-pairing[15] | Θ(1) | O(log n)[lower-alpha 1] | Θ(1) | Θ(1)[lower-alpha 1] | Θ(1) |
| Strict Fibonacci[16] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
| 2-3 heap[17] | O(log n) | O(log n)[lower-alpha 1] | O(log n)[lower-alpha 1] | Θ(1) | ? |
- ↑ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 Amortized time.
- ↑ n is the size of the larger heap.
- ↑ Lower bound of [math]\displaystyle{ \Omega(\log\log n), }[/math][11] upper bound of [math]\displaystyle{ O(2^{2\sqrt{\log\log n}}). }[/math][12]
- ↑ Brodal and Okasaki later describe a persistent variant with the same bounds except for decrease-key, which is not supported. Heaps with n elements can be constructed bottom-up in O(n).[14]
Notes
- ↑ Chris Okasaki (1995). "Purely Functional Random-Access Lists". Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture: 86-95. doi:10.1145/224164.224187.
- ↑ Day 1 Keynote - Bjarne Stroustrup: C++11 Style at GoingNative 2012 on channel9.msdn.com from minute 45 or foil 44
- ↑ Number crunching: Why you should never, ever, EVER use linked-list in your code again at kjellkod.wordpress.com
- ↑ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09), Department of Computer Science, University of Waterloo, http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf
- ↑ Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", Algorithms and Data Structures: The Basic Toolbox, Springer, pp. 81–98, http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf
- ↑ Cormen et al. 2022, p. 484.
- ↑ 7.0 7.1 7.2 7.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
- ↑ "Binomial Heap | Brilliant Math & Science Wiki" (in en-us). https://brilliant.org/wiki/binomial-heap/.
- ↑ Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the Association for Computing Machinery 34 (3): 596-615. doi:10.1145/28869.28874. http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Fibonacci-Heap-Tarjan.pdf.
- ↑ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, 1851, Springer-Verlag, pp. 63–77, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2, http://john2.poly.edu/papers/swat00/paper.pdf
- ↑ Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures". Journal of the Association for Computing Machinery 46 (4): 473–501. doi:10.1145/320211.320214. http://www.uqac.ca/azinflou/Fichiers840/EfficiencyPairingHeap.pdf.
- ↑ Pettie, Seth (2005). "Towards a Final Analysis of Pairing Heaps". FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0. http://web.eecs.umich.edu/~pettie/papers/focs05.pdf.
- ↑ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues", Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58, http://www.cs.au.dk/~gerth/papers/soda96.pdf
- ↑ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338-341. ISBN 0-471-46983-1.
- ↑ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps". SIAM J. Computing 40 (6): 1463–1485. doi:10.1137/100785351. http://sidsen.org/papers/rp-heaps-journal.pdf.
- ↑ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). "Strict Fibonacci heaps". Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5. http://www.cs.au.dk/~gerth/papers/stoc12.pdf.
- ↑ Takaoka, Tadao (1999), Theory of 2–3 Heaps, pp. 12, https://ir.canterbury.ac.nz/bitstream/handle/10092/14769/2-3heaps.pdf
References
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022-04-05) (in en). Introduction to Algorithms, fourth edition. MIT Press. ISBN 978-0-262-36750-9. https://books.google.com/books?id=RSMuEAAAQBAJ&dq=cormen+algorithms&pg=PR13.
 |  |
