大根堆/小根堆的实现

#include <iostream>
#include <vector>

using namespace std;

template<typename P>

class Heap {
private:
    vector<P> heap_elem{-1};//堆容器, 使得堆的编号从1开始
    int maxmin_heap;//选择大\小根堆

    void up_adjust(int now) {//上浮调整(默认大根堆)
        while (now > 1 && heap_elem[now] > heap_elem[now / 2]) {
            swap(heap_elem[now], heap_elem[now / 2]);
            now = now / 2;
        }
    };

    void down_adjust(P &top, int now) {//下沉调整
        heap_elem[now] = top;
        int next;
        while (now * 2 <= heap_elem.size() - 1) {
            if (now * 2 + 1 > heap_elem.size() - 1) {
                next = now * 2;
            } else {
                next = heap_elem[now * 2] > heap_elem[now * 2 + 1] ? now * 2 : now * 2 + 1;
            }
            if (heap_elem[next] > heap_elem[now]) {
                swap(heap_elem[next], heap_elem[now]);
                now = next;
            } else {
                break;
            }
        }
    };

public:
    Heap(int m) {//构造堆
        maxmin_heap = m;//default max_heap
    };

    P getTop() {//弹获取堆顶元素
        if (heap_elem.size() > 1)
            return heap_elem[1] * maxmin_heap;
        return heap_elem[0];//堆为空
    }

    bool empty() {//判断堆空
        return heap_elem.size() == 1;
    }

    void push(P x) {//送元素入堆
        heap_elem.push_back(x * maxmin_heap);
        int now = heap_elem.size() - 1;
        up_adjust(now);
    };

    P pop() {//堆顶元素弹出
        P res = getTop();
        P top = heap_elem.back();
        heap_elem.pop_back();
        int now = 1;
        down_adjust(top, now);
        cout << "pop " << res << " successfully." << endl;
        return res;
    };

    int size() {
        return heap_elem.size() - 1;
    }

    void print() {
        for (int i = 1; i < heap_elem.size(); i++) {
            cout << heap_elem[i] * maxmin_heap << ' ';
        }
        cout << endl;
    }

};

int main() {
    //Topk测试没问题
    int max_heap = 1, min_heap = -1;
    Heap<int> h(min_heap);//可更改为min_heap,来构建小根堆
    int x;
    for (int i = 0; i < 10; ++i) {
        x = rand() % 100;
        h.push(x);
        cout << "x: " << x << endl;
        h.print();
    }
    h.pop();
    h.print();
    return 0;
}

 

0