#ifndef __GBLIBCPP_ALGORITHM__ #define __GBLIBCPP_ALGORITHM__ #include #include #include #include namespace std { template constexpr void make_heap(RandomIter first, RandomIter last, Compare comp) { auto len = last - first; if (len < 2) return; auto idx = len / 2 - 1; for (;;) { auto& val = first[idx]; auto left = idx * 2 + 1; auto right = left + 1; if (right < len) { auto& left_val = first[left]; auto& right_val = first[right]; if (comp(left_val, right_val)) { if (comp(val, right_val)) { std::swap(val, right_val); idx = right; continue; } } else { if (comp(val, left_val)) { std::swap(val, left_val); idx = left; continue; } } } else if (left < len) { auto& left_val = first[left]; if (comp(val, left_val)) { std::swap(val, left_val); idx = left; continue; } } if (idx == 0) break; --idx; } } template constexpr void make_heap(RandomIter first, RandomIter last) { make_heap(first, last, std::less>()); } template constexpr void push_heap(RandomIter first, RandomIter last, Compare comp) { auto len = last - first; if (len < 2) return; auto idx = len - 1; for (;;) { auto parent = (idx - 1) / 2; if (parent == idx) break; auto& val = first[idx]; auto& parent_val = first[parent]; if (comp(parent_val, val)) { std::swap(val, parent_val); idx = parent; continue; } break; } } template constexpr void push_heap(RandomIter first, RandomIter last) { push_heap(first, last, std::less>()); } template constexpr void pop_heap(RandomIter first, RandomIter last, Compare comp) { auto len = last - first; if (len < 2) return; std::swap(first[0], first[len - 1]); auto idx = 0; for (;;) { auto& val = first[idx]; auto left = idx * 2 + 1; auto right = left + 1; if (right < len - 1) { auto& left_val = first[left]; auto& right_val = first[right]; if (comp(left_val, right_val)) { if (comp(val, right_val)) { std::swap(val, right_val); idx = right; continue; } } else { if (comp(val, left_val)) { std::swap(val, left_val); idx = left; continue; } } } else if (left < len - 1) { auto& left_val = first[left]; if (comp(val, left_val)) { std::swap(val, left_val); idx = left; continue; } } if (idx == 0) break; --idx; } } template constexpr void pop_heap(RandomIter first, RandomIter last) { pop_heap(first, last, std::less>()); } template constexpr void sort(RandomIter first, RandomIter last, Compare comp) { auto len = last - first; std::make_heap(first, last, comp); for (auto i = len - 1; i > 0; --i) { std::swap(first[0], first[i]); auto idx = 0; for (;;) { auto& val = first[idx]; auto left = idx * 2 + 1; auto right = left + 1; if (right < i) { auto& left_val = first[left]; auto& right_val = first[right]; if (comp(left_val, right_val)) { if (comp(val, right_val)) { std::swap(val, right_val); idx = right; continue; } } else { if (comp(val, left_val)) { std::swap(val, left_val); idx = left; continue; } } } else if (left < i) { auto& left_val = first[left]; if (comp(val, left_val)) { std::swap(val, left_val); idx = left; continue; } } if (idx == 0) break; --idx; } } } template constexpr void sort(RandomIter first, RandomIter last) { sort(first, last, std::less>()); } template constexpr const T& min(const T& a, const T& b) { return a < b ? a : b; } template constexpr const T& max(const T& a, const T& b) { return a > b ? a : b; } } // namespace std #endif