Queue insertion for WFQ is typically a sort algorithm (actually, it depends on the interleave of the arrival processes - if they are loosely synchronised, then it is possible that one may only rarely have to do more than a few swaps).
Hui Zhang's work has shows that for CBR (Guaranteed Service in Integrated Service Internet Terminology), a different queueing algorithm called Worst Case Fair Weighted Fair Queueing achieves better delay jitter bounds, and yet can have O(1) insertion time.