min max heap implementation in python

minmaxheap.py

from math import log, floor, pow


class MinMaxHeap(object):
    """an implementation of min-max heap using an array,
        which starts at 1 (ignores 0th element)
    """

    def __init__(self, array=[]):
        super(MinMaxHeap, self).__init__()
        self.heap = [0]
        for i in array:
            self.Insert(i)

    def Insert(self, value):
        """place value at an available leaf, then bubble up from there"""
        self.heap = self.heap + [value]
        self.BubbleUp(len(self.heap) - 1)

    def DeleteAt(self, position):
        """delete given position"""
        self.heap[position] = self.heap[-1]
        del(self.heap[-1])
        self.TrickleDown(position)

    def Index(self, value):
        return self.heap.index(value)

    def PeekMax(self):
        if len(self.heap) > 1:
            return self.heap[1]
        else:
            raise Exception

    def PeekMin(self):
        size = len(self.heap)
        if size > 1:
            c = [self.heap[1]]
            if size >= 2:
                c = c + [self.heap[2]]
            if size >= 3:
                c = c + [self.heap[3]]
            return min(c)
        else:
            raise Exception

    def PopMax(self):
        m = self.PeekMax()
        mi = self.Index(m)
        self.DeleteAt(mi)
        return m

    def PopMin(self):
        m = self.PeekMin()
        mi = self.Index(m)
        self.DeleteAt(mi)
        return m

    def TrickleDown(self, position):
        """delete key at position"""
        if self.OnMinLevel(position):
            self.TrickleDownMin(position)
        else:
            self.TrickleDownMax(position)

    def TrickleDownMin(self, position):
        if self.HasChildren(position):
            min_pair = self.SortPairs(self.ChildrenAndGrandChildren(position))[0]
            m = min_pair[0]  # index of smallest kid
            if self.IsGrandChild(position, m):
                if self.heap[m] < self.heap[position]:
                    self.Swap(m, position)
                    if self.heap[m] > self.heap[self.Parent(m)]:
                        self.Swap(m, self.Parent(m))
                    self.TrickleDownMin(m)
            # if not grandchild, m must be a child
            else:
                if self.heap[m] < self.heap[position]:
                    self.Swap(m, position)
        else:
            pass

    def TrickleDownMax(self, position):
        if self.HasChildren(position):
            max_pair = self.SortPairs(self.ChildrenAndGrandChildren(position))[-1]
            m = max_pair[0]  # index of smallest kid
            if self.IsGrandChild(position, m):
                if self.heap[m] > self.heap[position]:
                    self.Swap(m, position)
                    if self.heap[m] < self.heap[self.Parent(m)]:
                        self.Swap(m, self.Parent(m))
                    self.TrickleDownMax(m)
            # if not grandchild, m must be a child
            else:
                if self.heap[m] > self.heap[position]:
                    self.Swap(m, position)
        else:
            pass

    def BubbleUp(self, position):
        if self.OnMinLevel(position):
            if self.HasParent(position):
                if self.heap[position] > self.heap[self.Parent(position)]:
                    self.Swap(position, self.Parent(position))
                    self.BubbleUpMax(self.Parent(position))
                else:
                    self.BubbleUpMin(position)
        else:
            if self.HasParent(position):
                if self.heap[position] < self.heap[self.Parent(position)]:
                    self.Swap(position, self.Parent(position))
                    self.BubbleUpMin(self.Parent(position))
                else:
                    self.BubbleUpMax(position)

    def BubbleUpMin(self, position):
        grandparent = self.Parent(self.Parent(position))
        if self.HasGrandParent(position):
            if self.heap[position] < self.heap[grandparent]:
                self.Swap(position, grandparent)
                self.BubbleUpMin(grandparent)

    def BubbleUpMax(self, position):
        if self.HasGrandParent(position):
            grandparent = self.Parent(self.Parent(position))
            if self.heap[position] > self.heap[grandparent]:
                self.Swap(position, grandparent)
                self.BubbleUpMax(grandparent)

    def Swap(self, a, b):
        """swap values between a and b"""
        a_val = self.heap[a]
        b_val = self.heap[b]
        self.heap[a] = b_val
        self.heap[b] = a_val

    def Parent(self, child):
        """return child's parent"""
        return int(child) / 2

    def IsGrandChild(self, parent, grand_child):
        """tell whether grand_child is parent's grandchild or not"""
        if self.HasGrandChildren(parent):
            size = len(self.heap)
            if grand_child < size:
                return True
            else:
                return False
        else:
            return False

    def SortPairs(self, list_of_pairs):
        """return 2-tuple representing smallest, sorted by value in second"""
        return sorted(list_of_pairs, key=lambda tup: tup[1])

    def ChildrenAndGrandChildren(self, position):
        """
        return list of children's and grandchildren's indices
        Don't call if position doesn't have children!
        """
        if self.HasChildren(position):
            a = []
            a = a + [(int(pow(2, position)), self.heap[int(pow(2, position))])]
            a = a + [(int(pow(2, position)) + 1, self.heap[int(pow(2, position)) + 1])]
            if self.HasChildren(int(pow(2, position))):
                cpos = int(pow(2, position))
                a = a + [(int(pow(2, cpos)), self.heap[int(pow(2, cpos))])]
                a = a + [(int(pow(2, cpos)) + 1, self.heap[int(pow(2, cpos)) + 1])]
            if self.HasChildren(int(pow(2, position)) + 1):
                cpos = int(pow(2, position)) + 1
                a = a + [(int(pow(2, cpos)), self.heap[int(pow(2, cpos))])]
                a = a + [(int(pow(2, cpos)) + 1, self.heap[int(pow(2, cpos)) + 1])]
            return a
        else:
            raise Exception

    def HasParent(self, position):
        p = self.Parent(position)
        if p is not 0:
            return True
        else:
            return False

    def HasGrandParent(self, position):
        gp = self.Parent(self.Parent(position))
        if gp is not 0:
            return True
        else:
            return False

    def HasChildren(self, position):
        """check if 2^position and 2^(position)+1 exist"""
        size = len(self.heap)
        if (pow(2, position) < size) or ((pow(2, position) + 1) < size):
            return True
        else:
            return False

    def HasGrandChildren(self, position):
        """check if either of position's children have children of their own"""
        if self.HasChildren(int(pow(2, position))) or \
           self.HasChildren(int(pow(2, position)) + 1):
            return True
        else:
            return False

    def OnMinLevel(self, position):
        """returns bool - is it on a min level?"""
        test = self.OnLevel(position) % 2
        if test == 0:
            return False
        else:
            return True

    def OnMaxLevel(self, position):
        """returns bool - is it on a max level?"""
        test = self.OnLevel(position) % 2
        if test == 0:
            return True
        else:
            return False

    def OnLevel(self, position):
        """returns what level the key at position is on"""
        return floor(log(int(position), 2))

The DeleteAt does NOT work in all operations. For example, suppose we have the following min-max heap:

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    55    65    37    31

Now apply your DeleteAt algorithm to delete 55. You replace 55 with 31. You delete 55, and you obtain this:

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    31    65    37 

Now you TricleDown start from 31. TricleDown checks if we're in an even or odd level: we're in an odd level (3), so TricleDown calls TrickleDownMax starting from 31, but since 31 has no children, it stops. But if you observe that leaves the data structure in a state that is no more a min-max heap, because 54, which is at even level and therefore should be smaller than its descendants, is greater than 31, one of its descendants.

This is a max-min heap actually.

heap = MinMaxHeap()

# ignores 0th element as he stated
print heap.OnMinLevel(1) 
# False

Some modifications to make it a min-max heap:

    def OnMinLevel(self, position):
        """returns bool - is it on a min level?"""
        test = 1- self.OnLevel(position) % 2 # => inverse
        if test == 0:
            return False
        else:
            return True

    def OnMaxLevel(self, position):
        """returns bool - is it on a max level?"""
        test = 1- self.OnLevel(position) % 2 # => inverse
        if test == 0:
            return True
        else:
            return False

initialization is not efficient, could heapify the data, not insert one by one