MCPcopy Create free account
hub / github.com/HelenOS/helenos / correct_children

Function correct_children

uspace/lib/cpp/include/__bits/algorithm.hpp:880–913  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

878
879 template<class RandomAccessIterator, class Size, class Compare>
880 void correct_children(RandomAccessIterator first,
881 Size idx, Size count, Compare comp)
882 {
883 using aux::heap_left_child;
884 using aux::heap_right_child;
885
886 auto left = heap_left_child(idx);
887 auto right = heap_right_child(idx);
888
889 bool left_incorrect{comp(first[idx], first[left])};
890 bool right_incorrect{comp(first[idx], first[right])};
891 while ((left < count && left_incorrect) ||
892 (right < count && right_incorrect))
893 {
894 if (right >= count || (left_incorrect && comp(first[right], first[left])))
895 {
896 swap(first[idx], first[left]);
897
898 idx = left;
899 }
900 else if (right < count && right_incorrect)
901 {
902 swap(first[idx], first[right]);
903
904 idx = right;
905 } // Else should not happen because of the while condition.
906
907 left = heap_left_child(idx);
908 right = heap_right_child(idx);
909
910 left_incorrect = comp(first[idx], first[left]);
911 right_incorrect = comp(first[idx], first[right]);
912 }
913 }
914 }
915
916 /**

Callers 2

pop_heapFunction · 0.85
make_heapFunction · 0.85

Calls 3

heap_left_childFunction · 0.85
heap_right_childFunction · 0.85
swapFunction · 0.50

Tested by

no test coverage detected