[C++知识库]堆__C++泛型实现简易的优先队列

堆__C++泛型实现简易的优先队列

1. 最近复习优先队列时，想到了使用泛型的方法来进行实现，泛型可以灵活的调整优先队列排序的方法和容纳的数据类型，这里小小的分享一下：

template<typename T>
class Less {
public:
    bool operator()(const T& a, const T& b) {
        return a < b;
    }
};

template<typename T>
class Greater {
public:
    bool operator()(const T& a, const T& b) {
        return a > b;
    }
};

template<typename T, typename ORD = Less<T>>
class PriQueue {
private:
    vector<T> vi_;

private:

    void swim(int pos) {
        while (pos > 1 && ORD()(vi_[pos / 2], vi_[pos])) {
            swap(vi_[pos], vi_[pos / 2]);
            pos /= 2;
        }
    }

    void sink(int pos) {
        while (pos * 2 <= vi_.size() - 1) {
            int i = pos * 2;
            if (i < vi_.size() - 1 && ORD()(vi_[i], vi_[i + 1])) i++;
            if (ORD()(vi_[i], vi_[pos])) break;
            swap(vi_[i], vi_[pos]);
            pos = i;
        }
    }

public:

    PriQueue() {
        vi_.push_back(INT_MIN);
    }

    void push(T a) {
        vi_.push_back(a);
        swim(vi_.size() - 1);
    }

    T top() {
        if (vi_.size() > 1) {
            return vi_[1];
        }
        return INT_MIN;
    }

    void pop() {
        vi_[1] = vi_[vi_.size() - 1];
        vi_.pop_back();
        sink(1);
    }

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

2. 下面是简单的测试函数

void test2() {
    PriQueue<int, Less<int>> pq;
    pq.push(2);
    pq.push(1);
    pq.push(3);

    while (pq.size()) {
        cout << pq.top() << endl;
        pq.pop();
    }
    cout << endl;

    PriQueue<int, Greater<int>> pq2;
    pq2.push(2);
    pq2.push(1);
    pq2.push(3);

    while (pq2.size()) {
        cout << pq2.top() << endl;
        pq2.pop();
    }
}

int main()
{
    test2();
    return 0;
}

3. 测试结果：