The current implementation of Heap.insert(contentsOf:) simply iterates over newElements, individually inserting them into the heap, one by one.
This can sometimes be quite inefficient, as it has quasilinear O(n * log(n)) complexity. If we have more than a handful of items to insert, it would be better to just append them to the storage array and re-run Floyd's heap construction algorithm on the entire resulting storage, which would take linear O(n) complexity.
Fix insert(contentsOf:) to switch between the naive loop and Floyds, based on some heuristic function defined over the size of the original heap and the length of the appended sequence. A small back-of-the-envelope calculation implies one possible heuristic would be to switch to using Floyd whenever the number of new items k is greater than 2 * (n + k) / log(n + k).
The current implementation of
Heap.insert(contentsOf:)simply iterates overnewElements, individually inserting them into the heap, one by one.This can sometimes be quite inefficient, as it has quasilinear O(n * log(n)) complexity. If we have more than a handful of items to insert, it would be better to just append them to the storage array and re-run Floyd's heap construction algorithm on the entire resulting storage, which would take linear O(n) complexity.
Fix
insert(contentsOf:)to switch between the naive loop and Floyds, based on some heuristic function defined over the size of the original heap and the length of the appended sequence. A small back-of-the-envelope calculation implies one possible heuristic would be to switch to using Floyd whenever the number of new itemskis greater than2 * (n + k) / log(n + k).rdar://118373784