heap.py

class BinaryHeap:
    """Binary Heap implementation"""

    def __init__(self):
        """
        Initializing the heap with some values
                  T
               __/ \__
              /       \
             P         R
            / \       / \
          N     H    O   A
         / \   /
        E   I G
        """
        self.pq = [None, 'T', 'P', 'R', 'N', 'H', 'O', 'A', 'E', 'I', 'G']
        self.N = 10

    def swim(self, k):
        while k > 1 and self.less(k / 2, k):
            self.exch(k, k / 2)
            k = k / 2

    def sink(self, k):
        while 2 * k <= self.N:
            j = 2 * k
            if j < self.N and self.less(j, j + 1):
                j += 1
            if not self.less(k, j):
                break
            self.exch(k, j)
            k = j

    def less(self, i, j):
        return self.pq[i] < self.pq[j]

    def exch(self, i, j):
        t = self.pq[i]
        self.pq[i] = self.pq[j]
        self.pq[j] = t

    def insert(self, v):
        self.N += 1
        self.pq.append(v)
        self.swim(self.N)

    def del_max(self):
        max = self.pq[1]
        self.exch(1, self.N)
        self.pq[self.N] = None
        self.N -= 1
        self.sink(1)
        return max

    def is_empty(self):
        return self.N == 0

    def max(self):
        return self.pq[self.N]

    def size(self):
        return self.N

    def __str__(self):
        return str(self.pq)

    def heapsort(self):
        for i in range(self.N / 2, 0, -1):
            self.sink(i)
        while self.N > 1:
            self.exch(1, self.N)
            self.N -= 1
            self.sink(1)


pq = BinaryHeap()
pq.insert('S')
print pq