最大堆的简单实现

超、凢脫俗 2023-07-09 02:08 9阅读 0赞

一．什么是最大堆?  
　　最大堆的每一个节点的值都大于它的子节点的值．  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70]  
二.如何实现最大堆?

堆的插入  
首先插入到末尾  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70 1]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70 2]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70 4]  
三.代码实现

采用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
        };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200227103030603.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200227104456748.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200227105746286.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200227110336382.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200227110517106.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f,size_16,color_FFFFFF,t_70