Fork me on GitHub

数据结构-堆

二叉堆

二叉堆是一种特殊的二叉树, 它总是保证一棵树的最小元素(最小堆)或者最大元素(最大堆)处于树根上, 常见的应用场景就是用于构建优先队列, 在jdk中Doug Lea所实现的ScheduledThreadPoolExecutor中就用到了最小堆;

1、最小堆

1.1 基本操作

BinaryHeap() 创建一个新的,空的二叉堆。
insert(k) 向堆添加一个新项。
findMin() 返回具有最小键值的项,并将项留在堆中。
delMin() 返回具有最小键值的项,从堆中删除该项。
如果堆是空的,isEmpty() 返回 true,否则返回 false。
size() 返回堆中的项数。
buildHeap(list) 从键列表构建一个新的堆。

注意,无论我们向堆中添加项的顺序是什么,每次都删除最小的。

1.2 实现

为了使我们的堆有效地工作,我们将利用二叉树的对数性质来表示我们的堆。 为了保证对数性能,我们必须保持树平衡。平衡二叉树在根的左和右子树中具有大致相同数量的节点。 在我们的堆实现中,我们通过创建一个 完整二叉树 来保持树平衡。 一个完整的二叉树是一个树,其中每个层都有其所有的节点,除了树的最底层,从左到右填充,如图。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap1.png

完整二叉树的另一个有趣的属性是,我们可以使用单个列表来表示它。 我们不需要使用节点和引用,甚至列表的列表。因为树是完整的,父节点的左子节点(在位置 p 处)是在列表中位置 2p 中找到的节点。 类似地,父节点的右子节点在列表中的位置 2p + 1。为了找到树中任意节点的父节点,我们可以简单地使用Python 的整数除法。 假定节点在列表中的位置 n,则父节点在位置 n/2。如图,请注意父级和子级之间是 2p 和 2p+1 关系。 树的列表表示以及完整的结构属性允许我们仅使用几个简单的数学运算来高效地遍历一个完整的二叉树。 我们将看到,这也是我们的二叉堆的有效实现。

我们用于堆中存储项的方法依赖于维护堆的排序属性。 堆的排序属性如下:在堆中,对于具有父 p 的每个节点 x,p 中的键小于或等于 x 中的键。 下图展示了具有堆顺序属性的完整二叉树。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap2.png

我们将开始实现一个二叉堆的构造函数。由于整个二叉堆可以由单个列表表示,所以构造函数将初始化列表和一个 currentSize 属性来跟踪堆的当前大小。一个空的二叉堆有一个单一的零作为 heapList 的第一个元素,这个零只是放那里,用于以后简单的整数除法。

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

将项添加到列表中最简单,最有效的方法是将项附加到列表的末尾。 它维护完整的树属性。但可能违反堆结构属性。可以编写一个方法,通过比较新添加的项与其父项,我们可以重新获得堆结构属性。 如果新添加的项小于其父项,则我们可以将项与其父项交换。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap3.png

注意,当我们完成一个项时,我们需要恢复新添加的项和父项之间的堆属性。 我们还需保留任何兄弟节点的堆属性。当然,如果新添加的项非常小,我们可能仍需要将其交换另一上层。事实上,我们可能需要交换到树的顶部。

percUp 方法,它在树中向上遍历一个新项,因为它需要去维护堆属性。注意,我们可以通过使用简单的整数除法来计算任意节点的父节点。 当前节点的父节点可以通过将当前节点的索引除以 2 来计算。

插入方法中的大部分工作都是由 percUp 完成的。 一旦一个新项被追加到树上,percUp 接管并正确定位新项。

1
2
3
4
5
6
7
8
9
10
11
12
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+=1
self.percUp(self.currentSize)

因为堆属性要求树的根是树中的最小项,所以找到最小项很容易。delMin 的难点在根被删除后恢复堆结构和堆顺序属性。 我们可以分两步恢复我们的堆。首先,我们将通过获取列表中的最后一个项并将其移动到根位置来恢复根项,保持我们的堆结构属性。 但是,我们可能已经破坏了我们的二叉堆的堆顺序属性。 第二,我们通过将新的根节点沿着树向下推到其正确位置来恢复堆顺序属性。 下图展示了将新的根节点移动到堆中的正确位置所需的交换序列。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap4.png

为了维护堆顺序属性,我们所需要做的是将根节点和最小的子节点交换。在初始交换之后,我们可以将节点和其子节点重复交换,直到节点被交换到正确的位置,使它小于两个子节点。

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
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):
'''
找到最小子节点:
如果右子节点不存在,那么最小子节点为左;
如果右子节点存在,判断左右的大小后再返回;
:param self:
:param i:
:return:
'''
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 -= 1
self.heapList.pop()
self.percDown(1)
return retval

为了完成我们对二叉堆的讨论,我们将看从一个列表构建整个堆的方法.如图,给定一个列表,通过一次插入一个键轻松地构建一个堆。由于你从一个项的列表开始,该列表是有序的,可以使用二分查找找到正确的位置,以大约 O(logn)O(logn) 操作的成本插入下一个键。 但是,请记住,在列表中间插入项可能需要 O(n)O(n) 操作来移动列表的其余部分,为新项腾出空间。 因此,要在堆中插入 n 个键,将需要总共 O(nlogn)O(nlogn) 操作。 然而,如果我们从整个列表开始,那么我们可以在 O(n)O(n) 操作中构建整个堆。Listing 6 展示了构建整个堆的代码。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/heap5.png

buildHeap 方法在 [9,6,5,2,3] 的初始树中的节点移动到其正确位置时所做的交换。虽然我们从树的中间开始,并以我们的方式回到根节点,percDown 方法确保最大的子节点总是沿着树向下移动。因为堆是一个完整的二叉树,超过中途点的任何节点都将是树叶,因此没有子节点。注意,当i = 1 时,我们从树的根节点向下交换,因此可能需要多次交换。正如你在上图最右边的两个树中可以看到的,首先 9 从根位置移出,但是 9 在树中向下移动一级之后,percDown 检查下一组子树,以确保它被推到下一层。在这种情况下,它与 3 进行第二次交换。现在 9 已经移动到树的最低层,不能进行进一步交换。将上图所示的这一系列交换的列表与树进行比较是有用的。

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

完整代码:

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
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())

我们可以在 O(n)中构建堆的断言可能看起来有点神秘,证明超出了范围。 然而,理解的关键是记住 logn 因子是从树的高度派生的。 对于buildHeap 中的大部分工作,树比 logn 短。
基于可以从 O(n) 时间构建堆的事实,你可以使用堆对列表在 O(nlogn)时间内排序,作为本章结尾的练习。

2、最大堆

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
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.maxChild(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 maxChild(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 + 1
else:
return i * 2

def delMax(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.heapList)
print(bh.currentSize)
print(bh.delMax())
print(bh.heapList)
print(bh.delMax())
支持,让我的文章更加优秀!