python中大小平衡二叉树堆

Question

所以我正在做一些作业，我必须完成一个大小平衡的二叉树堆实现，并且我的入队函数遇到了一些问题。我们得到了一些开始的代码，我对如何访问类等有点困惑。在以下代码中，我编写的唯一内容是空函数（如果未传递树，则该函数不起作用，但我现在不太担心这一点。）和添加了队列函数前 3 个元素（我不确定它是否正确添加它们），然后失败。我认为我在使用 enqueue 函数时遇到的问题是，我不确切知道如何将 TreeNode 添加到堆中，以及如何正确访问“heap.lchild.size”之类的东西（如果可能的话）。被注释掉的 end 应该用于在完成后测试我们的程序，但我将其注释掉并复制了其中的一部分，仅测试排队功能。

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)

Answer 1

您所拥有的是一个好的开始，因为它确实适用于前 3 个元素。为了使其适用于所有情况，您需要知道每个新的 TreeNode 应该去哪里。在正常的二进制堆的情况下，我们知道新节点将位于底层最左边的空闲位置。但对于大小平衡的二叉树，它需要满足“每个节点的两个子树的大小相差不超过1”的约束（实验讲义第1页）。为了确保这一点成立，您需要交替向根的左子节点和右子节点添加新节点。

• 如果 TreeNode 的左子节点的大小为 k，右子节点的大小为 k-1，则您希望将其添加到右子树（如果您不这样做） t，左右子树的大小将相差 2)。

• 如果 TreeNode 的左子节点和右子节点的大小相同，那么将新节点添加到哪个子树并不重要，只要保持一致即可。

当您查看的当前节点的大小大于 2（意味着它同时具有左子节点和右子节点）时，这两点就涵盖了。其他 2 种情况是节点大小为 2（有 1 个子节点）或 1（有 0 个子节点）。如果大小为2，则只需将新节点添加到空的一侧，如果大小为1，则可以选择在哪一侧添加新节点，但要保持一致。一旦找到添加新节点的位置，当其键小于其父键时向上筛选。

出队有点复杂。您需要找到刚刚添加的堆中的位置，将其与根交换，删除该位置（现在具有根的键/值），然后在根节点的键大于其子节点的键时向下筛选根节点（如果有两个孩子，则为最小的孩子的钥匙）。

对于入队和出队，请记住在向下或向上堆时更新受影响节点的大小。

希望有帮助。

Answer 2

如果尺寸 则不必担心3 东西。

我建议你先写出 frontMin ，这应该很容易。

然后你就可以编写堆排序。它应该主要调用其他方法，本身不做任何艰苦的工作。

添加/入队时，您需要担心四种情况：

• left 和 right 都是 None
• right 是 None
• left 是 None
• 也不是 None

其中一些情况比其他情况简单得多。

dequeueMin 也会有同样的考虑。

我建议您仔细阅读wiki 页面。

我建议先构建一个二进制堆，然后确保其大小平衡。

其中一些情况很容易，有些则不然。