Size balanced binary tree heap in python

Question

So I am working on some homework and I have to complete a size balanced binary tree heap implementation, and I'm having some trouble with my enqueue function. We were given some code to start with and I am a little confused about how to access the classes and such. Of the following code, the only things that I have written are the empty function (which doesn't work if it is not passed a tree, but I am not too worried about that right now.) and the enqueue function which does add the first 3 elements (im not sure if it adds them correctly) and then fails after that. The problem I think I am having with the enqueue function is that I dont know exactly how to add the TreeNode to the heap, and how to access things like "heap.lchild.size' correctly, if thats even possible. The part at the end that is commented out is supposed to be used to test our program when we are finished, but I commented it out and copied a piece of it that just tests the enqueue function.

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)

it was how the original code we were given was formatted, that and I am not really sure how to do it any other way. — user1204470, Feb 12 '12 at 03:31
There's not much reason to use `__slots__` here that I can see. http://stackoverflow.com/questions/472000/python-slots — Daenyth, Feb 13 '12 at 15:46

Ivo · Answer 1 · 2012-02-12T01:30:00.143

0

Don't worry about if size < 3 stuff.

I'd suggest you write out frontMin first, that should be easy.

Then you can write heapsort. It should mainly call other methods, not do any hard work itself.

When adding/enqueueing, you have four cases to worry about:

left and right are both None
right is None
left is None
neither are None

Some of these cases are much simpler than others.

dequeueMin will have the same sort of considerations.

I suggest you read the wiki page thoroughly.

I would suggest just building a binary heap first, and then making sure it's size balanced.

Some of those cases are easy, some not.

edited Feb 12 '12 at 01:30

answered Feb 12 '12 at 01:24

Ivo

5,378
2
18
18

Thank you very much, both answers helped me think about it in the right way to figure everything out. – user1204470 Feb 14 '12 at 17:06

score 0 · Accepted Answer · answered Feb 12 '12 at 14:37

What you have is a good start, since it does work for the first 3 elements. To make it work for all cases, you need to know where each new TreeNode should go. In the case of a normal binary heap, we know the new node would go in the leftmost free spot on the bottom level. But for a size-balanced binary tree, it needs to satisfy the constraint that "the sizes of the two subtrees of every node never differ by more than 1" (page 1 of lab handout). To make sure this holds true, you need to alternate adding new nodes to root's left child and right child.

If a TreeNode's left child has a size of k, and the right child has size k-1, you want to add to the right subtree (If you don't, the sizes of left and right subtrees will differ by 2).
If a TreeNode's left and right children both have the same size, then it doesn't matter which subtree you add the new node to, as long as your consistent.

Those two points cover when the size of the current node your looking at is greater than 2 (meaning it has both a left and right child node). The other 2 cases are when the node either has a size of 2 (has 1 child node) or 1 (has 0 child nodes). If the size is 2, just add the new node to whichever side is empty, and if the size is 1, you get to choose which side to add the new node, but be consistent. Once you found a place to add the new node, sift up while its key is less than its parents key.

Dequeue is a little bit more complicated. You need to find the position in the heap that you just added, swap it with the root, remove that position (which now has the root's key/value), and sift down the root node while its key is greater than its child's key (the smallest child's key in the case of two children).

For both enqueue and dequeue, remember to update the sizes of the effected nodes while you're going down or up the heap.

Hope that helps.

Thank you very much, I finally figured everything out and got it working, Now I just have to comment it and I'm good to go. — user1204470, Feb 14 '12 at 17:05
Glad I could help a fellow CS 242 student. Good luck on Cable Car — Pat Needham, Feb 17 '12 at 18:53

Size balanced binary tree heap in python

2 Answers2