[数据结构和算法] 堆/优先队列的实现

预备知识：

• 完全二叉树可以用数组表示：
  • 从下标0开始存储数据：左子节点 = 2 * 父节点 + 1，右子节点 = 2 * 父节点 + 2；
  • 从下标1开始存储数据：左子结点 = 2 * 父节点，右子节点= 2 * 父节点 + 1；
• 堆：
  • 大根堆：父节点的值大于等于左右子节点的值；
  • 小根堆：父节点的值小于等于左右子节点的值；

【注】看不懂的没必要往下了~

示例：大根堆的实现

C++实现：（实际上就是C++中的优先队列容器）

#include <bits/stdc++.h>
using namespace std;
namespace chasemeng {
    template<typename T>
    class priority_queue {
    public:
        // 插入元素：添加到树的末尾，然后上浮
        void push(T& val) {
            _tree.push_back(val);
            // === 上浮 ===
            int son = size() - 1;
            // 遍历父节点
            for (int i = (son - 1) / 2; i >= 0; i = (i - 1) / 2) {
                if (_tree[son] <= _tree[i]) {
                    break;
                }
                swap(_tree[son], _tree[i]);
                son = i;
            }
        }
        // 弹出堆顶元素：将最后一个元素置换到堆顶，然后下沉该元素
        void pop() {
            swap(_tree.front(), _tree.back());
            _tree.pop_back();
            if (_tree.empty()) {
                return;
            }
            // 调整元素
            int left = 0, right = size() - 1;
            int parent = left;
            // 遍历子节点
            for (int i = 2 * left + 1; i <= right; i = 2 * i + 1) {
                if (i < right && _tree[i] < _tree[i + 1]) {
                    ++i;
                }
                if (_tree[parent] >= _tree[i]) {
                    break;
                }
                swap(_tree[parent], _tree[i]);
                parent = i;
            }
        }
        // 获取堆顶元素
        T top() {
            if (this->size() <= 0) {
                cout << "完蛋了" << endl;
                throw "完蛋了";
            }
            return _tree.front();
        }
        // 是否为空
        bool empty() {return _tree.empty();}
        // 获取元素个数
        int size() {return _tree.size();}
        
    private:
        vector<T> _tree;
    };
}

【注】小根堆的实现基本不用怎么改动，自己思考一下即可。

测试

int main() {
    srand((unsigned)time(NULL));
    chasemeng::priority_queue<int> pque;
    for (int i = 0; i < 20; ++i) {
        int num = rand() % 100;
        cout << num << " \n"[i == 20 - 1];
        pque.push(num);
    }
    while (!pque.empty()) {
        cout << pque.top() << " ";
        pque.pop();
    }
    return 0;
}

结果：

执行完成，耗时：0 ms
76 31 86 80 69 7 71 31 28 95 84 97 63 56 24 59 71 86 97 40
97 97 95 86 86 84 80 76 71 71 69 63 59 56 40 31 31 28 24 7 

完整代码

#include <bits/stdc++.h>
using namespace std;
namespace chasemeng {
    template<typename T>
    class priority_queue {
    public:
        // 插入元素：添加到树的末尾，然后上浮
        void push(T& val) {
            _tree.push_back(val);
            // === 上浮 ===
            int son = size() - 1;
            // 遍历父节点
            for (int i = (son - 1) / 2; i >= 0; i = (i - 1) / 2) {
                if (_tree[son] <= _tree[i]) {
                    break;
                }
                swap(_tree[son], _tree[i]);
                son = i;
            }
        }
        // 弹出堆顶元素：将最后一个元素置换到堆顶，然后下沉该元素
        void pop() {
            swap(_tree.front(), _tree.back());
            _tree.pop_back();
            if (_tree.empty()) {
                return;
            }
            // 调整元素
            int left = 0, right = size() - 1;
            int parent = left;
            // 遍历子节点
            for (int i = 2 * left + 1; i <= right; i = 2 * i + 1) {
                if (i < right && _tree[i] < _tree[i + 1]) {
                    ++i;
                }
                if (_tree[parent] >= _tree[i]) {
                    break;
                }
                swap(_tree[parent], _tree[i]);
                parent = i;
            }
        }
        // 获取堆顶元素
        T top() {
            if (this->size() <= 0) {
                cout << "完蛋了" << endl;
                throw "完蛋了";
            }
            return _tree.front();
        }
        // 是否为空
        bool empty() {return _tree.empty();}
        // 获取元素个数
        int size() {return _tree.size();}
        
    private:
        vector<T> _tree;
    };
}
int main() {
    srand((unsigned)time(NULL));
    chasemeng::priority_queue<int> pque;
    for (int i = 0; i < 20; ++i) {
        int num = rand() % 100;
        cout << num << " \n"[i == 20 - 1];
        pque.push(num);
    }
    while (!pque.empty()) {
        cout << pque.top() << " ";
        pque.pop();
    }
    return 0;
}

【注】自己测试没有问题，如果有bug，请反馈一下~