棧，隊(duì)列，雙端隊(duì)列
無(wú)序鏈表汽抚，有序鏈表
二叉樹(shù)，堆伯病，二叉搜索樹(shù)造烁，AVL樹(shù)
圖
以及一些算法

coding: utf-8

u"""
線(xiàn)性數(shù)據(jù)結(jié)構(gòu), 棧, 隊(duì)列, deques, 容器結(jié)構(gòu), 數(shù)據(jù)項(xiàng)之間存在相對(duì)的位置
"""

class Stack(object):
u"""
棧 先進(jìn)后出
"""
def init(self):
self.items = []

def push(self, item):
    self.items.append(item) # O(1)

def pop(self):
    return self.items.pop() # O(1)

def peek(self):
    return self.items[-1]

def isEmpty(self):
    return self.items == []

def size(self):
    return len(self.items)

u"""
全括號(hào)匹配
((()))
()(())()
"""
def parChecker(symbolString):
stack = Stack()
index = 0

while index < len(symbolString):
    sym = symbolString[index]
    if sym == '(':
        stack.push(sym)
    else:
        if stack.isEmpty():
            return False
        else:
            stack.pop()

    index += 1

if stack.isEmpty():
    return True
return False

u"""
代碼括號(hào)匹配
"""
def codeChecker(symbolString):
stack = Stack()
index = 0

while index < len(symbolString):
    sym = symbolString[index]
    if sym in '([{':
        stack.push(sym)
    elif sym in ')]}':
        if stack.isEmpty():
            return False
        else:
            if not matches(stack.pop(), sym):
                return False

    index += 1

if stack.isEmpty():
    return True
return False

def matches(open, close):
opens = '([{'
closes = ')]}'
return opens.index(open) == closes.index(close)

u"""
任意進(jìn)制轉(zhuǎn)換
"""
def baseConverter(decNumber, base):
digits = '0123456789ABCDEF'

stack = Stack()

while decNumber > 0:
    stack.push(digits[decNumber % base])
    decNumber = decNumber // base

string = ''
while not stack.isEmpty():
    string += stack.pop()

return string

class Queue(object):
u"""
隊(duì)列 先進(jìn)先出
"""
def __init(self):
self.items = []

def isEmpty(self):
    return self.items == []

def size(self):
    return len(self.items)

def enqueue(self, item):
    self.items.insert(0, item) # O(n)

def dequeue(self):
    return self.items.pop() # O(1)

u"""
燙手山芋 循環(huán)傳遞n次 淘汰一個(gè) 直到最后幸存一個(gè)
"""
def hotPotato(namelist, num):
queue = Queue()

for name in namelist:
    queue.enqueue(name)

while queue.size() > 1:
    for i in range(num):
        queue.enqueue(queue.dequeue())

    queue.dequeue()
return queue.dequeue()

class Deque(object):
u"""
雙端隊(duì)列 可以同時(shí)從2端 進(jìn)出
"""
def init(self):
self.items = []

def isEmpty(self):
    return self.items == []

def size(self):
    return len(self.items)

def addFront(self, item):
    self.items.insert(0, item) # O(n)

def removeFront(self):
    return self.items.pop(0) # O(n)

def addRear(self, item):
    self.items.append(item) # O(1)

def removeRear(self):
    return self.items.pop() # O(1)

u"""
回文檢查 字符串前后一致
"""
def palchecker(aString):
deque = Deque()

for i in aString:
    deque.addRear(i)

while deque.size() > 1:
    if deque.removeFront() != deque.removeRear():
        return False
return True

u"""
鏈表 節(jié)點(diǎn)包含數(shù)據(jù)本身，并保存指向下一個(gè)節(jié)點(diǎn)的指針
"""
class Node(object):
def init(self, initdata):
self.data = initdata
self.next = None

def getData(self):
    return self.data

def getNext(self):
    return self.next

def setData(self, data):
    self.data = data

def setNext(self, node):
    self.next = node

u"""
無(wú)序鏈表
"""
class UnorderedList(object):
def init(self):
self.head = None

def isEmpty(self): # O(1)
    return self.head == None

def add(self, item): # O(1)
    node = Node(item)
    node.setNext(self.head)
    self.head = node

def size(self): # 遍歷鏈 O(n)
    count = 0
    current = self.head
    while current:
        count += 1
        current = current.getNext()
    return count

def search(self, item): # O(n)
    current = self.head
    while current:
        if current.getData() == item:
            return True
        current = current.getNext()
    return False

def remove(self, item): # O(n)
    previous = None
    current = self.head
    while current:
        if current.getData() == item:
            if previous is None:
                self.head = current.getNext()
            else:
                previous.setNext(current.getNext())
            return
        previous = current
        current = current.getNext()

def append(self, item): # O(n)
    node = Node(item)
    if self.head is None:
        self.head = node
        return
    current = self.head
    while current.getNext():
        current = current.getNext()
    current.setNext(node)

def index(self, item): # O(n)
    count = 0
    current = self.head
    while current:
        if current.getData() == item:
            return count
        current = current.getNext()
        count += 1

def insert(self, pos, item): # O(k)
    node = Node(item)
    current = self.head
    previous = None
    for _ in range(pos):
        previous = current
        current = current.getNext()

    node.setNext(current)
    if previous is None:
        self.head = node
    else:
        previous.setNext(node)

def pop(self, pos=None):  # O(n)
    current = self.head
    previous = None

    if pos is None:
        while current.getNext():
            previous = current
            current = current.getNext()
    else:
        for _ in range(pos):
            previous = current
            current = current.getNext()

    if previous is None:
        self.head = current.getNext()
    else:
        previous.setNext(current.getNext())
    return current.getData()

u"""
有序鏈表
"""
class OrderedList(UnorderedList):
def add(self, item): # O(n)
previous = None
current = self.head
while current:
if current.getData() > item:
break
previous = current
current = current.getNext()
node = Node(item)
node.setNext(current)
if previous is None:
self.head = node
else:
previous.setNext(node)

def search(self, item):  # O(n)
    current = self.head
    while current:
        if current.getData() == item:
            return True
        elif current.getData() > item:
            break
        current = current.getNext()
    return False

u"""
遞歸

1. 遞歸算法必須具有基本情況
2. 遞歸算法必須改變狀態(tài)并靠近其基本情況
3. 遞歸算法必須遞歸方式調(diào)用自身
   """

u"""
遞歸算法 整數(shù)轉(zhuǎn)字符串
"""
def toStr(n, base):
digits = '0123456789ABCDEF'
if n < base:
return digits[n]
else:
return toStr(n // base, base) + digits[n % base]

u"""
河內(nèi)塔

1. 把上層的所有盤(pán)子移動(dòng)到中間
2. 把最后一個(gè)移動(dòng)到目標(biāo)
3. 把中間的所有盤(pán)子移動(dòng)到目標(biāo)
   """
   def moveTower(height, fromPole, toPole, withPole):
   if height >= 1:
   moveTower(height-1, fromPole, withPole, toPole)
   moveDisk(fromPole, toPole)
   moveTower(height-1, withPole, toPole, fromPole)

def moveDisk(fp,tp):
print 'move disk from ' + fp + ' to ' + tp

u"""
探索迷宮

1. 向北邊走一格, 遞歸
2. 如果向北不能走, 向南走一格, 遞歸
3. 如果向南不能走, 向東走一格, 遞歸
4. 如果向東不能走, 向西走一格, 遞歸

先走一格, 然后繼續(xù)向不同方向遞歸, 直到找到出口

def searchFrom(maze, startRow, startColumn):
maze.updatePosition(startRow, startColumn)
# Check for base cases:
# 1. We have run into an obstacle, return false
if maze[startRow][startColumn] == OBSTACLE : # 碰到墻壁
return False
# 2. We have found a square that has already been explored
if maze[startRow][startColumn] == TRIED: # 已經(jīng)來(lái)過(guò)
return False
# 3. Success, an outside edge not occupied by an obstacle
if maze.isExit(startRow,startColumn):
maze.updatePosition(startRow, startColumn, PART_OF_PATH)
return True # 判斷為出口
maze.updatePosition(startRow, startColumn, TRIED) # 設(shè)置來(lái)過(guò)

# Otherwise, use logical short circuiting to try each
# direction in turn (if needed)
found = searchFrom(maze, startRow-1, startColumn) or \
        searchFrom(maze, startRow+1, startColumn) or \
        searchFrom(maze, startRow, startColumn-1) or \
        searchFrom(maze, startRow, startColumn+1)
if found:
    maze.updatePosition(startRow, startColumn, PART_OF_PATH)
else:
    maze.updatePosition(startRow, startColumn, DEAD_END)
return found

"""

u"""
動(dòng)態(tài)規(guī)劃

硬幣找零問(wèn)題 找到最小可能的硬幣數(shù)
"""
def recMC(coinValueList, change):
minCoins = change
if change in coinValueList:
return 1
else:
for i in [c for c in coinValueList if c <= change]:
num = 1 + recMC(coinValueList, change-i)
if num < minCoins:
minCoins = num
return minCoins

u"""
以上算法由于計(jì)算了大量的重復(fù)數(shù)據(jù), 所以低效, 可以對(duì)已有的數(shù)據(jù)緩存, 避免重復(fù)計(jì)算
從頂至下
"""
def recDC(coinValueList, change, knownResults):
minCoins = change
if change in coinValueList:
knownResults[change] = 1
return 1
elif knownResults[change] > 0:
return knownResults[change]
else:
for i in [c for c in coinValueList if c <= change]:
num = 1 + recDC(coinValueList, change-i, knownResults)
if num < minCoins:
minCoins = num
knownResults[change] = minCoins
return minCoins

u"""
動(dòng)態(tài)規(guī)劃

1. 最小最優(yōu)解
2. 從小到大, 使用已有的計(jì)算結(jié)果， 從底至上
   """
   def dpMakeChange(coinValueList, change, minCoins, coinsUsed):
   for cents in range(change+1):
   coinCount = cents
   newCoin = 1
   for i in [c for c in coinValueList if c <= cents]:
   if minCoins[cents-i] + 1 < coinCount:
   coinCount = minCoins[cents-i] + 1
   newCoin = i
   minCoins[cents] = coinCount
   coinsUsed[cents] = newCoin
   return minCoins[change]

打印最佳組合的各個(gè)值

def printCoins(coinsUsed, change):
l = []
while change:
l.append(coinsUsed[change])
change -= coinsUsed[change]
print l

u"""
背包問(wèn)題

n=5是物品的數(shù)量惭蟋，c=10是書(shū)包能承受的重量苗桂，w=[2,2,6,5,4]是每個(gè)物品的重量，v=[6,3,5,4,6]是每個(gè)物品的價(jià)值
"""
def bag(n, c, w, v):
res=[[-1 for j in range(c + 1)] for i in range(n + 1)]
for j in range(c + 1):
res[0][j]=0 # 把第一列初始化 0
for i in range(1, n + 1): # 行 1~5
for j in range(1, c + 1): # 列 1~10
res[i][j] = res[i - 1][j] # 先把上一行的值賦值個(gè)當(dāng)前
if j >= w[i-1] and res[i][j] < res[i-1][j - w[i-1]] + v[i - 1]:
# 如果重量大于物品的行重量且當(dāng)前價(jià)值小于物品價(jià)值+前一個(gè)物品重量,則重算最大重量
res[i][j] = res[i-1][j-w[i-1]] + v[i-1]
return res

def show(n, c, w, res):
print '最大價(jià)值', res[n][c]
x = [False for _ in w]
j = c
for i in range(1, n+1):
if res[i][j] > res[i-1][j]:
x[i-1] = True
j -= w[i-1]
for i, j in enumerate(x):
if j:
print '第{}個(gè)'.format(i+1)

u"""
二分查找
"""
def binarySearch(alist, item):
first = 0
last = len(alist) - 1

found = False
while first <= last and not found:
    mid = first + (last - first) // 2
    if alist[mid] == item:
        found = True
    elif alist[mid] > item:
        last = mid - 1
    else:
        first = mid + 1
return found

遞歸版

def binarySearch2(alist, item): # O( log^n )
if len(alist) == 0:
return False
else:
mid = len(alist) // 2
if alist[mid] == item:
return True
elif alist[mid] > item:
return binarySearch2(alist[:mid], item)
else:
return binarySearch2(alist[mid+1:], item)

u"""
哈希表

1. 大小為m的哈希表告组，有從0~m-1為編號(hào)的槽 可以用數(shù)組表示

2. 項(xiàng)與編號(hào)的映射方法叫 hash 函數(shù)煤伟，簡(jiǎn)單的示例可以用取余
   ＊ 如果多個(gè)項(xiàng)經(jīng)過(guò) hash 函數(shù)得到的編號(hào)相同，則稱(chēng)為碰撞
   ＊ 分組求和 把項(xiàng)的多個(gè)數(shù)字分組求和再取m的余
   ＊ 平方取中 算項(xiàng)的平方值并去中間的某幾位 再取m的余

3. 項(xiàng)數(shù)/表大小m 的值 稱(chēng)為 負(fù)載因子

4. 沖突解決 重新散列
   ＊ 開(kāi)放尋址 如果槽已被占用木缝，則順序往槽的下一個(gè)槽查找持偏，直到找到空槽(線(xiàn)性探測(cè))
   ＊ 使用鏈?zhǔn)酱鎯?chǔ)，在同一個(gè)編號(hào)上存儲(chǔ)多個(gè)項(xiàng)
   """
   class HashTable(object):
   def init(self):
   self.size = 11 # 要為質(zhì)數(shù)
   self.slots = [None]self.size
   self.data = [None]self.size

   def _hash(self, key):
   return key % self.size

   def _rehash(self, oldhash):
   return (oldhash+1)%self.size

   def put(self, key, data):
   hashvalue = self._hash(key)
   if self.slots[hashvalue] is None: # 新增
   self.slots[hashvalue] = key
   self.data[hashvalue] = data
   elif self.slots[hashvalue] == key: # 修改
   self.data[hashvalue] = data
   else:
   nextslot = self._rehash(hashvalue)
   while self.slots[nextslot] != None and self.slots[nextslot] != key:
   nextslot = self._rehash(hashvalue)
   if self.slots[nextslot] is None:
   self.slots[nextslot] = key
   self.data[nextslot] = data

   def get(self, key):
   position = self._get_position(key)
   return self.data[position] if position is not None else None

   def _get_position(self, key): # 理想的情況下 O(1) 最差 O(n)
   startslot = self._hash(key)
   position = startslot
   while self.slots[position] != None:
   if self.slots[position] == key:
   return position
   else:
   position = self._rehash(position)
   if position == startslot:
   return None
   return None

   def getitem(self, key):
   return self.get(key)

   def setitem(self, key, data):
   self.put(key, data)

   def len(self):
   count = 0
   for i in self.slots:
   if i is not None:
   count += 1
   return count

   def delitem(self, key):
   position = self._get_position(key)
   if position is not None:
   self.slots[position] = None
   self.data[position] = None

   def contains(self, key):
   position = self._get_position(key)
   return False if position is None else True

u"""
冒泡排序
"""
def bubbleSort(alist): # O(n^2)
for passnum in range(len(alist)-1, 0, -1):
for i in range(passnum):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]

u"""
短冒泡排序

前一次遍歷如果沒(méi)有發(fā)生交換氨肌，證明整個(gè)序列以排序
"""
def shortBubbleSort(alist):
passnum = len(alist) - 1
exchange = True
while passnum > 0 and exchange:
exchange = False
for i in range(passnum):
if alist[i] > alist[i+1]:
exchange = True
alist[i], alist[i+1] = alist[i+1], alist[i]
passnum -= 1

u"""
選擇排序

同冒泡排序鸿秆，只是減少的交換次數(shù)
"""
def selectionSort(alist):
for passnum in range(len(alist)-1, 0, -1):
maxPositon = 0
for i in range(1, passnum+1):
if alist[i] > alist[maxPositon]:
maxPositon = i
alist[passnum], alist[maxPositon] = alist[maxPositon], alist[passnum]

u"""
插入排序 O(n^2)

維持最小的已排序序列，迭代未排序項(xiàng)怎囚，插入到合適的位置
"""
def insertionSort(alist):
for i in range(1, len(alist)):
current = alist[i]
position = i

    while position > 0 and alist[position-1] > current:
        alist[position] = alist[position-1]
        position -= 1

    alist[position] = current

u"""
shell 排序

通過(guò)gap間隔來(lái)劃分子序列卿叽，先對(duì)所有的子序列進(jìn)行插入排序，然后再對(duì)整個(gè)序列插入排序
O(n^3/2) 稍稍好于插入排序
"""
def shellSort(alist):
count = len(alist) // 2 # 選擇gap
while count > 0:
for i in range(count):
gapInsertionSort(alist, i, count)

    count = count // 2

def gapInsertionSort(alist, start, gap):
for i in range(start+gap, len(alist), gap):
current = alist[i]
position = i

    while position > start and alist[position-gap] > current:
        alist[position] = alist[position-gap]
        position -= gap

    alist[position] = current

u"""
歸并排序

遞歸算法恳守，分治考婴，把序列切割成最小的部分并排序，然后逐步合并已排序的結(jié)果 O(nlog^n)
"""
def mergeSort(alist):
if len(alist) > 1:
mid = len(alist)//2 # 二分 log^n
left = alist[:mid]
right = alist[mid:]

    mergeSort(left) # 遞歸排序催烘，最小部分為 長(zhǎng)度為1的列表
    mergeSort(right)

    # 合并已排序的片段 最大花費(fèi)n次
    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            alist[k] = left[i]
            i += 1
        else:
            alist[k] = right[j]
            j += 1
        k += 1

    while i < len(left):
        alist[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        alist[k] = right[j]
        j += 1
        k += 1

u"""
快速排序 O(nlogn)
"""
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist, first, last):
if first < last:
i, j = first, last
current = alist[first]
while i < j:
while i < j and alist[j] >= current:
j -= 1
alist[i] = alist[j]

        while i < j and alist[i] <= current:
            i += 1
        alist[j] = alist[i]

    alist[i] = current

    quickSortHelper(alist,first,i-1)
    quickSortHelper(alist,i+1,last)

u"""
樹(shù)

節(jié)點(diǎn) 樹(shù)的基礎(chǔ)部分 可以有附加屬性,稱(chēng)為有效載荷 key
邊 表示節(jié)點(diǎn)之間的聯(lián)系, 除了 根節(jié)點(diǎn) 其它節(jié)點(diǎn)都有從父節(jié)點(diǎn)來(lái)的邊(傳入邊)
根 沒(méi)有傳入邊的節(jié)點(diǎn)
路徑 由邊連接的節(jié)點(diǎn)的有序序列
子節(jié)點(diǎn) 傳入邊為相同父節(jié)點(diǎn)
父節(jié)點(diǎn)
兄弟
子樹(shù) 由父節(jié)點(diǎn) 與 子孫節(jié)點(diǎn)組成的一組節(jié)點(diǎn)與邊
葉節(jié)點(diǎn) 沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)
層數(shù) 由根到節(jié)點(diǎn)之間邊的條數(shù)
高度 最大的葉子節(jié)點(diǎn)層數(shù)

定義 樹(shù)由一組節(jié)點(diǎn)和連接節(jié)點(diǎn)的邊組成

• 樹(shù)的一個(gè)節(jié)點(diǎn)指定為根節(jié)點(diǎn)
• 除了根,沒(méi)有節(jié)點(diǎn)n通過(guò)邊與p相連,n是p的子節(jié)點(diǎn)
• 從根遍歷到某個(gè)節(jié)點(diǎn)的路徑唯一

定義 樹(shù)是由根與一系列子樹(shù)組成,子數(shù)的根與根相連,遞歸定義
"""

u"""
列表表示 二叉樹(shù)
"""
def binaryTree(r):
return [r, [], []]

def insertLeft(root,newBranch):
node = root.pop(1)
if node:
root.insert(1, [newBranch, node, []])
else:
root.insert(1, [newBranch, [], []])
return root

def insertRight(root,newBranch):
node = root.pop(2)
if node:
root.insert(2, [newBranch, [], node])
else:
root.insert(2, [newBranch, [], []])
return root

def getRootVal(root):
return root[0]

def setRootVal(root,newVal):
root[0] = newVal

def getLeftChild(root):
return root[1]

def getRightChild(root):
return root[2]

u"""
節(jié)點(diǎn)表示
"""
class BinaryTree(object):
def init(self, val):
self.key = val
self.left = None
self.right = None

def insertLeft(self, val):
    node = BinaryTree(val)
    if self.left is None:
        self.left = node
    else:
        node.left = self.left
        self.left = node

def insertRight(self, val):
    node = BinaryTree(val)
    if self.right is None:
        self.right = node
    else:
        node.right = self.right
        self.right = node

def getRootVal(self):
    return self.key

def setRootVal(self, val):
    self.key = val

def getLeftChild(self):
    return self.left

def getRightChild(self):
    return self.right

def preorder(self):
    print self.key
    if self.left:
        self.left.preorder()
    if self.right:
        self.right.preorder()

u"""
使用樹(shù)構(gòu)建數(shù)值運(yùn)算
( 1 + ( 4 * 3 ) )
"""
def buildParseTree(fpexp):
fplist = fpexp.split()
pstack = Stack()
etree = BinaryTree('')
pstack.push(etree)
current = etree
for i in fplist:
if i == '(':
current.insertLeft('')
pstack.push(current)
current = current.getLeftChild()
elif i not in ['+', '-', '', '', ')']:
current.setRootVal(int(i))
current = pstack.pop()
elif i in ['+', '-', '', '']:
current.setRootVal(i)
current.insertRight('')
pstack.push(current)
current = current.getRightChild()
elif i == ')':
current = pstack.pop()
print current.getRootVal()
return etree

import operator

u"""
遞歸算式樹(shù)求值
"""
def evaluate(parseTree):
opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}

left = parseTree.getLeftChild()
right = parseTree.getRightChild()

if left and right:
    fn = opers[parseTree.getRootVal()]
    return fn(evaluate(left), evaluate(right))
else:
    return parseTree.getRootVal()

u"""
樹(shù)的遍歷

前序 返問(wèn)根,遞歸前序遍歷左子樹(shù),遞歸前序遍歷右子樹(shù)
中序 遞歸中序遍歷左子樹(shù),返問(wèn)根,遞歸中序遍歷右子樹(shù)
后序 遞歸后序遍歷左子樹(shù),遞歸后序遍歷右子樹(shù),返問(wèn)根
"""
def preorder(tree): # 前序
if tree:
print tree.getRootVal()
preorder(tree.getLeftChild())
preorder(tree.getRightChild())

def postorder(tree): # 后序
if tree:
postorder(tree.getLeftChild())
postorder(tree.getRightChild())
print tree.getRootVal()

u"""
遍歷求值
"""
def postordereval(tree):
opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}
res1 = None
res2 = None
if tree:
res1 = postordereval(tree.getLeftChild())
res2 = postordereval(tree.getRightChild())
if res1 and res2:
return opers[tree.getRootVal()](res1, res2)
else:
return tree.getRootVal()

def inorder(tree): # 中序
if tree:
inorder(tree.getLeftChild())
print tree.getRootVal()
inorder(tree.getRightChild())

u"""
打印原始分析樹(shù)
"""
def printexp(tree):
s = ''
if tree:
s = '(' + printexp(tree.getLeftChild())
s = s + tree.getRootVal()
s = printexp(tree.getRightChild()) + ')'
return s

u"""
二叉堆 最小堆

子節(jié)點(diǎn)的一定小于父節(jié)點(diǎn)沥阱，根節(jié)點(diǎn)最小
每層的最大節(jié)點(diǎn)個(gè)數(shù)為2^h，所以子節(jié)點(diǎn)一定是父節(jié)點(diǎn)的2n 2n＋1
"""
class BinHeap(object):
def init(self):
self.heapList = [0]
self.currentSize = 0

def insert(self, i): # O(log2^n)
    self.heapList.append(i)
    self.currentSize += 1

    i = self.currentSize
    j = i // 2 # 找到父節(jié)點(diǎn)的位置
    while j > 0: # 對(duì)比交換
        if self.heapList[i] < self.heapList[j]:
            self.heapList[i], self.heapList[j] = self.heapList[j], self.heapList[i]
        i = j
        j = j // 2

def delMin(self): # O(log2^n)
    minVal = self.heapList[1]
    self.heapList[1] = self.heapList[-1]
    self.currentSize -= 1
    self.heapList.pop() # 刪除最小,把最大的移動(dòng)到根
    self._percDown(1) # 遍歷比較伊群，把合適的移動(dòng)到根
    return minVal

def _minChild(self, i):
    if (i * 2) + 1 > self.currentSize:
        return i * 2
    elif self.heapList[i*2] > self.heapList[i*2+1]:
        return i * 2 + 1
    else:
        return i * 2

def _percDown(self, i):
    while (i * 2) <= self.currentSize:
        mc = self._minChild(i)
        if self.heapList[i] > self.heapList[mc]:
            self.heapList[i], self.heapList[mc] = self.heapList[mc], self.heapList[i]
        i = mc

def buildHeap(self, alist): # O(n)
    self.currentSize = len(alist)
    self.heapList = [0] + alist[:]
    i = self.currentSize // 2
    while i > 0:
        self._percDown(i)
        i -= 1

def isEmpty(self):
    return True if self.currentSize == 0 else False

def size(self):
    return self.currentSize

u"""
最大堆
"""
class MaxBinHeap(object):
def init(self):
self.heapList = [0]
self.currentSize = 0

def insert(self, i):
    self.heapList.append(i)
    self.currentSize += 1

    i = self.currentSize
    j = i // 2
    while j > 0:
        if self.heapList[i] > self.heapList[j]:
            self.heapList[i], self.heapList[j] = self.heapList[j], self.heapList[i]
        i = j
        j = j // 2

def delMax(self):
    maxVal = self.heapList[1]
    self.heapList[1] = self.heapList[-1]
    self.currentSize -= 1
    self.heapList.pop()
    self._percUp(1)
    return maxVal

def _maxChild(self, i):
    if (i * 2) + 1 > self.currentSize:
        return i * 2
    elif self.heapList[i*2] < self.heapList[i*2+1]:
        return i * 2 + 1
    else:
        return i * 2

def _percUp(self, i):
    while (i * 2) <= self.currentSize:
        mc = self._maxChild(i)
        if self.heapList[i] < self.heapList[mc]:
            self.heapList[i], self.heapList[mc] = self.heapList[mc], self.heapList[i]
        i = mc

def buildHeap(self, alist):
    self.currentSize = len(alist)
    self.heapList = [0] + alist[:]
    i = self.currentSize // 2
    while i > 0:
        self._percUp(i)
        i -= 1

def isEmpty(self):
    return True if self.currentSize == 0 else False

def size(self):
    return self.currentSize

u"""
堆排序

構(gòu)建最大堆
把根交換到最后
遞歸n－1構(gòu)建最大堆考杉，交換 O(nlogn)
"""
def heap_sort(lst):
def sift_down(start, end):
root = start
while 1:
child = 2 * root + 1
if child > end:
break
if child + 1 < end and lst[child] < lst[child+1]:
child = child + 1
if lst[root] < lst[child]:
lst[root], lst[child] = lst[child], lst[root]
root = child
else:
break
i = len(lst) // 2 # 構(gòu)建最大堆
while i >= 0:
sift_down(i, len(lst) - 1)
i -= 1

for end in range(len(lst) - 1, 0, -1):
    lst[0], lst[end] = lst[end], lst[0] # 交換，重復(fù)構(gòu)建
    sift_down(0, end-1)

u"""
二叉搜索樹(shù)

節(jié)點(diǎn)的左子節(jié)點(diǎn)必須小于節(jié)點(diǎn)的key
節(jié)點(diǎn)的右子節(jié)點(diǎn)必須大于節(jié)點(diǎn)的key

get put delete 都是遍歷高度 O(log2^n)
如果輸入是有序的,那么就是最壞的結(jié)果O(n), 因?yàn)橹粫?huì)遍歷左邊或者右邊
"""
class BinarySearchTree(object):
def init(self):
self.root = None
self.size = 0

def length(self):
    return self.size

def __len__(self):
    return self.size

def __iter__(self):
    return self.root.__iter__()

def put(self, key, val): # 復(fù)雜度在于樹(shù)的高度 O(log2^n)
    if self.root is None:
        self.root = TreeNode(key, val)
    else:
        self._put(key, val, self.root)
    self.size += 1

def _put(self, key, val, current):
    if key > current.key:
        if current.hasRightChild():
            self._put(key, val, current.right)
        else:
            current.right = TreeNode(key, val, parent=current)
    elif key < current.key:
        if current.hasLeftChild():
            self._put(key, val, current.left)
        else:
            current.left = TreeNode(key, val, parent=current)
    else:
        current.playload = val # key 相同時(shí) 直接替換值

def __setitem__(self, k, v):
    self.put(k, v)

def get(self, key): # O(log2^n)
    if self.root:
        node = self._get(key, self.root)
        if node:
            return node.playload
    return None

def _get(self, key, current):
    if not current:
        return None
    elif key > current.key:
        return self._get(key, current.right)
    elif key < current.key:
        return self._get(key, current.left)
    else:
        return current

def __getitem__(self, k):
    return self.get(k)

def __contains__(self, k):
    return bool(self._get(k, self.root))

def __delitem__(self, k):
    self.delete(k)

def delete(self, key): # 雖然很復(fù)雜, 但是實(shí)際上向下遍歷找到合適的節(jié)點(diǎn), 所有最大還是高度 O(log2^n)
    if self.size > 1:
        node = self._get(key, self.root)
        if node:
            self.removeNode(node)
            self.size -= 1
        else:
            raise KeyError(key)
    elif self.size == 1 and self.root.key == key:
        self.root = None
        self.size -= 1
    else:
        raise KeyError(key)

def removeNode(self, current):
    if current.isLeaf(): # 如果是葉子節(jié)點(diǎn),直接刪除
        if current.isLeftChild():
            current.parent.left = None
        else:
            current.parent.right = None
    elif current.hasBothChildren(): # 有2個(gè)子節(jié)點(diǎn)
        succ = current.findSuccessor()
        succ.spliceOut()
        current.key = succ.key
        current.playload = succ.key

    else: # 有1個(gè)子節(jié)點(diǎn)
        if current.hasLeftChild(): # 有左節(jié)點(diǎn)
            if current.isLeftChild():
                current.parent.left = current.left
                current.left.parent = current.parent
            elif current.isRightChild():
                current.parent.right = current.left
                current.left.parent = current.parent
            else: # 根節(jié)點(diǎn),直接使用子節(jié)點(diǎn)的數(shù)據(jù)替換自己
                current.replaceNodeData(current.left.key, current.left.playload,
                    current.left.left, current.left.right)
        else:
            if current.isLeftChild():
                current.parent.left = current.right
                current.right.parent = current.parent
            elif current.isRightChild():
                current.parent.right = current.right
                current.right.parent = current.parent
            else: # 根節(jié)點(diǎn)
                current.replaceNodeData(current.right.key, current.right.playload,
                    current.right.left, current.right.right)

class TreeNode(object):
def init(self, key, val, left=None, right=None, parent=None):
self.key = key
self.playload = val
self.left = left
self.right = right
self.parent = parent
self.balanceFactor = 0

def hasLeftChild(self):
    return self.left

def hasRightChild(self):
    return self.right

def isLeftChild(self):
    return self.parent and self.parent.hasLeftChild() == self

def isRightChild(self):
    return self.parent and self.parent.hasRightChild() == self

def isRoot(self):
    return not self.parent

def isLeaf(self):
    return not (self.left and self.right)

def hasAnyChildren(self):
    return self.left or self.right

def hasBothChildren(self):
    return self.left and self.right

def replaceNodeData(self, key, value, lc, rc):
    self.key = key
    self.playload = value
    self.left = lc
    self.right = rc
    if self.hasLeftChild():
        self.left.parent = self
    if self.hasRightChild():
        self.right.parent = self

def findSuccessor(self):
    succ = None
    if self.hasRightChild():
        return self.right.findMin()
    else:
        if self.parent:
            if self.isLeftChild():
                succ = self.parent
            else: # 如果沒(méi)有右節(jié)點(diǎn), 且自己是右節(jié)點(diǎn), 父節(jié)點(diǎn)小于自己, 遍歷向上找
                self.parent.right = None # 可以肯定的是節(jié)點(diǎn) 右邊節(jié)點(diǎn)一定會(huì)大于節(jié)點(diǎn)本身
                succ = self.parent.findSuccessor()
                self.parent.right = self
    return succ

def findMin(self):
    current = self
    while current.hasLeftChild():
        current = current.left
    return current

def spliceOut(self):
    if self.isLeaf():
        if self.isLeftChild():
            self.parent.left = None
        else:
            self.parent.right = None
    elif self.hasLeftChild():
        if self.isLeftChild():
            self.parent.left = self.left
        else:
            self.parent.right = self.left
        self.left.parent = self.parent
    else:
        if self.isLeftChild():
            self.parent.left = self.right
        else:
            self.parent.right = self.right
        self.right.parent = self.parent

def __iter__(self):
    if self:
        if self.hasLeftChild():
            for ele in self.left:
                yield ele
        yield self.key
        if self.hasRightChild():
            for ele in self.right:
                yield ele

u"""
平衡二叉樹(shù)
AVL樹(shù) 自動(dòng)保持平衡的樹(shù)

平衡 根的左子樹(shù)與右子樹(shù)的高度差不超過(guò)1
"""
class AvlTree(BinarySearchTree):
def _put(self, key, val, current):
if key > current.key:
if current.hasRightChild():
self._put(key, val, current.right)
else:
current.right = TreeNode(key, val, parent=current)
self.updateBalance(current.right)
elif key < current.key:
if current.hasLeftChild():
self._put(key, val, current.left)
else:
current.left = TreeNode(key, val, parent=current)
self.updateBalance(current.left)
else:
current.playload = val

def updateBalance(self, node):
    u"""
    1. 遞歸調(diào)用到樹(shù)的根舰始，直到找到平衡因子大于1的節(jié)點(diǎn)
    2. 父節(jié)點(diǎn)的平衡因子已調(diào)整為零崇棠。你應(yīng)該說(shuō)服自己，一旦一個(gè)子樹(shù)的平衡因子為零丸卷，那么它的祖先節(jié)點(diǎn)的平衡不會(huì)改變枕稀。
    """
    if node.balanceFactor > 1 or node.balanceFactor < -1:
        self.rebalance(node) # 通過(guò)旋轉(zhuǎn)可以保證節(jié)點(diǎn)平衡因子為0
        return
    if node.parent != None:
        if node.isLeftChild():
            node.parent.balanceFactor += 1
        elif node.isRightChild():
            node.parent.balanceFactor -= 1
        if node.parent.balanceFactor != 0:
            self.updateBalance(node.parent)

def rebalance(self, node):
    if node.balanceFactor < 0:
        if node.right.balanceFactor > 0:
            self.rotateRight(node.right)
        self.rotateLeft(node)
    elif node.balanceFactor > 0:
        if node.left.balanceFactor < 0:
            self.rotateLeft(node.left)
        self.rotateRight(node)

def rotateLeft(self, rotRoot): # 左旋轉(zhuǎn)
    u"""
    1. 提升右孩子（B）成為子樹(shù)的根。
    2. 將舊根（A）移動(dòng)為新根的左子節(jié)點(diǎn)谜嫉。
    3. 如果新根（B）已經(jīng)有一個(gè)左孩子萎坷，那么使它成為新左孩子（A）的右孩子。
       注意：由于新根（B）是A的右孩子沐兰，A 的右孩子在這一點(diǎn)上保證為空哆档。
       這允許我們添加一個(gè)新的節(jié)點(diǎn)作為右孩子，不需進(jìn)一步的考慮僧鲁。
    """
    newRoot = rotRoot.right # 右節(jié)點(diǎn)為新根
    rotRoot.right = newRoot.left # 新根的左節(jié)點(diǎn)稱(chēng)為舊根的右節(jié)點(diǎn)
    if newRoot.hasLeftChild():
        newRoot.left.parent = rotRoot
    newRoot.parent = rotRoot.parent
    if rotRoot.isRoot():
        self.root = newRoot
    else:
        if rotRoot.isLeftChild():
            rotRoot.parent.left = newRoot
        elif rotRoot.isRightChild():
            rotRoot.parent.right = newRoot
    newRoot.left = rotRoot
    rotRoot.parent = newRoot
    rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)
    newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)

def rotateRight(self, rotRoot): # 右旋轉(zhuǎn)
    newRoot = rotRoot.left
    rotRoot.left = newRoot.right
    if newRoot.hasRightChild():
        newRoot.right.parent = rotRoot
    newRoot.parent = rotRoot.parent
    if rotRoot.isRoot():
        self.root = newRoot
    else:
        if rotRoot.isLeftChild():
            rotRoot.parent.left = newRoot
        elif rotRoot.isRightChild():
            rotRoot.parent.right = newRoot
    newRoot.right = rotRoot
    rotRoot.parent = newRoot
    rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)
    newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)

u"""
圖

頂點(diǎn) 同樹(shù)中的節(jié)點(diǎn)
邊 連接2個(gè)頂點(diǎn),可以是多個(gè)方向的,如果圖中邊都只有一個(gè)方法,則稱(chēng)為有向圖
權(quán)重 邊可以被加權(quán),表示頂點(diǎn)到頂點(diǎn)過(guò)去的成本
路徑 由邊連接的頂點(diǎn)的序列, 未加權(quán)的路徑長(zhǎng)度n-1, 加權(quán)的為路徑所有邊權(quán)重的和
循環(huán) 有向圖的循環(huán)是同一頂點(diǎn)為起點(diǎn)和終點(diǎn)的路徑, 沒(méi)有循環(huán)的圖稱(chēng)為非循環(huán)圖形, 沒(méi)有循環(huán)的有向圖稱(chēng)為無(wú)環(huán)圖 DAG

圖 是由頂點(diǎn)集合與邊集合組成的 G = (V, E) G 圖 V 頂點(diǎn)集合 E 邊的集合
"""

u"""
鄰接矩陣

行與列存儲(chǔ)了圖的頂點(diǎn),行與列的單元格存了邊的加權(quán)值,如果2個(gè)頂點(diǎn)間的單元格值,則2個(gè)頂點(diǎn)相鄰
由于存在很多的空單元格,大部分情況下矩陣是稀疏的,但是對(duì)于邊很多的情況下,領(lǐng)接矩陣很適合

領(lǐng)接表

適用于邊很稀疏的情況
對(duì)應(yīng)于列的頂點(diǎn)列表,對(duì)每個(gè)頂點(diǎn)維護(hù)一個(gè)邊的列表,保存了頂點(diǎn)與權(quán)重
空間更高效,并且保存了頂點(diǎn)直接連接的其它頂點(diǎn)
"""
import sys

class Vertex:
def init(self,num):
self.id = num
self.connectedTo = {}
self.color = 'white' # 是否已訪(fǎng)問(wèn) white 未訪(fǎng)問(wèn) gray 正在訪(fǎng)問(wèn) black 已訪(fǎng)問(wèn)
self.dist = sys.maxsize
self.pred = None # 上級(jí)頂點(diǎn)
self.disc = 0 # 距離開(kāi)始頂點(diǎn)的距離或者頂點(diǎn)標(biāo)識(shí)為 gray 的時(shí)間
self.fin = 0 # 頂點(diǎn)標(biāo)識(shí)為 black 的時(shí)間

def addNeighbor(self,nbr,weight=0):
    self.connectedTo[nbr] = weight

def setColor(self,color):
    self.color = color

def setDistance(self,d):
    self.dist = d

def setPred(self,p):
    self.pred = p

def setDiscovery(self,dtime):
    self.disc = dtime

def setFinish(self,ftime):
    self.fin = ftime

def getFinish(self):
    return self.fin

def getDiscovery(self):
    return self.disc

def getPred(self):
    return self.pred

def getDistance(self):
    return self.dist

def getColor(self):
    return self.color

def getConnections(self):
    return self.connectedTo.keys()

def getWeight(self,nbr):
    return self.connectedTo[nbr]

def getId(self):
    return self.id

class Graph(object):
def init(self):
self.vertList = {}
self.numVertices = 0

def addVertex(self, key):
    ver = Vertex(key)
    self.numVertices += 1
    self.vertList[key] = ver
    return ver

def getVertex(self, n):
    if n in self.vertList:
        return self.vertList[n]
    return None

def __contains__(self, n):
    return n in self.vertList

def addEdge(self, f, t, cost=0):
    if f not in self.vertList:
        self.addVertex(f)
    if t not in self.vertList:
        self.addVertex(t)
    self.vertList[f].addNeighbor(self.vertList[t], cost)

def getVertices(self):
    return self.vertList.keys()

def __iter__(self):
    return iter(self.vertList.values())

u"""
構(gòu)建字梯圖
"""
def buildGraph(words): # O(n^2)
d = {}
g = Graph()
for word in words:
for i in range(len(word)):
bucket = word[:i] + '_' + word[i+1:]
if bucket in d:
d[bucket].append(word)
else:
d[bucket] = [word]
for bucket in d.keys():
for word1 in d[bucket]:
for word2 in d[bucket]:
if word1 != word2:
g.addEdge(word1, word2)
return g

u"""
廣度優(yōu)先 BFS
"""
def bfs(start): # O(V) 每個(gè)頂點(diǎn)只會(huì)訪(fǎng)問(wèn)一次
start.setDistance(0)
start.setPred(None)
vertQueue = Queue()
vertQueue.enqueue(start)
while (vertQueue.size() > 0):
currentVert = vertQueue.dequeue()
for nbr in currentVert.getConnections():
if (nbr.getColor() == 'white'):
nbr.setColor('gray')
nbr.setDistance(currentVert.getDistance() + 1)
nbr.setPred(currentVert)
vertQueue.enqueue(nbr)
currentVert.setColor('black')

def traverse(y): # 反向追蹤找到路徑
x = y
while x.getPred():
print x.getId()
x = x.getPred()

u"""
騎士之旅

棋盤(pán)上的每個(gè)單元格都需要訪(fǎng)問(wèn)到
"""
def knightGraph(bdSize):
graph = Graph()
for row in range(bdSize):
for col in range(bdSize):
nodeId = posToNodeId(row, col, bdSize)
newPositions = genLegalMoves(row, col, bdSize)
for e in newPositions:
nid = posToNodeId(e[0], e[1], bdSize)
graph.addEdge(nodeId, nid)
return graph

def posToNodeId(row, column, board_size):
return (row * board_size) + column

def genLegalMoves(x, y, bdSize):
newMoves = []
moveOffsets = [(-1,-2),(-1,2),(-2,-1),(-2,1),
( 1,-2),( 1,2),( 2,-1),( 2,1)]
for i in moveOffsets:
newX = x + i[0]
newY = y + i[1]
if legalCoord(newX, bdSize) and
legalCoord(newY, bdSize):

        newMoves.append((newX, newY))
return newMoves

def legalCoord(x, bdSize):
if x >= 0 and x < bdSize:
return True
return False

u"""
深度優(yōu)先 DFS
"""
def knightTour(n, path, u, limit):
u"""
n: 搜索樹(shù)中當(dāng)前深度
path: 搜索路徑節(jié)點(diǎn)列表
u: 希望找到的頂點(diǎn)
limit: 路徑中的節(jié)點(diǎn)數(shù)停忿，最大的深度
"""
u.setColor('gray')
path.append(u)
if n < limit:
# nbrList = list(u.getConnections())
nbrList = orderByAvail(u)
i = 0
done = False
while i < len(nbrList) and not done:
if nbrList[i].getColor() == 'white':
done = knightTour(n+1, path, nbrList[i], limit)
i = i + 1
if not done: # prepare to backtrack
path.pop()
u.setColor('white') # 回溯，遍歷下一個(gè)鄰居
else:
done = True
return done

u"""
啟發(fā)式

傾向與先遍歷到有較少的可選的節(jié)點(diǎn)寻歧，這樣騎士會(huì)先覆蓋棋盤(pán)周邊的方格径荔，然后向中間，
避免在中間路徑過(guò)多的選擇, 由中間向周邊發(fā)散會(huì)產(chǎn)生更多的短路徑
"""
def orderByAvail(n):
resList = []
for v in n.getConnections():
if v.getColor() == 'white':
c = 0
for w in v.getConnections():
if w.getColor() == 'white':
c = c + 1
resList.append((c,v))
resList.sort(key=lambda x: x[0])
return [y[1] for y in resList]

class DFSGraph(Graph):
def init(self):
super(DFSGraph, self).init()
self.time = 0

def dfs(self):
    for aVertex in self:
        aVertex.setColor('white')
        aVertex.setPred(-1)
    for aVertex in self:
        if aVertex.getColor() == 'white':
            self.dfsvisit(aVertex)

def dfsvisit(self, startVertex): # O(V + E) 覆蓋每個(gè)頂點(diǎn)，并且每個(gè)邊都會(huì)過(guò)一次
    u"""
    遍歷過(guò)后的所有其它節(jié)點(diǎn)都能找到到開(kāi)始節(jié)點(diǎn)的路徑，構(gòu)成深度優(yōu)先森林
    """
    startVertex.setColor('gray')
    self.time += 1
    startVertex.setDiscovery(self.time) # 開(kāi)始遍歷的時(shí)間
    for nextVertex in startVertex.getConnections():
        if nextVertex.getColor() == 'white':
            nextVertex.setPred(startVertex)
            self.dfsvisit(nextVertex)
    startVertex.setColor('black')
    self.time += 1
    startVertex.setFinish(self.time) # 遍歷完成的時(shí)間

u"""
拓?fù)渑判?/p>

有向無(wú)環(huán)圖

1. 對(duì)于某些圖 g 調(diào)用 dfs(g)。我們想要調(diào)用深度優(yōu)先搜索的主要原因是計(jì)算每個(gè)頂點(diǎn)的完成時(shí)間忽孽。
2. 以完成時(shí)間的遞減順序?qū)㈨旤c(diǎn)存儲(chǔ)在列表中。
3. 返回有序列表作為拓?fù)渑判虻慕Y(jié)果谢床。得到正確的完成步驟
   """

u"""
強(qiáng)聯(lián)通分量

C 是 G 的子集, 并且 C 的每個(gè)頂點(diǎn)都是互通的(強(qiáng)聯(lián)通)

1. 調(diào)用dfs計(jì)算G的每個(gè)頂點(diǎn)的完成時(shí)間
2. 計(jì)算G^T 復(fù)制G,并翻轉(zhuǎn)每個(gè)邊的方向
3. 為G^T調(diào)用dfs, 但在 DFS 的主循環(huán)中兄一，以完成時(shí)間的遞減順序探查每個(gè)頂點(diǎn)。
4. 在步驟 3 中計(jì)算的森林中的每個(gè)樹(shù)是強(qiáng)連通分量识腿。輸出森林中每個(gè)樹(shù)中每個(gè)頂點(diǎn)的頂點(diǎn)標(biāo)識(shí)組件出革。
   """
   def buildSCC():
   g = DFSGraph()
   g.addEdge('A', 'B')
   g.addEdge('B', 'C')
   g.addEdge('C', 'F')
   g.addEdge('F', 'H')
   g.addEdge('H', 'I')
   g.addEdge('I', 'F')
   g.addEdge('B', 'E')
   g.addEdge('E', 'D')
   g.addEdge('D', 'G')
   g.addEdge('G', 'E')
   g.addEdge('E', 'A')
   g.addEdge('D', 'B')
   g.dfs()
   return g

def buildGT(g):
newG = DFSGraph()
for vert in g: # 構(gòu)建G^T
for nbr in vert.connectedTo.keys():
newG.addEdge(nbr.getId(), vert.getId())
verts = sorted(newG.vertList.values(), key=lambda vert: g.getVertex(vert.getId()).getFinish(), reverse=True)
for aVertex in verts:
aVertex.setColor('white')
aVertex.setPred(-1)
for aVertex in verts:
if aVertex.getColor() == 'white':
newG.dfsvisit(aVertex) # 構(gòu)建的子樹(shù)即為強(qiáng)連通分量
return newG

u"""
最短路徑問(wèn)題

針對(duì)加權(quán)邊的圖
"""
class PriorityQueue(object):
u"""
優(yōu)先級(jí)隊(duì)列
"""
def init(self):
self.heapArray = [(0,0)]
self.currentSize = 0

def buildHeap(self,alist):
    self.currentSize = len(alist)
    self.heapArray = [(0,0)]
    for i in alist:
        self.heapArray.append(i)
    i = len(alist) // 2
    while (i > 0):
        self.percDown(i)
        i = i - 1

def percDown(self,i):
    while (i * 2) <= self.currentSize:
        mc = self.minChild(i)
        if self.heapArray[i][0] > self.heapArray[mc][0]:
            tmp = self.heapArray[i]
            self.heapArray[i] = self.heapArray[mc]
            self.heapArray[mc] = tmp
        i = mc

def minChild(self,i):
    if i*2 > self.currentSize:
        return -1
    else:
        if i*2 + 1 > self.currentSize:
            return i*2
        else:
            if self.heapArray[i*2][0] < self.heapArray[i*2+1][0]:
                return i*2
            else:
                return i*2+1

def percUp(self,i):
    while i // 2 > 0:
        if self.heapArray[i][0] < self.heapArray[i//2][0]:
           tmp = self.heapArray[i//2]
           self.heapArray[i//2] = self.heapArray[i]
           self.heapArray[i] = tmp
        i = i//2

def add(self,k):
    self.heapArray.append(k)
    self.currentSize = self.currentSize + 1
    self.percUp(self.currentSize)

def delMin(self):
    retval = self.heapArray[1][1]
    self.heapArray[1] = self.heapArray[self.currentSize]
    self.currentSize = self.currentSize - 1
    self.heapArray.pop()
    self.percDown(1)
    return retval

def isEmpty(self):
    if self.currentSize == 0:
        return True
    else:
        return False

def decreaseKey(self,val,amt):
    # this is a little wierd, but we need to find the heap thing to decrease by
    # looking at its value
    done = False
    i = 1
    myKey = 0
    while not done and i <= self.currentSize:
        if self.heapArray[i][1] == val:
            done = True
            myKey = i
        else:
            i = i + 1
    if myKey > 0:
        self.heapArray[myKey] = (amt,self.heapArray[myKey][1])
        self.percUp(myKey)

def __contains__(self,vtx):
    for pair in self.heapArray:
        if pair[1] == vtx:
            return True
    return False

u"""
dijkstra算法, 類(lèi)似于bfs, 只是使用優(yōu)先級(jí)隊(duì)列, 按權(quán)重最小排列
最終算出其它頂點(diǎn)與開(kāi)始頂點(diǎn)間最短距離
只有權(quán)重為正才能正常運(yùn)行,否則會(huì)死循環(huán)
"""
def dijkstra(aGraph, start): # O((V + E)log^V )
pq = PriorityQueue()
start.setDistance(0)
pq.buildHeap([(v.getDistance(), v) for v in aGraph]) # 所有的都放進(jìn)去了
while not pq.isEmpty():
currentVert = pq.delMin()
for nextVert in currentVert.getConnections():
newDist = currentVert.getDistance()
+ currentVert.getWeight(nextVert)
if newDist < nextVert.getDistance():
nextVert.setDistance(newDist)
nextVert.setPred(currentVert)
pq.decreaseKey(nextVert, newDist) # 移動(dòng)到隊(duì)列的前面

u"""
最小權(quán)重生成樹(shù)

Prim生成樹(shù)算法

使用最小權(quán)重的邊重寫(xiě)頂點(diǎn)的路徑, 貪婪算法
"""
def prim(G, start):
pq = PriorityQueue()
for v in G:
v.setDistance(sys.maxint)
v.setPred(None)
start.setDistance(0)
pq.buildHeap([(v.getDistance(), v) for v in G])
while not pq.isEmpty():
currentVert = pq.delMin()
for nextVert in currentVert.getConnections():
newCost = currentVert.getWeight(nextVert) + currentVert.getDistance()
if nextVert in pq and newCost < nextVert.getDistance():
nextVert.setPred(currentVert)
nextVert.setDistance(newCost)
pq.decreaseKey(nextVert, newCost

轉(zhuǎn)自：
https://zhu327.github.io/2017/03/14/%E7%94%A8python%E8%A7%A3%E5%86%B3%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E9%97%AE%E9%A2%98/