数据结构 --- 堆
一．堆的概念与结构
堆首先是一个二叉树，并且是一个特殊完全二叉树。对于完全二叉树的概念如果还不清楚，欢迎看我之前的一篇文章<<数据结构-二叉树>>。这里我们直接来理解堆的概念。
上面提到的堆是一种特殊的完全二叉树，怎么个特殊法呢？对于这颗给定的完全二叉树中任意给定节点都要满足堆属性：
- 其值比它的子节点的值都要大，并且根节点的值比其它节点的值都要大， 这种完全二叉树称为最大堆属性。
- 其值比它的子节点的值都要小，并且根节点的值比其它节点的值都要小， 这种完全二叉树称为最小堆属性。
如图所示，最大堆的最小堆示例。
我们也可以将上面具有堆属性的完全二叉树称为二叉堆。
二．堆的存储与构建
一般情况下，可以用链表或者数组存储。由于堆的是一颗完全二叉树，所以用数组存储堆，访问起来非常方便，所以当给定一个有初值的数组，我们可以首先将其表示成一颗完全二叉树，然后再进行调整，使其成为一个最大堆或者最小堆。
下面具体描述如何从一个一维数组构建出一个最大堆(最小堆同理)。
假设有一个n个元素的数组A如下图(图中画了6个元素作为示例)。
- 首先将数组A表示成一颗完全二叉树
这里简述一下，如何将数组表示成(看成)一颗完全二叉树的。这是由于完全二叉树的特点决定的。由于完全二叉树除了最下层元素可以不满，其它层元素都是满的，而且最下层元素是从左向右排列的。也就是说，缺少的只能是最右边的元素，基于此，用可以一维数组表示一颗完全二叉树:
- 若A[i]表示父节点,那么其子节点为A[2*i+1]和A[2*i+2], 其中2*i+1 和 2*i+2必须<= A的长度
- 若A[k]表示子节点,那么A[(k-1)/2]即是A[k]的父节点
根据以上两点，我们就可以将该一维数组看成一颗完全二叉树。比如根节点A[0]=1 那么 A[2*0+1] = A[1] = 6, 即6是1的左孩子节点。再比如A[5]=7, 那么7的父节点为A[(5-1)/2] = A[2] = 9, 即7的父节点是9。 对照上图，可以看到完全正确。
- 从第一个非叶子节点索引为n/2 – 1 开始. 这里n表示元素个数。
- 将当前节点i设置为最大节点largestNodeIndex。
- 比较当前节点i的值A[i]左孩子节点A[2*i+1] 的值, 如何 A[2*i+1] > A[i]，设置2*i+1 为最大节点largestNodeIndex。
比较A[largestNodeIndex] 和 当前节点的右孩子A[2*i + 2]的值，如果A[2*i + 2] > A[largestNodeIndex] 则设置2*i + 2为最大节点largestNodeIndex。
- 交换当前节点A[i]和A[largestNodeIndex]。
- 重复#3到#6直到最大堆构建完成。
至此最大堆构建完成。实现的python代码如下:
def heapify(arr, n, i):
largestNodeIndex= i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largestNodeIndex= l
if r < n and arr[largest] < arr[r]:
largestNodeIndex= r
if largest != i:
arr[i],arr[largestNodeIndex] = arr[largestNodeIndex],arr[i]
heapify(arr, n, largestNodeIndex)
三．如何向堆中插入元素
上面我们谈了堆的构建，现在我们来看如何向堆内插入一个元素。向堆内插入元素，我可以将该元素插入到堆的尾部，然后再根据情况将元素向上调整可以认为是堆的一次构建。这里依然以最大堆插入为例，具体图示描述如下：
- 将元素插入到堆的尾部
- 将元素进行向上调整，直到全部元素满足堆的性质。
插入过程的python代码实现如下：
def insert(array, newNum):
size = len(array)
if size == 0:
array.append(newNum)
else:
array.append(newNum);
for i in range((size//2)-1, -1, -1):
heapify(array, size, i)
四． 如何从堆中删除一个元素
这里依然以最大堆删除为例。删除的步骤如下：
- 选择要删除的元素，比如下图所示，要删除6。
- 将其与最后一个元素进行交换。
- 删除最后一个元素。
- 重新对删除后的堆进行调整，直到全部元素满足最大堆的性质。
删除过程的Python代码实现如下：
def deleteNode(array, num):
size = len(array)
i = 0
for i in range(0, size):
if num == array[i]:
break
array[i], array[size-1] = array[size-1], array[i]
array.remove(num)
for i in range((len(array)//2)-1, -1, -1):
heapify(array, len(array), i)
由于堆的特性，在最大堆中根节点就是最大元素，而在最小堆中，根节点就是最小元素，所以在最大堆查找最大元素和在最小堆查找最小元素十分方便。