# heap的实现

```class maxheap(object):
def __init__(self):
self.__array = [0]
self.__count = 0
pass

def size(self):
return self.__count

def isEmpty(self):
return self.__count == 0```

#### insertHeap

```    def __shifUp(self, k):
while k > 1 and (self.__array[int(k/2)] < self.__array[k]):
swap(self.__array, int(k/2), k)
k = int(k/2)
pass```

```    def insert(self, number):
self.__array.append(number)
self.__count += 1
self.__shifUp(self.__count)
pass```

#### extractMax

```    def __shifDown(self, k):
while 2*k <= self.__count:
j = 2*k
if j + 1 <= self.__count and (self.__array[j + 1] > self.__array[j]):
j += 1
if self.__array[k] >= self.__array[j]:
break
swap(self.__array, k, j)
k = j
pass```

```    def extractMax(self):
maxNumber = self.__array[1]
self.__array[1] = self.__array[self.__count]
self.__count -= 1
self.__shifDown(1)
return maxNumber
pass```

```if __name__ == '__main__':
heap = maxheap()
for i in range(13):
heap.insert(np.random.randint(0, 200))
heap.showHeap()
for i in range(1):
print(heap.extractMax())
heap.showHeap()```

# tree

### 二叉搜索树

##### 二分查找

```def binarySearch(array, n, target):
'''
:param array:order array
:param n: the number of the array
:param target: number which we search for
:return: index of target
'''
l, r = 0, n-1
while l <= r:
mid = int((l + r)/2)
#mid = int((l + (r-l))/2)
if array[mid] == target:
return (mid + 1)
elif mid < target:
l = mid + 1
elif mid > target:
r = mid - 1
return -1```

`mid = int((l + (r-l))/2)`

method

search

insert

delete

array

order array

binary tree

##### 二分搜索树的实现

```class BST(object):
class _node(object):
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
def __init__(self):
self.root = None
self.count = 0

def size(self):
return self.count

def isempty(self):
return self.count == 0```

```    def insert(self, key, value):
self.root = self.__insert(self.root, key, value)

def __insert(self, node, key, value):
if node == None:
return self._node(key, value)
elif key == node.key:
node.value = value
elif key < node.key:
node.left = self.__insert(node.left, key, value)
else:
node.right = self.__insert(node.right, key, value)
return node```

```    def contain(self, key):
return self.__contain(self.root, key)

def __contain(self, node, key):
if node == None:
return False
elif node.key == key:
return True
elif key < node.key:
return self.__contain(node.left, key)
else:
return self.__contain(node.right, key)```

```    def search(self, key):
return self.__search(self.root, key)
pass

def __search(self, node, key):
if node == None:
return None
elif node.key == key:
return node.value
elif node.key < key:
return self.__search(node.right, key)
else:
return self.__search(node.left, key)
pass```

##### 二叉树的深度优先遍历

```    def preOrder(self):
self.__preOrder(self.root)
pass

def __preOrder(self, node):
if node != None:
print('key: ', node.key, ' value: ', node.value)
self.__preOrder(node.left)
self.__preOrder(node.right)

def inOrder(self):
self.__inOrder(self.root)
pass

def __inOrder(self, node):
if node != None:
self.__inOrder(node.left)
print('key: ', node.key, ' value: ', node.value)
self.__inOrder(node.right)
pass

def postOrder(self):
self.__postOrder(self.root)
pass

def __postOrder(self, node):
if node != None:
self.__postOrder(node.left)
self.__postOrder(node.right)
print('key: ', node.key, ' value: ', node.value)```

```    def destory(self):
self.__destory(self.root)
pass

def __destory(self, node):
if node != None:
self.__destory(node.left)
self.__destory(node.right)
del node```

##### 二叉树的广度优先遍历

。实现这个操作需要一个队列，遍历到28的时候，把它的左右子树塞进队列里面，接着把队首的元素输出，把输出元素的左右子树右赛进去，这样循环直到队列没有元素为止。 按照上面的做法实现一下即可：

```    def levelOrder(self):
self.__levelOrder(self.root)

def __levelOrder(self, node):
q = queue.Queue()
q.put(node)
while(q.empty() == False):
now = q.get()
print(now.key, end=' ')
if (now.left != None):
q.put(now.left)
if (now.right != None):
q.put(now.right)
pass```

##### 删除最大值和最小值

22有右孩子，那么直接把右孩子的那颗树拉上来就好了，因为任何一棵子树都是符合二叉树的性质，最大值也一样。这里是58，那么直接把子树拉上来就好了，最小值不可能有左子树，最大值不可能有右子树。 所以删除最大值和最小值就很简单了：

```    def removeMin(self):
if self.root != None:
self.root = self.__removeMin(self.root)
pass

def __removeMin(self, node):
if node.left == None:
right = node.right
del node
self.count -= 1
return right
node.left = self.__removeMin(node.left)
return node

def removeMax(self):
if self.root != None:
self.root = self.__removeMax(self.root)
pass

def __removeMax(self, node):
if node.right == None:
left = node.left
del node
self.count -= 1
return left
node.right = self.__removeMax(node.right)
return node```
##### 删除随便一个值

```    def remove(self, key):
self.__remove(self.root, key)
pass

def __remove(self, node, key):
if node == None:
return None
elif node.key > key:
node.left = self.__remove(node.left, key)
return node
elif node.key < key:
node.right = self.__remove(node.right, key)
else:
if node.left == None:
right = node.right
del node
self.count -= 1
return right

elif node.right == None:
left = node.left
del node
self.count -= 1
return left

else:
successor = copy.deepcopy(self.__minmum(node.right))
successor.right = self.__removeMin(node.right)
successor.left = node.left
return successor```

# 并查集

#### 并查集的构成和作用

0到4都是0，所以0到4着5个元素是互相连接的。5到9都是1那么就是互相联系的。

```class UnionFind(object):
id = None
count = 0```

```    def unionFind(self, n):
self.count = n
self.id = np.zeros(n)
for i in range(n):
self.id[i] = i```

```    def find(self, p):
if p >= 0 and p < self.count:
return self.id[p]```

```    def isConnected(self, p, q):
return self.find(p) == self.find(q)
pass```

```    def union(self, p, q):
pID = self.find(p)
qID = self.find(q)
if pID == qID:
return
for i in range(self.count):
if self.id[i] == pID:
self.id[i] = qID
pass```

#### 并查集的另一种实现思路

union(2, 1)

```class unionFind_version2(object):
parent = None
count = 0

def unionFind_version2(self, count):
self.parent = np.zeros(count)
self.count = count
for i in range(self.count):
self.parent[i] = i

def find(self, p):
if p >= 0 and p < self.count:
while p != self.parent[p]:
p = int(self.parent[p])
return p

def isConnected(self, p, q):
return self.find(p) == self.find(q)

def union(self, p, q):
pID = self.find(p)
qID = self.find(q)
if pID == qID:
return
self.parent[pID] = qID```

#### 并查集version2版本的优化

```class unionFind_version3(object):
parent = None
size = None
count = 0

def unionFind_version3(self, count):
self.parent = np.zeros(count)
self.size = np.zeros(count)
self.count = count
for i in range(self.count):
self.parent[i] = i
self.size[i] = 1

def find(self, p):
if p >= 0 and p < self.count:
while p != self.parent[p]:
p = int(self.parent[p])
return p

def isConnected(self, p, q):
return self.find(p) == self.find(q)

def union(self, p, q):
pID = self.find(p)
qID = self.find(q)
if pID == qID:
return
if self.size[pID] < self.size[qID]:
self.parent[pID] = qID
self.size[qID] += self.size[pID]
else:
self.parent[qID] = pID
self.size[pID] += self.size[qID]```

#### 再次优化

```class unionFind_version4(object):
parent = None
rank = None
count = 0

def unionFind_version4(self, count):
self.parent = np.zeros(count)
self.rank = np.zeros(count)
self.count = count
for i in range(self.count):
self.parent[i] = i
self.rank[i] = 1

def find(self, p):
if p >= 0 and p < self.count:
while p != self.parent[p]:
p = int(self.parent[p])
return p

def isConnected(self, p, q):
return self.find(p) == self.find(q)

def union(self, p, q):
pID = self.find(p)
qID = self.find(q)
if pID == qID:
return
if self.rank[pID] < self.rank[qID]:
self.parent[pID] = qID
elif self.rank[qID] < self.rank[pID]:
self.parent[qID] = pID
else:
self.parent[pID] = qID
self.rank[qID] += 1```

#### 路径压缩 Path Compression

```        if p >= 0 and p < self.count:
while p != self.parent[p]:
self.parent[p] = int(self.parent[int(self.parent[p])])
p = int(self.parent[p])
return p```

```        if p >= 0 and p < self.count:
if p != int(self.parent[p]):
self.parent[p] = int(self.find(int(self.parent[p])))
return int(self.parent[p])```

# 图 Graph

### 图的表示方法

1.比较简单的方法就是邻接矩阵了，用一个矩阵来表示一个图。

2.邻接表的表示方法

#### 图的实现

##### 邻接矩阵的实现
```class DenseGraph(object):
n, m = None, None
directed = None
__g = None
def __init__(self, n, directed):
self.n = n
self.m = 0
self.directed = directed
self.__g = np.array((n, n))
def v(self):
return self.n

def e(self):
return self.m

if self.hasEdge(v, w) == 1:
return
if v >= 0 and v < self.n:
if w >= 0 and w < self.n:
self.__g[v][w] = 1
if self.directed != True:
self.__g[w][v] = 1
self.m += 1
pass

def hasEdge(self, v, w):
if v >= 0 and v < self.n:
if w >= 0 and w < self.n:
return self.__g[v][w]```
##### 邻接表的实现
```class SparseGraph(object):
n, m = None, None
directed = None

def __init__(self, n, directed):
self.n = n
self.directed = directed
self.__g = list()
for i in range(n):
self.__g.append(list())

def v(self):
return self.n

def e(self):
return self.m

if v >= 0 and v < self.n:
if w >= 0 and w < self.n:
self.__g[v].append(w)
if v != w and self.directed != True:
self.__g[w].append(v)
self.m += 1

def hasEdge(self, v, w):
if v >= 0 and v < self.n:
if w >= 0 and w < self.n:
for i in range(len(self.__g[v])):
if self.__g[v][i] == w:
return True
return False```

### 图的遍历

#### 遍历邻边

；换成邻接表就很简单了，因为每一个节点下面链接的就是和他链接的节点，直接遍历就好了，所以是

。 常规实现就是遍历，不按套路出牌，实现一个迭代器来进行迭代处理。邻接矩阵的迭代器实现：

```    class FormIterator(object):
G = None
__g = None
v = None
index = None

def __init__(self, G, v):
self.G = G
self.__g = G._DenseGraph__g
self.v = v
self.index = -1
pass

def begin(self):
self.index = -1
return self.next()

def next(self):
for self.index in range(self.index + 1, self.G.v()):
if self.__g[self.v][self.index] == 1:
return self.index
return -1

def end(self):
if self.index == self.G.v()-1:
self.index += 1
return True
return self.index < self.G.v()```

```    class MatrixIterator(object):
__g = None
v = 0
index = 0
def __init__(self, G, v):
self.__g = G._SparseGraph__g
self.v = v
self.index = 0
pass

def begin(self):
self.index = 0
if len(self.__g[self.v]) > 0:
return self.__g[self.v][self.index]
return -1

def next(self):
self.index += 1
if self.index < len(self.__g[self.v]):
return self.__g[self.v][self.index]
return -1

def end(self):
return self.index >= len(self.__g[self.v])```

#### 深度优先遍历

1下面有0,0访问过了，于是退回0,0又跑到2,2下面也是0，所以又退回到0,12都看了，然后看5,5下面0看过了，看3,3又看4,4又看3,3看过了看5，5也看过了所以看6,6只有04，两个都看过了，所以退回4,4又退回3,3又退回5,5又退回0，完成遍历。 这种遍历方式有一个很重要的应用，求连通分量。

```class ReadGraph(object):
isVisited = None
count = 0
total = df.iloc[0].values[0].split(' ')
V = int(total[0])
E = int(total[1])
if G.v() != V:
print('error with edge!')
return
for i in range(E):
ab = df.iloc[i+1].values[0].split(' ')
a = int(ab[0])
b = int(ab[1])
if a >= 0 and a < V:
if b >= 0 and b < V:

```    def Component(self, G):
self.count = 0
self.isVisited = np.arange(G.v())
for i in range(G.v()):
self.isVisited[i] = False
for i in range(G.v()):
if self.isVisited[i] == False:
self.BFS(G, i)
self.count += 1

def BFS(self, G, v):
self.isVisited[v] = True
iter = G.Iterator(G, v)
w = iter.begin()
while iter.end() == True:
if w != -1:
if self.isVisited[w] == False:
self.BFS(G, w)
w = iter.next()

def vount(self):
return self.count```

#### 寻路问题

```class Path(object):
G = None
s = 0
isVisited = None
Pfrom = None
paths = []

def BFS(self, G, v):
self.isVisited[v] = True
iter = G.Iterator(G, v)
w = iter.begin()
while iter.end() == True:
if w != -1:
if self.isVisited[w] == False:
self.Pfrom[w] = v
self.BFS(G, w)
w = iter.next()```

```    def hasPath(self, w):
return self.isVisited[w]

def path(self, w):
stack = []
p = w
print(self.Pfrom)
while p != -1:
stack.append(p)
p = self.Pfrom[p]
for i in range(len(stack)):
self.paths.append(stack.pop(0))

def show(self):
for i in range(len(self.paths)):
print(self.paths[i], end = '')
if i != len(self.paths) - 1:
print('->', end='')
else:
print()
pass

def __init__(self, G, s):
self.isVisited = np.arange(G.v())
self.Pfrom = np.arange(G.v())
for i in range(G.v()):
self.isVisited[i] = False
self.Pfrom[i] = -1
self.s = s```

```    p = Path.Path(G1, 0)
p.BFS(G, 6)
p.path(2)
p.show()```

，邻接矩阵就是

#### 广度优先遍历

```    def __init__(self, G, s):
self.G = G
self.s = s
self.visited = np.arange(self.G.v())
self.Pfrom = np.arange(self.G.v())
self.ord = np.arange(self.G.v())
for i in range(G.v()):
self.visited[i] = False
self.ord[i] = -1
self.Pfrom[i] = -1

q = list()
q.append(s)
self.visited[s] = True
self.ord[s] = 0
while len(q) != 0:
v = q.pop(0)
iter = G.Iterator(G, v)
w = iter.begin()
while iter.end() == True:
if w != -1:
if self.visited[w] == False:
q.append(w)
self.visited[w] = True
self.Pfrom[w] = v
self.ord[w] = self.ord[v] + 1
w = iter.next()```

ord数组就是距离，表示当前点到原点的距离，from就是从哪个点到哪个点。当把这个点扔进队列里面的时候，就意味着这个元素就要被访问的了，所以设计已经被访问，距离就是上一个点的距离加1了。 其他的函数都是一样的，使用栈往回找即可。

```    def hasPath(self, w):
return self.visited[w]

def path(self, w):
stack = []
p = w
print(self.Pfrom)
while p != -1:
stack.append(p)
p = self.Pfrom[p]
for i in range(len(stack)):
self.paths.append(stack.pop(-1))

def show(self):
for i in range(len(self.paths)):
print(self.paths[i], end = '')
if i != len(self.paths) - 1:
print('->', end='')
else:
print()
pass```

0 条评论

## 相关文章

40570

### HashSet/HashMap详解

HashMap和HashSet是Java Collection接口两个重要的成员，其中HashMap是Map接口常用的实现类，HashSet是Set接口常用...

240100

### ES6 中的 Set

ES6 新增了几种集合类型，本文主要介绍Set以及其使用。Set对象是值的集合，你可以按照插入的顺序迭代它的元素。 Set中的元素只会出现一次，即 Set 中的...

84800

41790

9110

9430

20570

29370

### 聊聊storm nimbus的mkAssignments

storm-2.0.0/storm-server/src/main/java/org/apache/storm/daemon/nimbus/Nimbus.jav...

13420

15410