数据结构堆以及常见的操作

朱雀 2023-09-27 18:37 86阅读 0赞

### 前言 ###

本文介绍一种常见的数据结构——堆，堆也是一种高效的优先队列，文中将介绍大根堆、小根堆以及常见的操作。

### 正文 ###

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

堆通常是一个可以被看做一棵完全二叉树的数组对象，或者说是用数组实现的完全二叉树结构。

关于完全二叉树之前已经介绍过，这里就不再赘述，有兴趣可以查看[完全二叉树介绍][Link 1]。

那如何用数组实现完全二叉树呢？数组的下标依次对应二叉树从上到下的节点。例如，数组为`arr=[1,3,4,6,8,2,5,0,7]`，它对应的二叉树为如下图所示。

![format_png][]

从数组和二叉数对应的关系来看，对于数组中任意数组下标`i`，有以下几个性质：

*  数组下标`i`，他的左孩子下标为`2 * i + 1`
 *  数组下标`i`，他的右孩子下标为`2 * i + 2`
 *  数组下标`i`，他的父节点下标为`(i - 1) / 2`

堆又分为大根堆、小根堆。

#### 大根堆 ####

大根堆是指在一棵完全二叉树中，每一棵子树中节点的最大值都是头结点的位置。

如下图所示，以`10`为根节点的完全二叉树，这棵树的最大值为`10`，和根节点一致。

以`8`为根节点的完全二叉子树，这棵子树的最大值为`8`，和子树根节点一致。

以`6`为根节点的完全二叉子树，这棵子树的最大值为`6`，和子树根节点一致。

![format_png 1][]

#### 小根堆 ####

大根堆是指在一棵完全二叉树中，每一棵子树中节点的最小值都是头结点的位置。

如下图所示，下图中就是一个小根堆，在这个完全二叉树中，任意一个子树的最小值都是根节点。

![format_png 2][]

#### 添加元素 ####

以大根堆为例，我们来看下大根堆添加元素的过程，假如添加元素一次为：`10、6、8、12、11`，加入过程如下：

*  加入元素`10`，堆长度记为`1`。
 *  加入元素`6`，`6`比父节点`10`小，不用调整，堆长度记为`2`。
 *  加入元素`8`，`8`比父节点`10`小，不用调整，堆长度记为`3`。
 *  加入元素`12`，`12`比父节点`6`大，则`6`和`12`的位置进行交换，`12`继续和父节点`10`比较，比`10`大，继续交换，堆长度记为`4`。
 *  加入元素`11`，`11`比父节点`10`大，则`11`和`10`的位置进行交换，`11`继续和父节点`12`比较，比`10`小，停止交换，堆长度记为`5`。

最后对应的二叉树结构如下：

![format_png 3][]

添加元素规则如下：

*  在堆尾加入一个元素，先把这个结点置为当前结点。
 *  比较当前结点和他父结点值的大小， 如果当前结点小于父结点，则交换两个节点的位置，继续和父节点相比直到根节点。如果大于父节点的值，则停止比较。

代码实现如下：

public void heapInsert(int[] arr, int index) {
       while (arr[index] > arr[(index - 1) / 2]) {
          swap(arr, index, (index - 1) / 2);
          index = (index - 1) / 2;
       }
    }
    复制代码

#### 删除元素 ####

继续以大根堆为例，下面来看下如何删除元素，删除元素是指删除根节点元素，也就是数组中下标为`0`的元素。

需要注意的是，删除元素后，剩余的元素依然要保持大根堆的结构。

删除元素步骤如下：

*  将大根堆最后一个元素放到根节点，同时大根堆长度减`1`
 *  找到此时根节点左右孩子的最大节点，如果根节点大于最大节点则结束
 *  如果根节点小于他的左右孩子的最大节点，则交换两个节点的位置
 *  继续与左右孩子进行比较，直到比左右孩子的节点大或没有子节点为止

代码实现如下：

public void heapify(int[] arr, int index, int heapSize) {
       int left = index * 2 + 1;
       while (left < heapSize) { 
          // 把较大孩子的下标，给largest
          int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
          largest = arr[largest] > arr[index] ? largest : index;
          if (largest == index) {
             break;
          }
          // index和较大孩子，要互换
          swap(arr, largest, index);
          index = largest;
          left = index * 2 + 1;
       }
    }
    复制代码

总结

本文介绍一种常见的数据结构——堆，堆也是一种高效的优先队列，文中将介绍大根堆、小根堆以及常见的操作。

作者：Java星辰  
链接：https://juejin.cn/post/7228959271605059644

[Link 1]: https://juejin.cn/post/7225599634722930744
[format_png]: https://img-blog.csdnimg.cn/img_convert/a9c8d682e15df0d926f400289cc98aa0.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/468ca367be327861621b1c5d5d455919.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/4a64e0db8e022effc84dc8872dc14ff7.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/60f8b02788d7f0b6e4240fb60dca6362.webp?x-oss-process=image/format,png