基本算法2

最小堆优先队列：
class YOUXIAN(object):
    def __init__(self):
        self._lst=[0]
        self._size=0
    def show(self):
        print(self._lst)
    def addOne(self,v):
        self._size += 1
        self._lst.append(v)
        pos=self._size
        while pos//2 >0:
            if self._lst[pos//2]>self._lst[pos]:
                self._lst[pos//2], self._lst[pos]=self._lst[pos],self._lst[pos//2]
            pos=pos//2
            # else:
            #     break
    def legal(self,pos):
        if pos*2+1>self._size:
            return pos*2
        else:
            if self._lst[pos*2]>self._lst[pos*2+1]:
                return pos*2+1
            else:
                return pos*2

    def delmin(self):
        if self._size >0:
            ret=self._lst[1]
            self._lst[1]=self._lst[self._size]
            self._size += -1
            self._lst.pop()
            pos=1
            while pos*2 <=self._size:
                newpos=self.legal(pos)
                if self._lst[pos]>self._lst[newpos]:
                    self._lst[pos],self._lst[newpos]=self._lst[newpos],self._lst[pos]
                pos=newpos
            return ret

    def buildHeap(self,alist):
        for i in alist:
            self.addOne(i)



bh = YOUXIAN()
bh.buildHeap([9,5,6,2,3])
bh.show()

最短路径：


import heapq
 
import sys
class YouXianQueue(object):
    def __init__(self):
        self._lst=[]
        self._index=0

    def push(self,item,prime):
        heapq.heappush(self._lst,(prime,self._index,item))
        self._index +=1
    def show(self):
        print(self._lst)

    def len(self):
        return len(self._lst)

    def change(self,item,priority):
        try:
            temp=None
            for num,i in enumerate(self._lst):
                if i[-1] == item:

                    temp=num
                    break

            temp_v=self._lst[temp]
            del self._lst[temp]

            heapq.heappush(self._lst,(priority,temp_v[1],temp_v[2]))
        except Exception as ex:
            print(ex)

    def pop(self):
        return  heapq.heappop(self._lst)[-1]

class NODE(object):
    def __init__(self,value):
        self._value=value
        self.connections={}
        self._parent=None
        self._dis=sys.maxsize

    def getWeight(self,item):
        return self.connections.get(item,0)
    def addNeibor(self,item,weight=1):
        self.connections[item]=weight

    @property
    def value(self):
        return self._value

    @value.setter
    def value(self,value):
        self._value=value
    @property
    def parent(self):
        return self._parent
    @parent.setter
    def parent(self,item):
        self._parent=item


    def getNeibor(self):
        return self.connections.keys()

    def setParent(self,item):
        self.parent=item

    @property
    def dis(self):
        return self._dis

    @dis.setter
    def dis(self,value):
        self._dis=value



class GRAPH(object):
    def __init__(self):
        self.sons={}
        self.size=0

    def addSon(self,value):
        self.sons[value]=NODE(value)
        self.size +=1

    def getSon(self,value):
        return self.sons.get(value,None)
    def getall(self):
        return  self.sons.values()

    def addEdge(self,value1,value2,weight=1):
        if value1 not in self.sons:
            self.addSon(value1)
        if value2 not in self.sons:
            self.addSon(value2)
        self.sons[value1].addNeibor(self.sons[value2],weight)

def genData(datas):
    g=GRAPH()
    for data in datas:
        g.addEdge(data[0],data[1],data[2])
    return g

def minPaht(g,start):
    path=YouXianQueue()
    first=g.getSon(start)
    first.dis=0
    first.parent=None
    for son in g.getall():
        path.push(son,son.dis)
    while path.len()>0:
        current=path.pop()
        for son in current.getNeibor():
            newdis=current.dis+current.getWeight(son)
            if son.dis > newdis:
                son.dis=newdis
                son.parent=current
                path.change(son,newdis)


def showPah(g,dest):
    item=g.getSon(dest)
    print(item.value)
    while item.parent:
        item=item.parent
        print(item.value)

def main():
    datas=[('u','v',2),('u','w',5),('u','x',1),('v','u',2),('v','w',3),('v','x',2),
('w','v',3),('w','u',5),('w','x',3),('w','y',1),('w','z',5),('z','w',5),('z','y',1),
    ('y','z',1),('y','w',1),('y','x',1),('x','y',1),('x','w',3),('x','v',2),('x','u',1)]

    g=genData(datas)
    minPaht(g,"u")
    showPah(g,'y')

最小加权树：
import heapq
import sys
class YouXianQueue(object):
    def __init__(self):
        self._lst=[]
        self._index=0

    def push(self,item,prime):
        heapq.heappush(self._lst,(prime,self._index,item))
        self._index +=1
    def show(self):
        print(self._lst)

    def __contains__(self, item):
        temp=[data[2] for data in self._lst]
        return item in temp

    def len(self):
        return len(self._lst)

    def change(self,item,priority):
        try:
            temp=None
            for num,i in enumerate(self._lst):
                if i[-1] == item:

                    temp=num
                    break

            temp_v=self._lst[temp]
            del self._lst[temp]

            heapq.heappush(self._lst,(priority,temp_v[1],temp_v[2]))
        except Exception as ex:
            print(ex)

    def pop(self):
        return  heapq.heappop(self._lst)[-1]

class NODE(object):
    def __init__(self,value):
        self._value=value
        self.connections={}
        self._parent=None
        self._dis=sys.maxsize

    def getWeight(self,item):
        return self.connections.get(item,0)
    def addNeibor(self,item,weight=1):
        self.connections[item]=weight

    @property
    def value(self):
        return self._value

    @value.setter
    def value(self,value):
        self._value=value
    @property
    def parent(self):
        return self._parent
    @parent.setter
    def parent(self,item):
        self._parent=item


    def getNeibor(self):
        return self.connections.keys()

    def setParent(self,item):
        self.parent=item

    @property
    def dis(self):
        return self._dis

    @dis.setter
    def dis(self,value):
        self._dis=value



class GRAPH(object):
    def __init__(self):
        self.sons={}
        self.size=0

    def addSon(self,value):
        self.sons[value]=NODE(value)
        self.size +=1

    def getSon(self,value):
        return self.sons.get(value,None)
    def getall(self):
        return  self.sons.values()

    def addEdge(self,value1,value2,weight=1):
        if value1 not in self.sons:
            self.addSon(value1)
        if value2 not in self.sons:
            self.addSon(value2)
        self.sons[value1].addNeibor(self.sons[value2],weight)

def genData(datas):
    g=GRAPH()
    for data in datas:
        g.addEdge(data[0],data[1],data[2])
    return g

def minPaht(g,start):
    path=YouXianQueue()
    first=g.getSon(start)
    first.dis=0
    first.parent=None
    for son in g.getall():
        path.push(son,son.dis)
    while path.len()>0:
        current=path.pop()
        for son in current.getNeibor():
            newdis=current.dis+current.getWeight(son)
            if son in path and son.dis > newdis:
                son.dis=newdis
                son.parent=current
                path.change(son,newdis)


def showPah(g,dest):
    item=g.getSon(dest)
    print(item.value)
    while item.parent:
        item=item.parent
        print(item.value)

def main():
    datas=[('A','B',2),('A','C',3),('B','C',1),('B','D',1),('B','E',4),('E','F',1),('F','C',5),('F','G',1),('D','E',1)]
    temp=[]
    for data in datas:
        temp.append(data)
        temp.append((data[1],data[0],data[2]))
    g=genData(temp)
    minPaht(g,"A")
    names=['A','B','C','D','E','F','G']
    sum=0
    for name in names:
        sum += g.getSon(name).dis
    print('sum',sum)

main()