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

前言

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

正文

什么是堆

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

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

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

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

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

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

大根堆

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

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

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

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

小根堆

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

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

添加元素

以大根堆为例，我们来看下大根堆添加元素的过程，假如添加元素一次为：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。

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

添加元素规则如下：

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

代码实现如下：

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;
   }
}

总结

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