在Python中实现平衡大小的二叉树堆
我正在做一些作业，需要完成一个大小平衡的二叉树堆的实现，但在我的入队函数上遇到了一些麻烦。老师给了我们一些代码作为起点，但我对如何访问这些类有点困惑。在下面的代码中，只有我写的空函数（如果没有传入树的话，它是无法工作的，但我现在对此不太担心）和入队函数，它能添加前面三个元素（我不确定它们是否添加正确），然后就失败了。我觉得我在入队函数上遇到的问题是，我不知道怎么把TreeNode添加到堆里，也不太清楚如何正确访问像“heap.lchild.size”这样的东西，如果这甚至可能的话。最后那部分被注释掉的代码是用来测试我们完成的程序的，但我把它注释掉了，并复制了一部分只用来测试入队函数。
import random
class TreeNode( object ):
"""
A (non-empty) binary tree node for a size-balanced binary tree heap.
SLOTS:
key: Orderable
value: Any
size: NatNum; the size of the sub-tree rooted at this node
parent: NoneType|TreeNode; the parent node
lchild: NoneType|TreeNode; the node of the left sub-tree
rchild: NoneType|TreeNode; the node of the right sub-tree
"""
__slots__ = ( 'key', 'value', 'size', 'parent', 'lchild', 'rchild' )
def __init__( self, key, value, parent ):
self.key = key
self.value = value
self.size = 1
self.parent = parent
self.lchild = None
self.rchild = None
def __str__( self ):
slchild = str(self.lchild)
srchild = str(self.rchild)
skv = str((self.key, self.value)) + " <" + str(self.size) + ">"
pad = " " * (len(skv) + 1)
s = ""
for l in str(self.lchild).split('\n'):
s += pad + l + "\n"
s += skv + "\n"
for l in str(self.rchild).split('\n'):
s += pad + l + "\n"
return s[:-1]
class SBBTreeHeap( object ):
"""
A size-balanced binary tree heap.
SLOTS:
root: NoneType|TreeNode
"""
__slots__ = ( 'root' )
def __init__( self ):
self.root = None
def __str__( self ):
return str(self.root)
def checkNode( node, parent ):
"""
checkNode: NoneType|TreeNode NoneType|TreeNode -> Tuple(NatNum, Boolean, Boolean, Boolean, Boolean)
Checks that the node correctly records size information,
correctly records parent information, satisfies the
size-balanced property, and satisfies the heap property.
"""
if node == None:
return 0, True, True, True, True
else:
lsize, lsizeOk, lparentOk, lbalanceProp, lheapProp = checkNode( node.lchild, node )
rsize, rsizeOk, rparentOk, rbalanceProp, rheapProp = checkNode( node.rchild, node )
nsize = lsize + 1 + rsize
nsizeOk = node.size == nsize
sizeOk = lsizeOk and rsizeOk and nsizeOk
nparentOk = node.parent == parent
parentOk = lparentOk and rparentOk and nparentOk
nbalanceProp = abs(lsize - rsize) <= 1
balanceProp = lbalanceProp and rbalanceProp and nbalanceProp
nheapProp = True
if (node.lchild != None) and (node.lchild.key < node.key):
nheapProp = False
if (node.rchild != None) and (node.rchild.key < node.key):
nheapProp = False
heapProp = lheapProp and rheapProp and nheapProp
return nsize, sizeOk, parentOk, balanceProp, heapProp
def checkHeap( heap ):
"""
checkHeap: SBBTreeHeap -> NoneType
Checks that the heap is a size-balanced binary tree heap.
"""
__, sizeOk, parentOk, balanceProp, heapProp = checkNode( heap.root, None )
if not sizeOk:
print("** ERROR ** Heap nodes do not correctly record size information.")
if not parentOk:
print("** ERROR ** Heap nodes do not correctly record parent information.")
if not balanceProp:
print("** Error ** Heap does not satisfy size-balanced property.")
if not heapProp:
print("** Error ** Heap does not satisfy heap property.")
assert(sizeOk and parentOk and balanceProp and heapProp)
return
def empty(heap):
"""
empty: SBBTreeHeap -> Boolean
Returns True if the heap is empty and False if the heap is non-empty.
Raises TypeError if heap is not an instance of SBBTreeHeap.
Must be an O(1) operation.
"""
if not SBBTreeHeap:
print("** Error ** Heap is not an instance of SBBTreeHeap.")
if heap.root == None:
return True
else:
return False
def enqueue( heap, key, value ):
"""
enqueue: SBBTreeHeap Orderable Any -> NoneType
Adds the key/value pair to the heap.
Raises TypeError if heap is not an instance of SBBTreeHeap.
Must be an O(log n) operation.
"""
# print('heap has entered enqueue')
# print(str(heap))
if empty(heap):
heap.root = TreeNode(key, value, None)
if heap.root.size < 3:
if heap.root.lchild != None:
if heap.root.rchild == None:
heap.root.rchild = TreeNode(key, value, heap.root)
heap.root.size += 1
elif heap.root.lchild == None:
heap.root.lchild = TreeNode(key, value, heap.root)
heap.root.size += 1
else:
if heap.lchild.size >= heap.rchild.size:
heap.lchild = TreeNode(key, value, heap.root)
else:
heap.rchild = TreeNode(key, value, heap.root)
def frontMin( heap ):
"""
frontMin: SBBTreeHeap -> Tuple(Orderable, Any)
Returns (and does not remove) the minimum key/value in the heap.
Raises TypeError if heap is not an instance of SBBTreeHeap.
Raises IndexError if heap is empty.
Precondition: not empty(heap)
Must be an O(1) operation.
"""
## COMPLETE frontMin FUNCTION ##
def dequeueMin( heap ):
"""
dequeueMin: SBBTreeHeap -> NoneType
Removes (and does not return) the minimum key/value in the heap.
Raises TypeError if heap is not an instance of SBBTreeHeap.
Raises IndexError if heap is empty.
Precondition: not empty(heap)
Must be an O(log n) operation.
"""
## COMPLETE dequeueMin FUNCTION ##
def heapsort( l ):
"""
heapsort: ListOfOrderable -> ListOfOrderable
Returns a list that has the same elements as l, but in ascending order.
The implementation must a size-balanced binary tree heap to sort the elements.
Must be an O(n log n) operation.
"""
## COMPLETE heapsort FUNCTION ##
######################################################################
######################################################################
if __name__ == "__main__":
# R = random.Random()
# R.seed(0)
# print(">>> h = SBBTreeHeap()");
# h = SBBTreeHeap()
# print(h)
# checkHeap(h)
# for v in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
# k = R.randint(0,99)
# print(">>> enqueue(h," + str(k) + "," + str(v) + ")")
# enqueue(h, k, v)
# print(h)
# checkHeap(h)
# while not empty(h):
# print(">>> k, v = frontMin(h)")
# k, v = frontMin(h)
# print((k, v))
# print(">>> dequeueMin(h)")
# dequeueMin(h)
# print(h)
# checkHeap(h)
# for i in range(4):
# l = []
# for x in range(2 ** (i + 2)):
# l.append(R.randint(0,99))
# print(" l = " + str(l))
# sl = heapsort(l)
# print("sl = " + str(sl))
#
#heap = SBBTreeHeap()
#print(empty(heap))
R = random.Random()
R.seed(0)
print(">>> h = SBBTreeHeap()");
h = SBBTreeHeap()
print(h)
checkHeap(h)
for v in 'ABCDEFG':
k = R.randint(0,99)
print(">>> enqueue(h," + str(k) + "," + str(v) + ")")
enqueue(h, k, v)
print(h)
checkHeap(h)
2 个回答
0
别担心 if size < 3 这种情况。
我建议你先写出 frontMin，这个应该比较简单。
然后你可以写 heapsort。这个主要是调用其他方法，不需要自己做太复杂的事情。
在添加或 enqueue 的时候，你需要考虑四种情况：
- 左边和右边都是空的
- 右边是空的
- 左边是空的
- 两个都不是空的
这些情况中，有些比较简单，有些就复杂一些。
dequeueMin 也会有类似的考虑。
我建议你仔细阅读一下 这个维基页面。
我建议你先构建一个二叉堆，然后确保它的大小是平衡的。
有些情况很简单，有些就不那么简单了。
0
你现在的做法已经有了一个不错的开端，因为它能处理前面三个元素。要让它适用于所有情况，你需要知道每个新的树节点应该放在哪里。对于普通的二叉堆，我们知道新节点会放在底层最左边的空位上。但对于大小平衡的二叉树，它需要满足一个条件：“每个节点的两个子树的大小差不能超过1”（这是实验手册第一页的内容）。为了确保这一点，你需要交替地将新节点添加到根节点的左子树和右子树。
如果一个树节点的左子树大小是
k，而右子树的大小是k-1，那么你应该把新节点添加到右子树（如果不这样做，左子树和右子树的大小差就会变成2）。如果一个树节点的左子树和右子树大小相同，那么你可以随便选择将新节点添加到哪个子树，只要保持一致就行。
这两点适用于当前节点的大小大于2的情况（也就是说，它有左右两个子节点）。另外两种情况是节点的大小为2（有1个子节点）或1（没有子节点）。如果大小是2，就把新节点添加到空的那一侧；如果大小是1，你可以选择将新节点添加到哪个侧，但要保持一致。一旦找到合适的位置添加新节点，就要向上调整，直到它的值小于父节点的值。
出队的过程稍微复杂一些。你需要找到你刚添加的节点在堆中的位置，把它和根节点交换，然后移除这个位置（现在这个位置有根节点的值），接着向下调整根节点，直到它的值小于子节点的值（如果有两个子节点，就取较小的那个子节点的值）。
在进行入队和出队操作时，记得在向上或向下调整堆的同时更新受影响节点的大小。
希望这些能帮到你。