8 堆

Wu Jun 2020-02-04 22:45:02
01 数据结构与算法 > 数据结构 > 01 数据结构

堆(Heap)是一种特别的树状数据结构:“给定堆中任意节点 P 和 C,若 P 是 C 的母节点,那么 P 的值会小于等于(或大于等于)C 的值”。分为最小堆和最大堆。

  1. 二叉堆
  2. 左倾堆
  3. 斜堆
  4. 二项堆
  5. 斐波那契堆
  6. 索引堆
  7. Treap 树堆

1、二叉堆

二叉堆是完全二元树或者是近似完全二元树,按照数据的排列方式可以分为两种:最大堆和最小堆。

二叉堆一般都通过"数组"来实现

2、左倾堆

左倾堆(leftist tree 或 leftist heap),又被成为左偏树、左偏堆,最左堆等。

它和二叉堆一样,都是优先队列实现方式。可以高效解决"对两个优先队列进行合并"的问题。

上图是一颗左倾树,它的节点除了和二叉树的节点一样具有左右子树指针外,还有两个属性:键值和零距离。

左倾堆有以下几个基本性质:

合并两个左倾堆的基本思想如下:

  1. 如果一个空左倾堆与一个非空左倾堆合并,返回非空左倾堆。
  2. 如果两个左倾堆都非空,那么比较两个根节点,取较小堆的根节点为新的根节点。将"较小堆的根节点的右孩子"和"较大堆"进行合并。
  3. 如果新堆的右孩子的NPL > 左孩子的NPL,则交换左右孩子。
  4. 设置新堆的根节点的NPL = 右子堆NPL + 1

3、斜堆

斜堆也叫自适应堆,它是左倾堆的一个变种。和左倾堆一样,它通常也用于实现优先队列;作为一种自适应的左倾堆,它的合并操作的时间复杂度也是O(log n)。

它与左倾堆的差别是:

  1. 斜堆的节点没有"零距离"这个属性,而左倾堆则有。
  2. 斜堆的合并操作和左倾堆的合并操作算法不同。

斜堆的合并操作

  1. 如果一个空斜堆与一个非空斜堆合并,返回非空斜堆。
  2. 如果两个斜堆都非空,那么比较两个根节点,取较小堆的根节点为新的根节点。将"较小堆的根节点的右孩子"和"较大堆"进行合并。
  3. 合并后,交换新堆根节点的左孩子和右孩子。

第 3 步是斜堆和左倾堆的合并操作差别的关键所在,如果是左倾堆,则合并后要比较左右孩子的零距离大小,若右孩子的零距离 > 左孩子的零距离,则交换左右孩子;最后,在设置根的零距离。

4、二项堆

二项堆是二项树的集合。在了解二项堆之前,先对二项树进行介绍。

1)二项树

二项树是一种递归定义的有序树。它的递归定义如下:

  1. 二项树B0只有一个结点;
  2. 二项树Bk由两棵二项树B(k-1)组成的,其中一棵树是另一棵树根的最左孩子。

2)二项堆

二项堆和之前所讲的堆(二叉堆、左倾堆、斜堆)一样,也是用于实现优先队列的。二项堆是指满足以下性质的二项树的集合:

  1. 每棵二项树都满足最小堆性质。即,父节点的关键字 <= 它的孩子的关键字。
  2. 不能有两棵或以上的二项树具有相同的度数(包括度数为0)。换句话说,具有度数k的二项树有0个或1个。

5、斐波那契堆

斐波那契堆(Fibonacci heap)是一种可合并堆,可用于实现合并优先队列。它比二项堆具有更好的平摊分析性能,它的合并操作的时间复杂度是O(1)。

与二项堆一样,它也是由一组堆最小有序树组成,并且是一种可合并堆。

与二项堆不同的是,斐波那契堆中的树不一定是二项树;而且二项堆中的树是有序排列的,但是斐波那契堆中的树都是有根而无序的。

6、索引堆

索引堆是对堆进行了优化。

索引堆使用了一个新的int类型的数组,用于存放索引信息。

索引堆的交换操作交换的是元素的索引,而不是直接交换元素。

7、Treap 树堆

一棵treap是一棵修改了结点顺序的二叉查找树,如图,显示一个例子,通常树内的每个结点x都有一个关键字值key[x],另外,还要为结点分配priority[x],它是一个独立选取的随机数。

假设所有的优先级是不同的,所有的关键字也是不同的。treap的结点排列成让关键字遵循二叉查找树性质,并且优先级遵循最小堆顺序性质:

  1. 如果v是u的左孩子,则key[v] < key[u].
  2. 如果v是u的右孩子,则key[v] > key[u].
  3. 如果v是u的孩子,则priority[u] > priority[u].

这两个性质的结合就是为什么这种树被称为“treap”的原因,因为它同时具有二叉查找树和堆的特征。