sift_down()

template<typename Iterator, typename Compare>

void fl::detail::sift_down	(	Iterator	first,
		Iterator	start,
		Iterator	end,
		Compare	comp )

Definition at line 300 of file algorithm.h.

                                                                           {
    Iterator root = start;
    
    while (root - first <= (end - first - 2) / 2) {
        Iterator child = first + 2 * (root - first) + 1;
        Iterator swap_iter = root;
        
        if (comp(*swap_iter, *child)) {
            swap_iter = child;
        }
        
        if (child + 1 <= end && comp(*swap_iter, *(child + 1))) {
            swap_iter = child + 1;
        }
        
        if (swap_iter == root) {
            return;
        } else {
            swap(*root, *swap_iter);
            root = swap_iter;
        }
    }
}

References fl::end(), and fl::swap().

Referenced by heap_sort(), and heapify().

Here is the call graph for this function:

Here is the caller graph for this function: