This makes the clear method linear in the size of the heap and adds a new method for adding elements without updating the heap. The use case is that I want to re-use a single heap several times as the keys are significantly larger than the size of the heap. Between the uses, I clear the heap and this should be linear in the number of remaining elements. I recognize that a simple linear fill is faster than random writes. Therefore, this only uses the random writes if we do not touch all cache lines with the random writes even if every write is on a separate cache line. I have not compared the performance and I'm also open to other suggestions. For adding new elements after the clear, I added the push_without_update method. It is very similar to the build_heap methods, just that it allows adding elements one-by-one and one has to call update_all (or clear) at the end. I have kept the update of the handles even though it is not strictly necessary as this ensures that contains can be used in between push_without_update calls. I have not added a push_without_update method that moves the key as the documentation states that key_type "has to be an unsigned integer type" and I cannot imagine that moving unsigned integers has any advantage over a pass by value or pass by reference.