A heap with d children per node, in one array: inserts get cheaper as d grows, extracts get costlier, and decrease-key climbs fewer levels.
This interactive visualization needs JavaScript.