数据结构-堆基本概念以及操作实现

淩亂°似流年 2022-06-05 10:37 182阅读 0赞

#### **一：堆相关的概念：** ####

##### **1>什么是堆**：堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。 #####

##### **2>堆的分类**：最大堆：每个父节点的都大于孩子节点。最小堆：每个父节点的都小于孩子节点。例如下面的两个堆： #####

![这里写图片描述][SouthEast]

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

#### **二：堆的向下调整过程**（拿大堆举例） ####

##### 首先给定父亲节点的下标，由于堆存放在数组中，下标一定连续，所以可以看作一棵完全二叉树，我们只需要求出该父亲节点对应左孩子的下标，使得child值为孩子中较大的一个的下标，若孩子中大的节点的值比父节点的值还大，则进行交换，再向下循环操作。反则不进行操作。可参考下面对应代码梳理一遍。 #####

![这里写图片描述][SouthEast 1]

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

##### 实现代码如下： #####

void _AdjustDown(int root)
        {
            int parent = root;
            //因为是完全二叉树，所以若存在孩子 则左孩子必定存在
            int child = parent * 2 + 1;
            while (child < _a.size())
            {
                if (child + 1 < _a.size() && _a[child + 1] > _a[child])
                    child++;
    
                if(_a[child] > _a[parent])
                {
                    swap(_a[child], _a[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                    break;
            }
        }

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

#### **二：堆的上调过程** ####

##### 上调过程多出现于在堆的push操作，当整个堆最后插入一个值后，只影响该节点到根路径上的节点，因为在没插入之前该堆是符合规则的。 #####

![这里写图片描述][SouthEast 2]

##### 简单实现代码如下： #####

void _AdjustUp(int child)
        {
            int parent = (child - 1) >> 1;
            while (child > 0)
            {
                if (_a[child] > _a[parent])
                {
                    swap(_a[child], _a[parent]);
                    child = parent;
                    parent = (child - 1) >> 1;
                }
                else
                {
                    break;
                }
            }
        }

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

#### **三：堆的push操作** ####

##### 由于堆底层是一个数组，我们可以使用vector来实现，当进行push操作时，首先需要将该节点插入到数组的尾部，其次以该节点下标为child，进行上调操作，具体图示可参考二。 #####

void Push(const T& x)
        {
            _a.push_back(x);
            _AdjustUp(_a.size() - 1);
        }

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

#### **四：堆的pop操作** ####

##### 对于一个堆，我们想要删除头节点时，可以采用替代删除法。先将头与数组最后一个值进行交换，再对头节点进行向下调整操作。 #####

![这里写图片描述][SouthEast 3]

void Pop()
        {
            assert(!_a.empty());
            swap(_a[0], _a[_a.size() - 1]);
            _a.pop_back();
            _AdjustDown(0);
        }

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

#### **五：建堆操作** ####

##### 当我们给定一个数组，想要将其放到一个大堆或者小堆时，首先要做的是将给定数组的值全部压入堆中，接下来就是找到最后一个节点的父亲，再依次进行向下调整操作，直到调整到头节点，完成整个建堆操作。 #####

Heap(const T* arr, int n)
        {
            _a.reserve(n);
            for (int i = 0; i < n; i++)
                _a.push_back(arr[i]);
    
            for (int i = (_a.size() - 2) >> 1; i >= 0; --i)
                _AdjustDown(i);
        }

#### 关于堆的简单实现完整代码可点击[https://github.com/SssUuuu/Data\_structure/blob/master/Heap.h][https_github.com_SssUuuu_Data_structure_blob_master_Heap.h]。 ####

[SouthEast]: /images/20220605/48ccced16f6a495892a363c1db4d1855.png
[SouthEast 1]: /images/20220605/953d4da8aee74bf2a3576d8093f2ba4a.png
[SouthEast 2]: /images/20220605/2579dce243f24f348fe40ca0f360d5d7.png
[SouthEast 3]: /images/20220605/02badbc38177487a86d3072db844090a.png
[https_github.com_SssUuuu_Data_structure_blob_master_Heap.h]: https://github.com/SssUuuu/Data_structure/blob/master/Heap.h