最大堆的简单实现

一．什么是最大堆?
　　最大堆的每一个节点的值都大于它的子节点的值．

二.如何实现最大堆?

堆的插入
首先插入到末尾

与父结点进行比较如果大于则与父结点交换位置

堆中取出元素，让堆末尾的元素放入堆的首部，和相邻子类进行比较，将其中较大的数字和父类指针进行交换

三.代码实现

采用vector 和 unordered_map 来进行实现

在代码中有详细的解释

#include <unordered_map>
#include <utility>
#include <vector>
class Priority_queue {
public:
    using pair = std::pair<size_t, uint64_t>;
    Priority_queue() = default;
    Priority_queue& operator=(const Priority_queue& other) = delete;
    bool Contains(size_t key) const {
        return m_pointer.find(key) != m_pointer.end();
    	//判断相应的键在堆中是不是存在
    }
    
    size_t GetSize() const {
        return m_heap.size(); // 返回堆的大小
    }
    const pair& Top() const {
        return m_heap.front();　// 返回堆顶
    }
    void Push(size_t key, uint64_t value) {
        if (Contains(key)) {　// 这个key 在不在堆中
            const size_t index = m_pointer.at(key);
            //找到在堆中对应的位置
  			//直接进行更新
            m_heap.at(index).second = value;
            //进行上滤操作
            Heap_Up(index);
            //可能比之前结点小　／／那么进行下滤
            //进行下滤比较
            Heap_Down(index);
        } else {
           //不存在的话，在堆最后放入结点，进行上滤操作
            const size_t index = m_heap.size();
            m_pointer[key] = index;
            m_heap.emplace_back(key, value);
            Heap_Up(index);
        }
    }
    void Pop() {
    	//首先从哈希map中删除堆顶元素的索引
        m_pointer.erase(m_heap.front().first);
        m_heap.front() = m_heap.back();
        m_heap.resize(m_heap.size() - 1);
        //末尾的第一个元素放对顶
        constexpr size_t index = 0;
        m_pointer[m_heap.front().first] = index;
        //
        Heap_Down(index);
        //进行下滤
    }
private:
    void Heap_Up(size_t index) {
    	//上滤
        while (index != m_root) {  // 如果索引到根结点退出
            auto&& parent = Parent(index);
            //获取父亲结点的索引
            auto&& value = m_heap.at(index).second;
            //当前结点的值
            auto&& parent_value = m_heap.at(parent).second;
            //获取父结点的值
            if (parent_value > value)
                break;
            Swap(index, parent);
           //索引和值的交换
            index = parent;
        }
    }
    void Heap_Down(size_t index) {
    	//下滤
        while (index < m_heap.size()) {
            auto&& child = Leftchild(index);
            //获取孩子的Ｉｎｄｅｘ
            //超出堆的范围
            if (child >= m_heap.size()) {
                break;
            }
            //左孩子和右孩子进行比较，选出最大的
            if (child + 1 < m_heap.size()) {
                child = (m_heap.at(child + 1).second > m_heap.at(child).second) ? child + 1 : child;
            }
            
            if (m_heap.at(index).second > m_heap.at(child).second)
                break;
            //交换
            Swap(index, child);
            index = child;
        }
    }

    //堆中元素的交换
    //交换堆的值和hashmap中的索引
    void Swap(size_t first, size_t second) {
        auto&& pair_first = m_heap.at(first);
        auto&& pair_second = m_heap.at(second);
        m_pointer[pair_first.first] = second;
        m_pointer[pair_second.first] = first;
        std::swap(m_heap[first], m_heap[second]);
    }
 	//返回父结点的地址信息
    inline size_t Parent(size_t index) const {
        return (index - 1) / 2;
    }
	//返回子结点的地址信息
    inline size_t Leftchild(size_t index) const {
        return index * 2 + 1;
    }

    std::vector<pair> m_heap;
    std::unordered_map<size_t, size_t> m_pointer;
    static constexpr size_t m_root = 0;  // 堆的根为0
    };