- #include <iostream>
- #include <functional> //for std::less
- #include <utility> //for std::swap
- #include <type_traits>
- template <typename T, size_t N>
- void print(T(&array)[N])
- {
- for (auto e: array) {
- std::cout <<e<<"\\t";
- }
- std::cout <<"\\n";
- }
- template <typename It>
- void print(It beg, It end)
- {
- for (;beg < end;++ beg) {
- std::cout <<*beg<<"\\t";
- }
- std::cout <<"\\n";
- }
- inline ssize_t lchild(ssize_t pos)
- {
- //array start as 0, so left child should add 1.
- return (pos << 1) + 1;
- }
- template <typename It, typename Cmp, typename T = typename std::iterator_traits<It>::value_type>
- void percDown(It beg, ssize_t len, ssize_t pos, Cmp cmp)
- {
- T ins = *(beg + pos);
- for (ssize_t child = 0;lchild(pos) < len; pos = child) {
- child = lchild(pos);
- if (child != len - 1 && cmp(*(beg + child), *(beg + child + 1))) {
- child ++;
- }
- if (cmp(ins, *(beg + child))) {
- *(beg + pos) = *(beg + child);
- } else {
- break;
- }
- }
- *(beg + pos) = ins;
- }
- template <typename It, typename Cmp = std::less<typename std::iterator_traits<It>::value_type>>
- void heapSort(It beg, It end, Cmp cmp = Cmp())
- {
- if (beg == end) return ;
- //use signed size_t
- ssize_t len = end - beg;
- //build heap
- for (ssize_t i = len / 2;i >= 0;i --) {
- percDown(beg, len, i, cmp);
- }
- //sort
- for (ssize_t i = len - 1;i > 0;i --) {
- std::swap(*beg, *(beg + i)); // delete min or max
- percDown(beg, i, 0, cmp);
- }
- }
- int main()
- {
- int array[] = {1, 10, 5, 3, 4, 41, 8, 9, 11};
- std::cout <<"Before:\\n";
- print(array);
- heapSort(array, array + 9);
- std::cout <<"After:\\n";
- print(array);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/0501201614359.html
来源: http://www.codesnippet.cn/detail/0501201614359.html