二叉堆的介绍

今天药忘吃喽~ 2024-04-01 19:27 93阅读 0赞

#### 一、介绍 ####

习惯上，我们将二叉堆简称为“堆”，二叉堆是以数组存储的**完全二叉树**。父节点值大于或等于其孩子节点值的，叫最大堆；父节点值小于或等于孩子节点值的，叫最小堆。最大堆的根节点的值最大，最小堆的根节点的值最小。下图为树形结构表示的堆：

![20190822155923204.png][]

#### 二、二叉堆的性质 ####

<table> 
 <thead> 
  <tr> 
   <th>编号</th> 
   <th>性质</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>二叉堆是一棵完全二叉树</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>二叉堆的任意一个节点的优先级一定大于其两个子节点的</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>如果一个节点的下标为 x ，则其左孩子的下标为 2x ，右孩子的下标为 2x+1</td> 
  </tr> 
 </tbody> 
</table>

![02322ca2f9c649c0bd06e10d65787fcc.png][]

#### 三、堆的存储 ####

由于堆是一颗完全二叉树，根据完全二叉树的性质，可以用数组来存储堆

定义一个堆

#define maxn 100
    int  heap[maxn] ;  // 存储堆
    int  len;        // 堆中元素个数

![014bb6f63e3346e3a6eefaa916a8d8e7.png][]

从图中可以看出：数组中i元素对应的左子树在数组的2i的位置上，右子树在2i+1的位置上，其父亲在floor(i/2)的位置上。利用该特性很容易在用数组存储的二叉堆中找出一个节点的左右子树和父亲节点。

在数组的存储方式下，堆有如下性质：  
（1） 当用数组表示存储了n个元素的堆时，叶子结点的下标是 \[n/2\]+1,\[n/2\]+2,…,n  
（2） 一个从小到大已排好序的数组是最小堆，反之则不然，因为堆的结构不唯一

#### 四、插入元素 ####

在堆中插入元素x，首先将元素x放到堆中的最后一个位置（即最底层最右边的位置），然后不断地把x往上调整，直到x调不动为止（即大于它现在的父亲，或者x处于根结点）。

举个例子，我们往数组中插入元素50，步骤如下：

![aa73b699043548d6a9900145a5219a96.png][]

代码实现

void insert(int x) //将x放进堆 
    {
        heap[++len] = x; //把当前数放进堆尾 
        int i = len; //i为要调整的数在heap[]中的位置 
        while (i > 1 && heap[i] < heap[i / 2])
            //还没调到堆头，因为是小根堆，要满足儿子大于父亲，如果儿子小于父亲说明需要调整 
        {
            swap(heap[i], heap[i / 2]);//儿子和父亲交换 
            i /= 2; //交换后要调整的数的位置也改变了 
        }
    }

#### 五、在堆中删除位置为k的元素 ####

首先把位置k的元素和最后一个位置的元素交换，然后删去最后一个位置，这样k上的元素就被删除了，接着把位置k上的新元素不断下调，直到满足堆的性质。

![5258207257dd4dd487bf3733c205b3dc.png][]

代码实现

void del(int k) //删除堆中位置为k的元素
    {
        int i = k, j; //i:父亲 j:儿子 
        heap[k] = heap[len];
        len--; //将堆顶赋值为堆尾的数，再删除堆尾，调整堆顶的位置（往下移动） 
        while (i * 2 <= len)//把还没调到堆尾 
        {
            if (i * 2 == len || heap[i * 2] < heap[i * 2 + 1]) {
                j = i * 2;
             }           
            else {
                j = i * 2 + 1;
            }     
            //小根堆要满足父亲小于儿子，左儿子小于右儿子，j就是找左右儿子较小的那一个，与父亲进行交换 
            if (heap[j] < heap[i]) {
                 swap(heap[j], heap[i]);
                 i = j;
    `        }
    
            //如果儿子小于父亲，可以交换，更新父亲的位置
            else return; //否则此时的二叉堆满足堆的性质，可以返回 
        }
    }

#### 六、建立二叉堆 ####

把元素不断插入到堆

![7310ce57b9e54e58b778eeaa82c65a07.png][]

代码实现

}
    void make_heap()
    {
        int x;
        for (int i = 1; i <= m; i++)//m为要建堆的元素个数
        {
            cin >> x;
            insert(x);
        }
    }

参考：

[c++ 二叉堆讲义（CMB整理）\_楚颜a的博客-CSDN博客\_c++ 二叉堆][c_ _CMB_a_-CSDN_c_]

[c++ 二叉堆\_KonjakLAF的博客-CSDN博客][c_ _KonjakLAF_-CSDN]

[c++实现二叉堆及堆排序\_远走的兔子的博客-CSDN博客][c_-CSDN]

[20190822155923204.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/816200c073b347eb88747fad05854e48.png
[02322ca2f9c649c0bd06e10d65787fcc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/699d97fd23c94e6fbc65e7db8975f910.png
[014bb6f63e3346e3a6eefaa916a8d8e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/791571521c43428c8bad34ff55e06577.png
[aa73b699043548d6a9900145a5219a96.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/dfd47509106f4dd2a87a640b15f810ab.png
[5258207257dd4dd487bf3733c205b3dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/27aeb05bd15b4376b1fe364e8963995a.png
[7310ce57b9e54e58b778eeaa82c65a07.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/174652b6e3ad4d30bb0062de333b2a8f.png
[c_ _CMB_a_-CSDN_c_]: https://blog.csdn.net/weixin_45485187/article/details/100016886
[c_ _KonjakLAF_-CSDN]: https://blog.csdn.net/KonjakuLAF/article/details/115714564
[c_-CSDN]: https://blog.csdn.net/u014182411/article/details/72794061?spm=1001.2101.3001.6650.10&utm_medium=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromBaidu~Rate-10-72794061-blog-100016886.pc_relevant_multi_platform_whitelistv4&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromBaidu~Rate-10-72794061-blog-100016886.pc_relevant_multi_platform_whitelistv4&utm_relevant_index=10