make_heap should be vectorizable, that would be more useful. I can also see a path to vectorize bulk insert, but that seems harder.

I don't believe it's possible to vectorize the classic heap.

I've seen vectorized and SIMD heap implementations. They are a different data structure entirely. You basically work with 16-sorted items and then sort your working set (16-items) with any node, allowing you to generalize the push down or push up operations of a heap. (Sort both lists. Top16 make a node and stay here. Bottom16 push down and recurse).

This is very very similar to a classic heap but you need a lot of operations so that you have enough work to SIMD.

Sorting is after all, a highly parallelized operation (Bionic Sort, MergePath, etc) and is a good basis for generalizing single threaded data structures into a multi thread or SIMD version.