Editing 2–3 heap (section)

=== 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>.