手写堆求调

Ruiqun2009 @ 2023-01-06 10:52:19

by Ruiqun2009 @ 2023-01-06 10:52:26

#include <cstdio>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cmath>
#define LEFT_SON(p) (p << 1 | 1)
#define RIGHT_SON(p) ((p + 1) << 1)
#define PARENT(p) ((p - 1) >> 1)

template <typename _RandomAccessIterator, typename _Diff, typename _Comp>
inline void min_heap_adjust(_RandomAccessIterator __first, _RandomAccessIterator __last,
    _Diff __index, _Comp comp) {
    _Diff siz = __last - __first;
    _Diff tar = LEFT_SON(__index);
    while (tar < siz) {
        _RandomAccessIterator child = __first + tar;
        if (tar < siz - 1) {
            if (comp(*(child + 1), *child)) {
                ++tar;
                ++child;
            }
        }
        if (comp(*child, *(__first + __index))) std::iter_swap(__first + __index, child);
        else break;
        __index = tar;
        tar = LEFT_SON(__index);
    }
}
template <typename _RandomAccessIterator, typename _Comp>
inline void pop_min_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
    --__last;
    std::iter_swap(__first, __last);
    min_heap_adjust(__first, __last, 0, comp);
}
template <typename _RandomAccessIterator, typename _Comp>
inline void push_min_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
    typedef typename std::iterator_traits< _RandomAccessIterator>::difference_type _Diff;
    _Diff pos = (__last - __first) - 1;
    while (pos && comp(*(__first + pos), *(__first + PARENT(pos)))) {
        std::iter_swap(__first + pos, __first + PARENT(pos));
        pos = PARENT(pos);
    }
}
template <typename _RandomAccessIterator, typename _Comp>
inline void make_min_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
    typedef typename std::iterator_traits< _RandomAccessIterator>::difference_type _Diff;
    _Diff siz = __last - __first;
    _Diff parent = PARENT(siz);
    while (true) {
        min_heap_adjust(__first, __last, parent, comp);
        if (!parent) return;
        --parent;
    }
}

template <typename _RandomAccessIterator, typename _Diff, typename _Comp>
inline void max_heap_adjust(_RandomAccessIterator __first, _RandomAccessIterator __last,
    _Diff __index, _Comp comp) {
    _Diff siz = __last - __first;
    _Diff tar = LEFT_SON(__index);
    while (tar < siz) {
        _RandomAccessIterator child = __first + tar;
        if (tar < siz - 1) {
            if (comp(*child, *(child + 1))) {
                ++tar;
                ++child;
            }
        }
        if (comp(*(__first + __index), *child)) std::iter_swap(__first + __index, child);
        else break;
        __index = tar;
        tar = LEFT_SON(__index);
    }
}
template <typename _RandomAccessIterator, typename _Comp>
inline void pop_max_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
    --__last;
    std::iter_swap(__first, __last);
    max_heap_adjust(__first, __last, 0, comp);
}
template <typename _RandomAccessIterator, typename _Comp>
inline void push_max_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
    typedef typename std::iterator_traits< _RandomAccessIterator>::difference_type _Diff;
    _Diff pos = (__last - __first) - 1;
    while (pos && comp(*(__first + PARENT(pos)), *(__first + pos))) {
        std::iter_swap(__first + pos, __first + PARENT(pos));
        pos = PARENT(pos);
    }
}
template <typename _RandomAccessIterator, typename _Comp>
inline void make_max_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
    typedef typename std::iterator_traits< _RandomAccessIterator>::difference_type _Diff;
    _Diff siz = __last - __first;
    _Diff parent = PARENT(siz);
    while (true) {
        max_heap_adjust(__first, __last, parent, comp);
        if (!parent) return;
        --parent;
    }
}
#undef LEFT_SON
#undef RIGHT_SON
#undef PARENT
std::vector<unsigned> lq, gq;
std::less<unsigned> comp;
int main() {
    int n;
    unsigned x;
    scanf("%d%u", &n, &x);
    lq.reserve(n / 2 + 1);
    gq.reserve(n / 2 + 1);
    lq.push_back(x);
    printf("%u\n", x);
    for (int i = 2; i <= n; i++) {
        scanf("%u", &x);
        if (x > lq[0]) {
            gq.push_back(x);
            push_min_heap(gq.begin(), gq.end(), comp);
        }
        else {
            lq.push_back(x);
            push_max_heap(lq.begin(), lq.end(), comp);
        }
        while (abs((int)lq.size() - (int)gq.size()) > 1) {
            if (lq.size() > gq.size()) {
                gq.push_back(lq[0]);
                pop_max_heap(lq.begin(), lq.end(), comp);
                lq.pop_back();
            }
            else {
                lq.push_back(gq[0]);
                pop_min_heap(gq.begin(), gq.end(), comp);
                gq.pop_back();
            }
        }
        if (i & 1) printf("%u\n", lq.size() > gq.size() ? lq[0] : gq[0]);
    }
}

by Sprague_Garundy @ 2023-01-06 10:58:34

《手写堆》你怕不是哪个地方贺的源码

by Ruiqun2009 @ 2023-01-06 11:03:55

@Sprague_Garundy 是我自己写的。你自己看 bits/stl_heap.h 会发现完全不一样。

by C_liar @ 2023-01-06 11:04:45

@Sprague_Garundy 这是大佬，重工业选手，人就习惯这么写QwQ

by Ruiqun2009 @ 2023-01-06 11:30:25

我是那*，push 的时候没有 push_heap

此贴结