jweinst1
2/16/2016 - 7:46 AM

practicing with a heap

practicing with a heap

#heap implementation

class HeapNode:
    
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
    def isleaf(self):
        return self.left is None and self.right is None
    def isopen(self):
        return self.left is None or self.right is None
    def isheaped(self):
        return self.left.value <= self.value and self.right.value <= self.value
    def swapleft(self):
        temp = self.left.value
        self.left.value = self.value
        self.value = temp
    def swapright(self):
        temp = self.right.value
        self.right.value = self.value
        self.value = temp
        
class Heap:
    
    def __init__(self, root):
        self.root = HeapNode(root)
    def insert(self, val):
        current = self.root
        #backtracer
        previous = current
        while not current.isopen():
            if current.left:
                previous = current
                current = current.left
            else:
                previous = current
                current = current.right
        if current.right:
            current.left = HeapNode(val)
        else:
            current.right = HeapNode(val)
        
#helper function to balance heap    
def countheap(hp):
    if hp is None:
        return 0
    elif hp.isleaf():
        return 1
    return 1 + countheap(hp.left) + countheap(hp.right)