优先队列/堆

概述

优先队列: 一种抽象数据类型，按照特定的优先级，可以从接口依次获取到有序的数据
堆: 一个按特定的优先级将数据组织起来的数据结构，是优先队列的一种实现，只提供一段设置/获取数据，默认介绍二叉堆

简单图示

特性

完全二叉树: 一般使用数组来实现的完全二叉树作为堆结构
- 按照层序遍历构建的二叉树，使用数组实现很方便
部分有序/偏序(Partially Ordered): 以树的结构来看，堆的大小关系只局限在父子节点之间，不考虑兄弟节点

复杂度分析

操作	时间复杂度
查找最值	O(1)
插入一个数据	O(log(n))
插入n个数据	O(nlog(n))
删除最值	O(log(n))
建堆(逐个插入)(等价插入n个数据)	O(nlog(n))
建堆(非叶节点倒序遍历，往下调整)	$\sum_{k=0}^{\log n} \frac{n}{2^{k+1}} \cdot k = \frac{n}{2}\sum_{k=0}^{\log n} \frac{k}{2^{k}} = O(n)$

发散/随想/自身理解(?)

C++ 中优先队列调用 std::priority_queue
在工作中有见过堆结构的运用，但不是自己搞的，没有深究
在以前刷题的时候见的更多一点，一般在需要按特定顺序获取前k个特定元素的场景会看到
虽然说结构没那么难，但本人在理清该结构的时候还是费了一点脑子

实现(C++)

class Heap
{
public:
    Heap() {}
    Heap(const vector<int>& data_) : data(data_) {}

    virtual ~Heap() {}

    void Push(int val) {
        data.push_back(val);
        SiftUp(data.size() - 1);
    }
    void Pop() {
        swap(data[0], data.back());
        data.pop_back();
        SiftDown(0);
    }

    int Top() const {
        if (!Empty()) return data[0];
        return -1;
    }
    int Size() const { return data.size(); }
    bool Empty() const { return data.size() == 0; }

protected:
    // 比较逻辑：a 是否应该排在 b 上面
    // MaxHeap: return a > b; MinHeap: return a < b;
    virtual bool Compare(int a, int b) const = 0;

    void BuildHeap() {
        // for (int i = 0; i < data.size(); ++i) SiftUp(i); // O(log(n))
        for (int i = data.size() / 2 - 1; i >= 0; --i) SiftDown(i); // O(n)
    }

private:
    void SiftDown(int pos) {
        while (!IsLeaf(pos)) {
            int child = LeftChild(pos);
            int right_child = RightChild(pos);
            if (right_child < data.size() && Compare(data[right_child], data[child])) {
                cout << pos << endl;
                child = right_child;
            }
            if (Compare(data[pos], data[child])) break;
            swap(data[pos], data[child]);
            pos = child;
        }
    }
    void SiftUp(int pos) {
        while (pos > 0) {
            int parent = Parent(pos);
            if (!Compare(data[pos], data[parent])) break;
            swap(data[pos], data[parent]);
            pos = parent;
        }
    }

    int Parent(int child) {
        return child <= 0 ? 0 : (child - 1) / 2;
    }

    int LeftChild(int parent) {
        return parent < 0 ? 0 : parent * 2 + 1;
    }
    int RightChild(int parent) {
        return parent < 0 ? 0 : parent * 2 + 2;
    }
    bool IsLeaf(int node) {
        return (node >= data.size() / 2) && (node < data.size());
    }

private:
    vector<int> data;
};

class MaxHeap : public Heap
{
public:
    using Heap::Heap;
    MaxHeap(const vector<int>& data_) : Heap(data_) { BuildHeap(); }

protected:
    bool Compare(int a, int b) const override { return a > b; }
};

class MinHeap : public Heap
{
public:
    using Heap::Heap;
    MinHeap(const vector<int>& data_) : Heap(data_) { BuildHeap(); }

    protected:
    bool Compare(int a, int b) const override { return a < b; }
};

优先队列/堆

概述

简单图示

特性

分类

复杂度分析

发散/随想/自身理解(?)

实现(C++)