Max Order Priority Queue

maxpq.py

class MaxPQ(object):
    def __init__(self):
        # TODO initialize with array
        self._N = -1
        self._arr = []
        pass

    def _compare(self, a, b):
        if a > b: return 1
        if a < b: return -1
        return 0

    def _less(self, a, b):
        # array is zero based, but tree is 1 based
        # Subtract for real index
        a -= 1
        b -= 1
        return self._compare(self._arr[a], self._arr[b]) < 0

    def _exch(self, a, b):
        # array is zero based, but tree is 1 based
        # Subtract for real index
        a -= 1
        b -= 1
        tmp = self._arr[a]
        self._arr[a] = self._arr[b]
        self._arr[b] = tmp

    def is_empty(self):
        return self._N < 0

    def put(self, val):
        # Add new value to heap
        self._N += 1
        self._arr.append(val)

        # Restore heap order
        self._swim(self._N)

    def _swim(self, child):
        """
        If parent is smaller, exchange positions with child
        Parent exists at child's position / 2
        """

        # Tree is 1 based
        child += 1

        # as long as the child isn't root and smaller than
        # it's parent
        while child > 1 and self._less(child / 2, child):
            parent = child / 2
            self._exch(parent, child)
            child = parent

    # Get max value from heap
    def del_max(self):
        # Store value for returning
        val = self._arr[0]

        # Switch first item with last
        # `Exch` expects first item + 1 in PQ
        # So use 1 instead of 0, N will also be decremented
        self._exch(1, self._N + 1)

        # get rid of last element which is our max
        # from the pq
        self._arr[self._N] = None
        self._N -= 1

        # Restore heap order
        self._sink(0)

        return val

    def _sink(self, parent):
        """
        if parent becomes smaller than one of the children
        sink below greater parent until heap order is restored
        """

        parent += 1

        # Iterate over 2 * position of element in PQ
        # until we've reached the length of the PQ
        while parent * 2 <= self._N:
            # Level children exist at parent * 2 and parent * 2 + 1
            child = parent * 2

            # Check if children exists and if right child
            # is greater than left. If right is larger, inc
            # parent to position at right child
            if child < self._N and self._less(child, child + 1): child += 1

            # Check if child is greater than parent
            # If not, we are done
            if not self._less(parent, child): break

            # Child is greater, exchange positions
            self._exch(parent, child)

            # parent is now in childs position
            parent = child

    def __len__(self):
        # N is zero with 1 value in the PQ
        # and -1 with no values
        # so inc my by one :)
        return self._N + 1

    def __str__(self):
        return "<MaxPQ %d elements>" % len(self)

    def __repr__(self):
        return "<MaxPQ %r>" % self._arr

    @staticmethod
    def sort(pq):

        # ensure order
        N = len(pq)

        # Start at last level to the right in tree where elements have children
        k = N / 2

        # iterate over all elements in pq to ensure order
        while k >= 1:
            MaxPQ.sink(pq, k, N)
            # Check next element
            k -= 1

        while N > 1:
            # swap smallest with max
            MaxPQ.exch(pq, 1, N)

            # 'remove' element from iteration
            N -= 1

            # Bring smallest back down
            MaxPQ.sink(pq, 1, N)


    @staticmethod
    def sink(pq, parent, N):
        """
        if parent becomes smaller than one of the children
        sink below greater parent until heap order is restored
        """

        # Iterate over 2 * position of element in PQ
        # until we've reached the length of the PQ
        while parent * 2 <= N:
            # Level children exist at parent * 2
            child = parent * 2

            # Check if children exists and if right child
            # is greater than left. If right is larger, inc
            # parent to position at right child
            if child < N and MaxPQ.less(pq, child, child + 1): child += 1

            # Check if child is greater than parent
            # If not, we are done
            if not MaxPQ.less(pq, parent, child): break

            # Child is greater, exchange positions
            MaxPQ.exch(pq, child, parent)

            # parent is now in childs position
            parent = child

    @staticmethod
    def less(pq, a, b):
        return pq._less(a, b)

    @staticmethod
    def exch(pq, a, b):
        pq._exch(a, b)


if __name__ == "__main__":
    from random import shuffle

    N = 3
    pq = MaxPQ()

    arr = "abcnsnsdlkjl"

    for x in arr: pq.put(x)
    print "%r" % pq

    #while not pq.is_empty():
    #    print pq.del_max()

    MaxPQ.sort(pq)
    print "Sorted %r" % pq