A lazy heap: insert, union and decrease-key in O(1) amortized, with the tidying left to extractMin. Marks, cuts and cascading cuts keep the trees bushy.
This interactive visualization needs JavaScript.