Use a forest of 2-4 trees in which the keys are at the leaves. Every internal node contains a copy of the minimum key that descends from it as well as a positive integer indicating the number of values of this key descending from it.

Additionally, maintain a van Emde Boas tree containing as keys each positive integers $i$ where $i$ is the minimum element in a 2-4 tree. In the vEB tree, each one integer has satellite data: a pointer to the root of the tree it is in.

1. $Split$ is the normal split on 2-4 trees, updating the internal node data as it proceeds. This takes logarithmic time in the size of the tree being split, while update the vEB tree takes time corresponding to the logarithm of the logarithm of the number of trees in the forest.

2. $FindMin$, which now returns the $l$ smallest keys, does a breadth-first search down the tree containing the element in question. Starting from the root, this takes time linear in $l$. To find the root from the element, access the vEB tree, find the predecessor, then follow the pointer to that root.

3. $DecreaseKey$ modifies a single 2-4 tree, taking time logarithmic in the size of that tree.

Each $Split$ uses $O(\log \log n)$ time for the vEB operation and $O(\log n)$ key comparisons. Each $FindMin$ uses $O(\log \log n)$ time for the vEB operation and $O(l)$ key comparisons. Each $DecreaseKey$ uses $O(\log n)$ key comparisons.

Use a forest of 2-4 trees in which the keys are at the leaves. Every internal node contains a copy of the minimum key that descends from it as well as a positive integer indicating the number of values of this key descending from it.

Additionally, maintain a van Emde Boas tree containing as keys each positive integer $i$ where $e_i$ is the left-most element in one of the 2-4 trees. In the vEB tree, each integer $i$ has satellite data: a pointer to the root of the tree the key associated with $e_i$ is in.

1. $Split$ is the normal split on 2-4 trees, updating the internal node data as it proceeds. This takes logarithmic time in the size of the tree being split, while updating the vEB tree takes time corresponding to the logarithm of the logarithm of the number of trees in the forest.

2. $FindMin$, which now returns the $l$ smallest keys, does a breadth-first search down the tree containing the element in question. Starting from the root, this takes time linear in $l$. To find the root from the element, access the vEB tree, find the predecessor, then follow the pointer to that root.

3. $DecreaseKey$ modifies a single 2-4 tree, taking time logarithmic in the size of that tree.

Each $Split$ uses $O(\log \log n)$ time for the vEB operation and $O(\log n)$ key comparisons. Each $FindMin$ uses $O(\log \log n)$ time for the vEB operation and $O(l)$ key comparisons. Each $DecreaseKey$ uses $O(\log n)$ key comparisons.