堆（Heap）大根堆、小根堆

ゝ一纸荒年。 2022-11-08 11:49 114阅读 0赞

# 堆（Heap）大根堆、小根堆 #

### 文章目录 ###

*  堆（Heap）大根堆、小根堆
 *  Heap是一种数据结构
 *  堆的存储
 *  堆的操作：insert
 *  堆的操作：Removemax
 *  堆的操作：buildHeap 堆化数组
 *  堆排序

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

![在这里插入图片描述][20210313134410606.gif]

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

# Heap是一种数据结构 #

> 具有以下的特点：  
> 1）完全二叉树；  
> 2）heap中存储的值是偏序；

> Min-heap: 父节点的值小于或等于子节点的值；  
> Max-heap: 父节点的值大于或等于子节点的值；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hSVE9OWQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210313143534699.png]

# 堆的存储 #

> 一般都用数组来表示堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2 \* i + 1和2 \* i + 2。如第0个结点左右子结点下标分别为1和2。

![在这里插入图片描述][2021031314321392.png]  
![在这里插入图片描述][20210313143854690.png_pic_center]

# 堆的操作：insert #

> 插入一个元素：新元素被加入到heap的末尾，然后更新树以恢复堆的次序。  
> 每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hSVE9OWQ_size_16_color_FFFFFF_t_70 1]

# 堆的操作：Removemax #

> 按定义，堆中每次都删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最大的，如果父结点比这个最小的子结点还大说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。

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

![在这里插入图片描述][20210313143954285.png]

# 堆的操作：buildHeap 堆化数组 #

> 对于叶子节点，不用调整次序，根据满二叉树的性质，叶子节点比内部节点的个数多1.所以i=n/2 -1 ，不用从n开始。

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

![在这里插入图片描述][20210313144002550.png]

# 堆排序 #

> 堆建好之后堆中第0个数据是堆中最大的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最大的数据，重复上述步骤直至堆中只有一个数据时就直接取出这个数据。

![在这里插入图片描述][20210313144100876.gif]

[20210313134410606.gif]: /images/20221023/f9097f49aa024f87b6f63b78b5c86a25.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hSVE9OWQ_size_16_color_FFFFFF_t_70]: /images/20221023/72fbc2076f3f4e909c62c2d2d23cbede.png
[20210313143534699.png]: /images/20221023/7b1e78ed37c14e80aced7cd1541c0720.png
[2021031314321392.png]: /images/20221023/f44f8f8389e74bbc8955b3a1a7f5d030.png
[20210313143854690.png_pic_center]: /images/20221023/99afdcf5365e4f27850b4fc19e15c9a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hSVE9OWQ_size_16_color_FFFFFF_t_70 1]: /images/20221023/644c29fe0b7e492a88d618d067fca63a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hSVE9OWQ_size_16_color_FFFFFF_t_70 2]: /images/20221023/f104c15a9e854f5194567a20d4be17b2.png
[20210313143954285.png]: /images/20221023/fcc94e4e26414de49e96b8b5dedb72ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hSVE9OWQ_size_16_color_FFFFFF_t_70 3]: /images/20221023/028ea5d9b26e4a78b8ddfb4fcf49b612.png
[20210313144002550.png]: /images/20221023/38675193e4214dbab109e5fc96995c15.png
[20210313144100876.gif]: /images/20221023/3d90e4c5489a4eb39fd05129d0d4f7f8.png