Heap – Python implementation

class Heap:
    #init
    def __init__(self):
        self.buffer = [0]
        self.size = 0
    #insert – key
    def insert(self, key):
        self.buffer.append(key)
        self.size = self.size + 1
        self.bublUp(self.size)
    #bublUp
    def bublUp(self, i):
        if i // 2 > 0:
            if self.buffer[i] < self.buffer[i // 2]:
                 swap(i,i // 2)
            self.bublUp(i // 2)
    #delMin
    def delMin(self):
        minVal = self.buffer[1]
        self.buffer[1] = self.buffer[self.size]
        self.buffer.pop()
        self.bublDown(1)
        return minVal
    #bublDown
    def bublDown(self, i):
        if i * 2 <= self.size:
            mc = self.minChild(i)
            if self.buffer[mc] < self.buffer[i]:
                self.swap(mc,i)
            self.bublDown(mc)
    #minChild
    def minChild(self,i):
        if 2*i + 1 > self.size:
            return 2 * i
        else:
            if self.buffer[2 * i] > self.buffer[2 * i + 1]:
                return 2 * i + 1
            else:
                return 2 * i
    #helper functions
    def swap(self, a, b):
        self.buffer[a],self.buffer[b] = self.buffer[b],self.buffer[a]
    def show(self):
        print self.buffer
h = Heap()
h.insert(4)
h.insert(4)
h.insert(8)
h.insert(9)
h.insert(4)
h.insert(12)
h.insert(9)
h.insert(11)
h.insert(13)
h.show()
print h.delMin()
h.show()
Advertisements

Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: