In computer science, a 2–3 heap is a data structure that implements a priority queue. It is a variation on the heap, designed by Tadao Takaoka in 1999. The structure is similar to a Fibonacci heap, and borrows ideas from the 2–3 tree.
The time needed for some common heap operations are as follows.
- Delete-min takes <math>O(\log(n))</math> amortized time and in the worst case.
- Decrease-key takes constant amortized time.
- Insertion takes constant amortized time and <math>O(\log(n))</math> time in the worst case.
Polynomial of trees
Source:
A linear tree of size <math>r</math> is a sequential path of <math>r</math> nodes with the first node as a root of the tree and it is represented by a bold <math>\mathbf{r}</math> (e.g. <math>\mathbf{1}</math> is a linear tree of a single node). Product <math>P = ST</math> of two trees <math>S</math> and <math>T</math>, is a tree produced by replacing every node of <math>S</math> by a copy of <math>T</math>; for each edge of <math>S</math>, there is an edge in <math>ST</math> connecting the roots of the trees that replaced the endpoints of the edge. This definition of product is associative but not commutative. The sum <math>S+T</math> of two trees <math>S</math> and <math>T</math> is the forest of the two trees <math>S</math> and <math>T</math>.
The operation <math>\triangleleft</math> on trees <math>S,T</math> is defined as follows. The tree <math>L = S \triangleleft T</math> is produced by linking the root of the tree <math>T</math> as a child of the root of tree <math>S</math>. Now consider the linear tree <math>\mathbf{r}</math>. The tree <math>\mathbf{r}^{i}</math> is defined by combining r copies of <math>\mathbf{r}^{i-1}</math> as follows:
<math>\mathbf{r}^i = \mathbf{r}^{i - 1} \triangleleft \mathbf{r}^{i - 1} \triangleleft \dots \triangleleft \mathbf{r}^{i - 1}</math> (evaluated right to left).
The path created from this linking forms the <math>i</math>th trunk of <math>\mathbf{r}^{i}</math> which can also be called the <math>i</math>th dimension of the tree.
An r-ary polynomial of trees is defined as <math>P = \mathbf{a}_{k-1}\mathbf{r}^{k-1} + \dots + \mathbf{a}_1\mathbf{r} + \mathbf{a}_0</math> where <math>0 \leq a_i \leq r-1</math>. This polynomial notation for trees of <math>n</math> nodes is unique. The tree <math>\mathbf{a}_i\mathbf{r}^i</math> consists of <math>a_i</math> copies of <math>\mathbf{r}^i</math> such that their roots are connected with <math>a_i-1</math> edges sequentially. The path of these <math>a_i-1</math> edges is called the main trunk of the tree <math>\mathbf{a}_i\mathbf{r}^i</math>. Furthermore, an r-ary polynomial of trees is called an r-nomial queue if nodes of the polynomial of trees are associated with keys satisfying the heap property.
thumb|A polynomial heap, in fact a (2,3) heap with a dimension representation of its trees
Operations on r-nomial queues
To merge two terms of form <math>\mathbf{a}_i \mathbf{r}^i</math> and <math>\mathbf{a}'_i \mathbf{r}^i</math>, the trees are reordered in the main trunk based on the keys in the root of trees. If <math>a_i + a'_i \geq r</math> there will be a term of form <math>(\mathbf{a}_i+\mathbf{a}'_i-\mathbf{r}) \mathbf{r}^i</math> and a carry tree <math>\mathbf{r}^{i+1}</math>. Otherwise, there is only a tree <math>(\mathbf{a}_i+\mathbf{a}'_i) \mathbf{r}^i</math>. The sum of two r-nomial queues are similar to the addition of two number in base <math>r</math>.
An insertion of a key into a polynomial queue is like merging a single node with the label of the key into the existing r-nomial queue, taking <math>O(r \log_r{n})</math> time.
A delete operation of the minimum is done by finding the minimum in the root of a tree, say <math>T</math> and deleting it. The resulting polynomial queue <math>Q</math> is added back to <math>P-T</math> in total time <math>O(r \log_r{n})</math>.
(2,3)-heap
Source: