数据结构-堆

墨蓝 2023-06-13 04:55 2阅读 0赞

> **1.堆**

堆通常是一个可以被看做是一颗完全二叉树的数组对象。

**性质：**

1）堆中某个节点的值总是不大于或不小于其父节点的值；

2）堆总是一颗完全二叉树；

堆分为两种情况，有最大堆和最小堆。将根节点最大的堆叫做大根堆，根节点最小的堆叫做小根堆。可以看见每个父节点的元素一定比子节点的元素大或者小。但是兄弟结点的大小则没有规定谁大谁小。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70][] 小根堆![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70 1][] 大根堆

> ** 2.相关算法**

数组下标从1-9分别加入：\{8,3,2,4,5,7,1,9,6\},我们以小根堆为列。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70 2][]

**1）上浮**

因为要构成小根堆，所以arr\[7\] = 1要上浮到根节点,从当前节点开始和父节点相比较，如果比父亲小则交换，然后将当前访问的节点下标更新为以前父节点的下标。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70 3][]

//上浮
    void upAdjust(Array arr,int index)
    {
        while(index / 2 >= 1)
        {
            if(arr[index] < arr[index/2])
            {
                swap(arr[index] , arr[index/2]);
                index = index / 2;
            }
            else
            {
                break;
            }
        }
    }

**2）下沉**

调整到上述图之后，不满足小根堆性质，所以将arr\[3\] = 8 下沉，让当前节点和其左右孩子节点比较，哪个比较小就和它交换，并更新节点的下标。

//index当前节点下标，totalNum表示当前有几个节点
    void adjustDown(Array arr,int index,int totalNum)
    {
        while(index * 2 <= totalNum)
        {
            int sonIndex = index * 2;
            if(sonIndex  + 1 <= totalNum && arr[sonIndex +1] < arr[sonIndex])
            {
                sonIndex++;
            }
            if(arr[index] < arr[sonIndex])
            {
                swap(arr[index],arr[sonIndex]);
                index = sonIndex;
            }
            else
            {
                break;
            }
        }
    }

**3）插入**

每次插入都是在最后进行插入

void push(Array arr,int value,int &totalNum)
    {
        totalNum++;
        arr[totalNum] = value;
        adjustUp(totalNum);
    }

**4）取顶**

让根节点与尾节点交换，根节点下沉，节点总数减一

int pop(Array arr,int &totalNum)
    {
        int rootValue = arr[1];
        swap(arr[1],arr[totalNum]);
        totalNum--;
        adjustDown(1);
        return rootValue;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191114102245903.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191114102225347.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191114105309447.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191114110156760.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d6ejk1MzIwMDQ2Mw==,size_16,color_FFFFFF,t_70