Sort a $d$-sorted array
Since your heap contains $d$ elements, every operation takes take $O(\log d)$, for a total running time of $O(n\log d)$.
When $d$ is constant, this is $O(n)$, and when $d = O(\log n)$, this is $O(n\log\log n)$.
For a matching $\Omega(n\log d)$ lower bound, see this question.