2-3 heap
Encyclopedia
In computer science
, a 2-3 heap is a data structure
, a variation on the heap
, designed by Tadao Takaoka in 1999. The structure is similar to the Fibonacci heap
, and borrows from the 2-3 tree
.
Time costs for some common heap operations:
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a 2-3 heap is a data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
, a variation on the heap
Heap (data structure)
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key ≥ key. This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap...
, designed by Tadao Takaoka in 1999. The structure is similar to the Fibonacci heap
Fibonacci heap
In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987...
, and borrows from the 2-3 tree
2-3 tree
In computer science, a 2-3 tree is a type of data structure, a tree where every node with children has either two children and one data element or three children and two data elements...
.
Time costs for some common heap operations:
- delete-min takes
amortized time - decrease-key takes constant amortized time
- insertion takes constant amortized time.