【数据结构】堆

╰+哭是因爲堅強的太久メ 2022-05-28 12:11 245阅读 0赞

#### 什么是堆？ ####

这里的堆不是指计算机里的“堆栈”，而是指一种数据结构，它的结构是一颗二叉树。  
我们把一个关键码集合中所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足以下两个之一：

*  任一个节点的关键码均小于等于它的左右孩子的关键码，位于堆顶的关键码最小的称为最小堆；
 *  任一个节点的关键码均大于等于它的左右孩子的关键码，位于堆顶的关键码最大的称之为最大堆。

--------------------

#### 堆的创建 ####

这里创建一个最小堆：  
![这里写图片描述][70]

#### 堆的插入和删除 ####

由于堆的每次插入都在已经建好的最小堆的后面插入，但插入之后，还需要对堆进行自下而上的调整。  
![这里写图片描述][70 1]  
堆的删除：从堆顶中删除堆顶元素。移除堆顶元素后，用堆的最后一个结点填补堆顶元素，并将元素个数减一，在对堆进行自上而下的调整。  
![这里写图片描述][70 2]

#### 堆的应用 ####

1.  优先级队列：优先级队列的底层实现就是堆。
2.  在一堆数据中找最大的前K个：先将前K个数据按照小堆进行创建，在依次遍历要查找的数据，如果该数据大于堆顶元素，则用它替换堆顶元素，并将堆调整，这样最终就可以得到最大的K个元素。
3.  堆排序：如果是升序，我们需要创建一个大堆，利用和删除元素类似的想法，我们将堆顶元素和最后一个互换没然后调整堆，最终就可以得到一个升序的序列；反之，排列降序，就创建小堆。

--------------------

下面是代码实现：

#include <iostream>
    #include <vector>
    using namespace std;
    
    template <class T>
    struct Less//小堆
    {
        bool operator()(const T& left, const T& right)
        {
            return left->_data < right->_data;
        }
    }; 
    
    template <class T>
    struct Greater//大堆
    {
        bool operator()(const T& left, const T& right)
        {
            return left > right;
        }
    };
    
    template <class T, class Compare = Less<T>>
    class Heap
    {
    public:
        Heap()
        {}
        Heap(T *arr, size_t size)
        {
            _arr.resize(size);
            for (size_t i = 0; i < size; i++)
                _arr[i] = arr[i];
            if (size > 1)
            {
                int root = (size - 2) / 2;//size_t的数据大于等于0造成死循环
                for (; root >= 0; root--)
                    _AdjustDown(root);
            }
        }
    
        void Push(const T& data)
        {
            _arr.push_back(data);
            size_t size = _arr.size();
            if (size > 1)
                _AdjustUp(size - 1);
        }
    
        void Pop()
        {
            size_t size = _arr.size();
            if (_arr.empty())
                return;
            swap(_arr[0], _arr[size - 1]);
            _arr.pop_back();
            if (_arr.size() > 1)
                _AdjustDown(0);
        }
    
        bool Empty()const
        {
            return _arr.empty();
        }
    
        size_t Size()const
        {
            return _arr.size();
        }
    
        T Top()const
        {
            return _arr[0];
        }
    
    private:
        void _AdjustDown(size_t parent)
        {
            size_t child = parent * 2 + 1;
            size_t size = _arr.size();
            while (child < size)
            {
                if (child + 1 < size && Compare()(_arr[child + 1], _arr[child]))
                    child += 1;
                if (Compare()(_arr[child], _arr[parent]))
                {
                    swap(_arr[parent], _arr[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                    break;
            }
        }
    
        void _AdjustUp(size_t child)
        {
            size_t parent = (child - 1) / 2;
            size_t size = _arr.size();
            while (child > 0)
            {
                if (Compare()(_arr[child], _arr[parent]))
                {
                    swap(_arr[parent], _arr[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                    break;
            }
        }
    private:
        vector<T> _arr;
    };

[70]: /images/20220528/aeabbbb93c974024860dae257c505d22.png
[70 1]: /images/20220528/e2bf5bf528ae4517bc94f67fcf7e125e.png
[70 2]: /images/20220528/a6f8b57ee72348f19fe045cb1961b6cf.png