数据结构——堆和堆排序(python)_堆数据结构

本文通过堆的实现、最小堆（最大堆）、堆的时间复杂度、优先队列的实现、堆排序来介绍「 堆 」。

堆的实现
堆的一个经典的实现是完全二叉树(complete binary tree)，这样实现的堆称为二叉堆(binary heap)。

这里来说明一下满二叉树的概念与完全二叉树的概念。

满二叉树：除了叶子节点，所有的节点的左右孩子都不为空，就是一棵满二叉树，如下图。

可以看出：满二叉树所有的节点都拥有左孩子，又拥有右孩子。

完全二叉树：不一定是一个满二叉树，但它不满的那部分一定在右下侧，如下图：

堆的特性：

• 必须是完全二叉树
• 任一结点的值是其子树所有结点的最大值或最小值
• 最大值时，称为“最大堆”，也称大顶堆；
• 最小值时，称为“最小堆”，也称小顶堆。
  
  堆的基础实现

只要谨记堆的定义特性，实现起来其实是很容易的。

• 特性1. 维持完全二叉树
• 特性2. 子类数字总是大于父类数字

二叉堆的操作

二叉堆的基本操作定义如下：

BinaryHeap()：创建一个空的二叉堆对象

insert(k)：将新元素加入到堆中

findMin()：返回堆中的最小项，最小项仍保留在堆中

delMin()：返回堆中的最小项，同时从堆中删除

isEmpty()：返回堆是否为空

size()：返回堆中节点的个数

buildHeap(list)：从一个包含节点的列表里创建新堆

二叉堆结构性质

为了更好地实现堆，我们采用二叉树。我们必须始终保持二叉树的“平衡”，就要使操作始终保持在对数数量级上。平衡的二叉树根节点的左右子树的子节点个数相同。在堆的实现中，我们采用“完全二叉树”的结构来近似地实现“平衡”。完全二叉树，指每个内部节点树均达到最大值，除了最后一层可以只缺少右边的若干节点。图 1 所示是一个完全二叉树。

有意思的是我们用单个列表就能实现完全树。我们不需要使用节点，引用或嵌套列表。因为对于完全二叉树，如果节点在列表中的下标为 p，那么其左子节点下标为 2p，右节点为 2p+1。当我们要找任何节点的父节点时，可以直接使用 python 的整除。如果节点在列表中下标为n，那么父节点下标为n//2.图 2 所示是一个完全二叉树和树的列表表示法。注意父节点与子节点之间 2p 与 2p+1 的关系。完全树的列表表示法结合了完全二叉树的特性，使我们能够使用简单的数学方法高效地遍历一棵完全树。这也使我们能高效实现二叉堆。

堆次序的性质

我们在堆里储存元素的方法依赖于堆的次序。所谓堆次序，是指堆中任何一个节点 x，其父节点 p 的键值均小于或等于 x 的键值。图 2 所示是具备堆次序性质的完全二叉树。

二叉堆操作的实现

接下来我们来构造二叉堆。因为可以采用一个列表保存堆的数据，构造函数只需要初始化一个列表和一个currentSize来表示堆当前的大小。Listing 1 所示的是构造二叉堆的 python 代码。注意到二叉堆的heaplist并没有用到，但为了后面代码可以方便地使用整除，我们仍然保留它。

Listing 1

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0
1
2
3
4

我们接下来要实现的是insert方法。首先，为了满足“完全二叉树”的性质，新键值应该添加到列表的末尾。然而新键值简单地添加在列表末尾，显然无法满足堆次序。但我们可以通过比较父节点和新加入的元素的方法来重新满足堆次序。如果新加入的元素比父节点要小，可以与父节点互换位置。图 3 所示的是一系列交换操作来使新加入元素“上浮”到正确的位置。

当我们让一个元素“上浮”时，我们要保证新节点与父节点以及其他兄弟节点之间的堆次序。当然，如果新节点非常小，我们仍然需要将它交换到其他层。事实上，我们需要不断交换，直到到达树的顶端。Listing 2 所示的是“上浮”方法，它把一个新节点“上浮”到其正确位置来满足堆次序。这里很好地体现了我们之前在headlist中没有用到的元素 0 的重要性。这样只需要做简单的整除，将当前节点的下标除以 2，我们就能计算出任何节点的父节点。

Listing 2

def percUp(self,i):
    while i // 2 > 0:
      if self.heapList[i] < self.heapList[i // 2]:
         tmp = self.heapList[i // 2]
         self.heapList[i // 2] = self.heapList[i]
         self.heapList[i] = tmp
      i = i // 2
1
2
3
4
5
6
7

在Listing 3 中，我们已经可以写出insert方法的代码。insert里面很大一部分工作是由percUp函数完成的。当树添加新节点时，调用percUp就可以将新节点放到正确的位置上。

Listing 3

def insert(self,k):
    self.heapList.append(k)
    self.currentSize = self.currentSize + 1
    self.percUp(self.currentSize)
1
2
3
4

我们已经写好了insert方法，那再来看看delMin方法。堆次序要求根节点是树中最小的元素，因此很容易找到最小项。比较困难的是移走根节点的元素后如何保持堆结构和堆次序，我们可以分两步走。首先，用最后一个节点来代替根节点。移走最后一个节点保持了堆结构的性质。这么简单的替换，还是会破坏堆次序。那么第二步，将新节点“下沉”来恢复堆次序。图 4 所示的是一系列交换操作来使新节点“下沉”到正确的位置。

为了保持堆次序，我们需将新的根节点沿着一条路径“下沉”，直到比两个子节点都小。在选择下沉路径时，如果新根节点比子节点大，那么选择较小的子节点与之交换。Listing 4 所示的是新节点下沉所需的percDown和minChild方法的代码。

Listing 4

def percDown(self,i):
    while (i * 2) <= self.currentSize:
        mc = self.minChild(i)
        if self.heapList[i] > self.heapList[mc]:
            tmp = self.heapList[i]
            self.heapList[i] = self.heapList[mc]
            self.heapList[mc] = tmp
        i = mc

def minChild(self,i):
    if i * 2 + 1 > self.currentSize:
        return i * 2
    else:
        if self.heapList[i*2] < self.heapList[i*2+1]:
            return i * 2
        else:
            return i * 2 + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Listing 5 所示的是delMin操作的代码。可以看到比较麻烦的地方由一个辅助函数来处理，即percDown。

Listing 5

def delMin(self):
    retval = self.heapList[1]
    self.heapList[1] = self.heapList[self.currentSize]
    self.currentSize = self.currentSize - 1
    self.heapList.pop()
    self.percDown(1)
    return retval
1
2
3
4
5
6
7

关于二叉堆的最后一部分便是找到从无序列表生成一个“堆”的方法。我们首先想到的是，将无序列表中的每个元素依次插入到堆中。对于一个排好序的列表，我们可以用二分搜索找到合适的位置，然后在下一个位置插入这个键值到堆中，时间复杂度为O(logn)。另外插入一个元素到列表中需要将列表的一些其他元素移动，为新节点腾出位置，时间复杂度为O(n)。因此用insert方法的总开销是O(nlogn)。其实我们能直接将整个列表生成堆，将总开销控制在O(n)。Listing 6 所示的是生成堆的操作。

Listing 6

def buildHeap(self,alist):
    i = len(alist) // 2
    self.currentSize = len(alist)
    self.heapList = [0] + alist[:]
    while (i > 0):
        self.percDown(i)
        i = i - 1
1
2
3
4
5
6
7

图 5 所示的是利用buildHeap方法将最开始的树[ 9, 6, 5, 2, 3]中的节点移动到正确的位置时所做的交换操作。尽管我们从树中间开始，然后回溯到根节点，但percDown方法保证了最大子节点总是“下沉”。因为堆是完全二叉树，任何在中间的节点都是叶节点，因此没有子节点。注意，当i=1时，我们从根节点开始下沉，这就需要进行大量的交换操作。可以看到，图 5 最右边的两颗树，首先 9 从根节点的位置移走，移到下一层级之后，percDown进一步检查它此时的子节点，保证它下降到不能再下降为止，即下降到正确的位置。然后进行第二次交换，9 和 3 的交换。由于 9 已经移到了树最底层的层级，便无法进一步交换了。比较一下列表表示法和图 5 所示的树表示法进行的一系列交换还是很有帮助的。

下面是二叉堆的实现

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0


    def percUp(self,i):
        while i // 2 > 0:
          if self.heapList[i] < self.heapList[i // 2]:
             tmp = self.heapList[i // 2]
             self.heapList[i // 2] = self.heapList[i]
             self.heapList[i] = tmp
          i = i // 2

    def insert(self,k):
      self.heapList.append(k)
      self.currentSize = self.currentSize + 1
      self.percUp(self.currentSize)

    def percDown(self,i):
      while (i * 2) <= self.currentSize:
          mc = self.minChild(i)
          if self.heapList[i] > self.heapList[mc]:
              tmp = self.heapList[i]
              self.heapList[i] = self.heapList[mc]
              self.heapList[mc] = tmp
          i = mc

    def minChild(self,i):
      if i * 2 + 1 > self.currentSize:
          return i * 2
      else:
          if self.heapList[i*2] < self.heapList[i*2+1]:
              return i * 2
          else:
              return i * 2 + 1

    def delMin(self):
      retval = self.heapList[1]
      self.heapList[1] = self.heapList[self.currentSize]
      self.currentSize = self.currentSize - 1
      self.heapList.pop()
      self.percDown(1)
      return retval

    def buildHeap(self,alist):
      i = len(alist) // 2
      self.currentSize = len(alist)
      self.heapList = [0] + alist[:]
      while (i > 0):
          self.percDown(i)
          i = i - 1

bh = BinHeap()
bh.buildHeap([9,5,6,2,3])

print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。

算法步骤
1.创建一个堆 H[0……n-1]；
2.把堆首（最大值）和堆尾互换；
3.把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
4.重复步骤 2，直到堆的尺寸为 1。

排序动画过程解释

1.首先，将所有的数字存储在堆中
2.按大顶堆构建堆，其中大顶堆的一个特性是数据将被从大到小取出，将取出的数字按照相反的顺序进行排列，数字就完成了排序
3.在这里数字 5 先入堆
4.数字 2 入堆
5.数字 7 入堆， 7 此时是最后一个节点，与最后一个非叶子节点（也就是数字 5 ）进行比较，由于 7 大于 5 ，所以 7 和 5 交互
6.按照上述的操作将所有数字入堆，然后从左到右，从上到下进行调整，构造出大顶堆
7.入堆完成之后，将堆顶元素取出，将末尾元素置于堆顶，重新调整结构，使其满足堆定义
8.堆顶元素数字 7 取出，末尾元素数字 4 置于堆顶，为了维护好大顶堆的定义，最后一个非叶子节点数字 5 与 4 比较，而后交换两个数字的位置
9.反复执行调整+交换步骤，直到整个序列有序

class HeapSort:
    def heapSort(self, A, n):
        # write code here
        for i in range(n/2+1, -1, -1):
            self.MaxHeapFixDown(A, i, n);
        for i in range(n-1, -1, -1):
            A[0], A[i] = A[i], A[0]
            self.MaxHeapFixDown(A, 0, i)
        return A
      
    def MaxHeapFixDown(self, A, i, n):
        tmp = A[i]
        j = 2*i+1
        while(j<n):
            if j+1<n and A[j+1] > A[j]:
                j+=1
            if A[j] < tmp:
                break
            A[i] = A[j]
            i = j
            j = 2*i+1
        A[i] = tmp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

算法时间复杂度是O(nlogn)，和快速排序是一样的。但是实际开发当中，快速排序还是要比堆排序性能更好。

为什么？

1.堆排序数据访问的方式没有快速排序友好

对于快排来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的。堆排序中最重要的操作就是数据的堆化，会跳着访问，所以，这样对CPU缓存是不友好的。

2.对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快排。

讲排序的时候，有两个概念：有序度和逆序度。对于基于比较的排序算法来说，整个排序过程就是由两个基本的操作组成：比较和交换。快排数据交换的次数不会比逆序度多。

但是堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有序度降低。对于一组已经有序的数据来说，经过建堆，数据反而更无序了。

总结：堆是一种完全二叉树。最大的特性：每个节点的值都大于等于（或小于等于）其子树节点的值。所以有大顶堆和小顶堆。

堆中有；两个重要的操作是插入一个数据和删除堆顶的数据。这两个操作都要用到堆化。插入一个数据的时候，把新的数据放到数组的最后，然后从下往上堆化；删除堆顶数据的时候，把数组中的最后一个元素放到堆顶，然后从上到下堆化。这两个操作时间复杂度都是O(logn)

还有堆的一个应用——堆排序。包括两个过程，建堆和排序。将下标从$\frac{n}{2}$到1的节点，依次进行从上到下的堆化操作，然后就可以将数组中的数据组织成堆这种数据结构。接下来迭代地将堆顶的元素放到堆的末尾，并将堆的大小减一，然后再堆化，重复这个过程，直到堆中只剩下一个元素，整个数组中的数据就有序排列了。