二叉堆的Python实现
2019-03-25 本文已影响0人
盗梦者_56f2
二叉堆(binary heap)是一种特殊的堆,二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。
二叉堆一般用数组来表示。如果根节点在数组中的位置是1,第n个位置的子节点分别在2n和 2n+1。因此,第1个位置的子节点在2和3,第2个位置的子节点在4和5。以此类推。这种基于1的数组存储方式便于寻找父节点和子节点。
python
class Heap(object):
def __init__(self):
self.heap = [0]
self.size = 0
def isEmpty(self):
return self.size == 0
def findMin(self):
return self.heap[1]
def percUp(self, i):
while (i // 2) > 0:
if self.heap[i] < self.heap[i // 2]:
tmp = self.heap[i // 2]
self.heap[i // 2] = self.heap[i]
self.heap[i] = tmp
i = i // 2
def insert(self, k):
self.heap.append(k)
self.size = self.size + 1
self.percUp(self.size)
def percDown(self, i):
while (i * 2) <= self.size:
mc = self.minChild(i)
if self.heap[i] > self.heap[mc]:
tmp = self.heap[i]
self.heap[i] = self.heap[mc]
self.heap[mc] = tmp
i = mc
def minChild(self, i):
if i * 2 + 1 > self.size:
return i * 2
else:
if self.heap[i * 2] < self.heap[i * 2 + 1]:
return i * 2
else:
return i * 2 + 1
def delMin(self):
retval = self.heap[1]
self.heap[1] = self.heap[self.size]
self.size = self.size - 1
self.heap.pop()
self.percDown(1)
return retval
def buildHeap(self, lst):
i = len(lst) // 2
self.size = len(lst)
self.heap = [0] + lst[:]
while i > 0:
self.percDown(i)
i = i - 1
bh = Heap()
bh.buildHeap([9, 5, 6, 2, 3])
print(bh.delMin())
print(bh.findMin())
print(bh.size)