堆

发表于 | 浏览 次

什么是堆

我们面临的第一个问题是：什么是堆？

堆可以定义为一颗二叉树，树的节点中包含键，并且满足两个条件：
１．该二叉树是完全二叉树．除了最后一层，树的每一层都是满的．
２．父母优势：(以最大堆为例)父节点的键大于或等于孩子节点的键

可以用数组来实现堆．

建堆，插入新元素，删除堆顶元素

自底向上构造堆

从最后一个非叶节点开始，检查该节点是否满足父母优势．如果不满足，就将该节点与最大孩子节点的键交换，然后再检查新的位置．这个过程持续到被检查节点满足父母优势为止(叶子节点自动满足父母优势)．此过程从最后一个非叶节点一直持续到根节点．
最后一个非叶节点：假设堆中有n个节点，则最后一个非叶节点为(n/2)向下取整．例如，n=7,最后一个非叶节点为３.

将一个堆调整为最大堆

将以k为根的子树调整为一个堆的过程可以简单描述如下：查看k的孩子节点中是否存在比k大的，如果不存在说明以k为根的子树已经是一个最大堆了（这里存在一个假设：在调整以k为根的子树时，以k的左右孩子节点为根的子树都已经是堆了）．否则，交换k和孩子节点中较大的那个（无论两个孩子节点是否都满足大于k），假设此新节点为n，接下来就是调整以n为根节点的子树了．显然，这就是重复上面的过程，那么这个过程应该持续到什么时候结束呢？答案是到k已经是叶子节点或者没有孩子节点都比它小了．

非递归方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
max_heapify_iter(H[1,...,n], k)
    // 输入：H[1,..,n]是一个数组，表示一个完全二叉树
    // k：当前要调整的节点K
    // 输出：以节点i为根的二叉树调整为一个堆
  	k = i, v = H[k]   // K是当前需要检查的节点
  	heap = false   　　//　状态变量，表示当前要检查的节点是否满足父母优势
  	while not heap and 2 * k <= n  // 当要检查的节点不满足父母优势且不是叶子节点
        j = 2 * k
        if j < n    // 被检查节点有两个孩子节点
        	if H[j + 1] > H[j]
        		j = j + 1
        if v >= H[j]
        	heap = true
        else
            H[k] = H[j]   // 交换被检查的节点和它最大孩子节点的键
            k = j　　　　　// 继续检查被交换后的最大孩子节点的键

递归方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
max_heapify_recur(A, i)
    // 输入：A[1,..,n]是一个数组，表示一个完全二叉树
    // i：当前要调整的节点i
    // 输出：以节点i为根的二叉树调整为一个堆
    l = 2 * i     // 节点i的左孩子2 * i
    r = 2 * i + 1 // 节点i的左孩子2 * i + 1
    if l <= n and A[l] >= A[i]
    	largest = l
   	else 
        largest = i
   	if r <= n and A[r] >= A[largest]
   		largest = r
	if largest != i
		exchange(A[i], A[largest])
    	max_heapify(A, largest)

时间复杂度：O(lgn)

建堆

非递归方式

1
2
3
4
5
6
HeapBottomUp(H[1,...,n])
  // 用自底向上算法，从给定数组的元素中构造一个堆
  // 输入：一个可排序元素的数组H[1,...,n]
  // 输出：一个堆H[1,...,n]
  for i = [n/2] to 1 do
  	max_heapify_iter(H, i)

递归方式

1
2
3
4
5
6
build_max_heap(A)
    // 用自底向上算法，从给定数组的元素中构造一个堆
  	// 输入：一个可排序元素的数组A[1,...,n]
  	// 输出：一个堆A[1,...,n]
    for i = n/2 to 1 do   // n/2向下取整
        max_heapify_recur(A, i)

自底向上建堆时间复杂度分析

自底向上方式建堆，需要调用n/2次max_headify(将一个堆调整为最大堆)，每次调用max_heapify的时间复杂度为O(logk)，这里的k是被调整的子树中节点的总数。接下来，计算总的时间复杂度。
包含n个元素的堆的高度为
$$
\lfloor{lgn}\rfloor
$$
高度为h的堆最多包含
$$
\lceil{\frac{n}{2^{h+1}}}\rceil
$$
个结点。在一个高度为h的结点上运行max_heapify的代价为O(h)，因此建堆的总的时间复杂度为：
$$
\sum_{h=0}^{\lfloor{lgn}\rfloor}{\lceil{\frac{n}{2^{h+1}}}\rceil} O(h)= O(n \sum_{h=0}^{\lfloor{lgn}\rfloor}\frac{h}{2^h})
$$
级数求和公式：
$$
\sum_{k=0}^{\infty}{k}{x^k} = \frac{x}{(1-x)^2}
$$
将x=1/2带入级数求和公式，可知：
$$
\sum_{k=0}^{\infty}\frac{h}{2^h} = \frac{1/2}{(1 - {1/2})^2} = 2
$$
因此，建堆的时间复杂度为：
$$
O(n \sum_{h=0}^{\lfloor{lgn}\rfloor}\frac{h}{2^h}) = O(n \sum_{h=0}^{\infty}\frac{h}{2^h}) = O(n)
$$
因此，可以在线性时间内，将一个无序数组构造成一个最大堆。

向已经建好的堆中插入元素

向一个已经建好的堆中插入新元素，首先将新元素k插入到堆中最后一个叶子节点的后面。然后按照下面的方法把这个新元素k放到适当的位置上。首先拿k和它的父节点进行比较，如果k的键小于等于父节点的值，则算法停止（当前堆已经是个最大堆了）。否则交换这个元素的位置，并比较元素k和它的新父节点。这个过程一直持续到父节点的键值大于等于元素k的键值或者元素k没有了父节点(即元素k是根节点）。
显然，插入操作需要的比较次数不会多于树的高度，即向堆中插入新元素的时间复杂度为O(lgn)。

删除堆顶元素

第一步，交换根节点的元素和堆中最后一个节点的元素。
第二步，堆的规模减去1。
第三步，调用max_heapify，将以根节点为根的子树调整为最大堆。
删除需要一次交换和一次自顶向下调整堆的过程，因此，时间复杂度取决于调整堆的时间复杂度，即为O(lgn)。

堆排序

第一步，堆排序首先构造堆，为一个给定的数组构造一个堆．时间复杂度为O(n)

第二步，从堆中删除最大键，持续此动作n-1次．时间复杂度为O(nlogn)

删除最大键并调整堆的时间复杂度：O(lgn)

堆排序的时间效率是O(nlogn)，但是堆排序是原址排序，不需要任何额外的存储空间． 堆排序比快速排序运行得慢，但是比归并排序快．

1
2
3
4
5
6
7
8
heap_sort(A)
	// 输入：一个可排序元素的数组A[1,...,n]
  	// 输出：一个排好序的数组A
   	heap_size = n
    for i = n to 2
        exchange(A[i], A[1])
        --heap_size;
        max_heapify_iter(A, 1) // 调整以节点１为根，大小为heap_size的数组为最大堆