二叉堆

二叉堆时一个我目前掌握的一个比较复杂（对我来说）的数据结构了。特地用python写了一个，虽然python提供现成的二叉堆这个数据结构，效率肯定时吊打我写的这个东东了，不过练习一些也是好事。

写二叉堆时自己犯的几个错误或需要注意的地方：

1.堆的开始是0还是1，导致后边数列的序号应该是count还是count+1还是count-1
2.堆的count变化应该写在什么位置，比如这里-shiftDown中的count=j这个命令我写在了if里边，导致有时候会出现死循环。
3.注意越界判断。

自己实现的一个二叉堆：

import random
class zuixiaodui:
    _count=0
    _capacity=0
    _data=[0]
    def __init__(self,capacity):
        self._capacity=capacity
        self._data=[0]*capacity

    def _shiftUp(self,count):
        if count<=self._count and count>0:
            while self._data[count]<self._data[count/2] :
                self._data[count],self._data[count/2]=self._data[count/2],self._data[count]
                count=count/2

    def _shiftDown(self,count):
        if count>0:
            while count*2 < self._count:
                j=count*2
                if j>self._count:
                    return
                elif self._data[j] > self._data[j+1] and j+1 < self._count:
                    j=j+1

                if self._data[count]>self._data[j]:
                    self._data[count],self._data[j]=self._data[j],self._data[count]
                count=j



    def insert(self,value):
        if self._count+1<self._capacity:
            self._count+=1
            self._data[self._count]=value
            self._shiftUp(self._count)
        else:
            print 'FULL'

    def extractMin(self):
        item=self._data[1]
        self._data[1]=self._data[self._count]
        self._data[self._count]=0
        self._count-=1
        self._shiftDown(1)
        return item

    def size(self):
        return self._count

    def isEmpty(self):
        return self._count==0
    def getItem(self,i):
        return  self._data[i]



if __name__ == '__main__':
    c=zuixiaodui(11)
    for i in range(10):
        c.insert(random.randint(1,10))
    print c.isEmpty(),c.size()

    for i in range(10):
        print c.extractMin()