2–3 heap
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 are: Polynomial of trees. A linear tree of size formula_2 is a sequential path of formula_2 nodes with the first node as a root of the tree and it is represented by a bold formula_4 (e.g. formula_5 is a linear tree of a single node). Product formula_6 of two trees formula_7 and formula_8, is a new  tree with every node of formula_7 is replaced by a copy of formula_8 and for each edge of formula_7 we connect the roots of the trees corresponding to the endpoints of the edge. Note that this definition of product is associative but not commutative. Sum formula_12 of two trees formula_7 and formula_8 is the collection of two trees formula_7 and formula_8. An r-ary polynomial of trees is defined as formula_17 where formula_18. This polynomial notation for trees of formula_19 nodes is unique. The tree formula_20 is actually formula_21 copy of formula_22 that their roots are connected with formula_23 edges  sequentially and the path of these formula_23 edge is called the main trunk of the tree formula_20. Furthermore, an r-ary polynomial of trees is called an r-nomial queue if nodes of the polynomial of trees are associated with keys in heap property. Operations on r-nomial queues. To merge two terms of form formula_26 and formula_27, we just reorder the trees in the main trunk based on the keys in the root of trees. If formula_28 we will have a term of form formula_29 and a carry tree formula_30. Otherwise, we would have only a tree formula_31. So  the sum of two r-nomial queues are actually similar to the addition of two number in base formula_2. 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 formula_33 time. To delete the minimum, first, we need to find the minimum in the root of a tree, say formula_8, then we delete the minimum from formula_8 and we add the resulting polynomial queue formula_36 to formula_37 in total time formula_33. Section::::(2,3)-heap. An formula_39 tree formula_40 is defined recursively by formula_41 for  formula_42 (formula_43 is between formula_44 and formula_2 and formula_46 formula_47 operations are evaluated from right to left) where for two trees, formula_48 and formula_49, the result of the operationformula_50 is connecting the root of formula_51 as a rightmost child to the root of formula_48 and formula_53 is a single node tree. Note that the root of the tree formula_40 has degree formula_55. An extended polynomial of trees, formula_56, is defined by formula_57. If we assign keys into the nodes of an extended polynomial of trees in heap order it is called formula_58, and the special case of formula_59 and formula_60  is called formula_61. Operations on (2,3)-heap. Delete-min: First of all, we find the minimum by scanning the root of the trees. Let formula_40 be the tree containing minimum element and let formula_36 be the result of removing root from formula_40. Then we merge formula_65 and formula_36 (The merge operation is similar to merge of two r-nomial queues). Insertion: In order to insert a new key, we merge the currently existing (2,3)-heap with a single node tree, formula_67 labeled with this key. Decrease Key: To be done!