Skip to content

Commit b6805c6

Browse files
heqin-zhuheqin-zhu
committed
Add binaryheap, circularqueue, linkedlist, maxxor, union find set
1 parent 273702e commit b6805c6

33 files changed

Lines changed: 630 additions & 54 deletions

‎README.md‎

Lines changed: 15 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -2,16 +2,12 @@
22
# Algorithm
33
>Notes and codes for learning algorithm and data structures :smiley:
44
5-
Some pictures and ideas are from `<<Introduction to Algotithm>>
5+
Some pictures and ideas are from `<<Introduction to Algotithm>>`
66

7-
I use python 3.6+ and c++ to implements them.
8-
Since I used f-Strings in python, you may use python 3.6+ to run the following python scripts.
9-
10-
>>I am still learning new things and this repo is always updating.
7+
I use python 3.6+ and c/c++ to implement them.
118

129
# Notice
13-
Currently, Github can't render latex math formulas.
14-
So,if you wannt to view the notes which contain latex math formulas and are in markdown format, you can visit [my blog](https://mbinary.coding.me)
10+
Currently, Github can't render latex math formulas.Thus,if you want to view the markodwn notes which contain latex math formulas, you can visit [my blog](https://mbinary.coding.me)
1511

1612
# Index
1713
* [.](.)
@@ -21,12 +17,15 @@ So,if you wannt to view the notes which contain latex math formulas and are in m
2117
* [allOone](./dataStructure/allOone)
2218
* [bTree.py](./dataStructure/bTree.py)
2319
* [binaryHeap.py](./dataStructure/binaryHeap.py)
20+
* [binaryHeap1.py](./dataStructure/binaryHeap1.py)
2421
* [binaryTree.py](./dataStructure/binaryTree.py)
22+
* [circularQueue.py](./dataStructure/circularQueue.py)
2523
* [graph](./dataStructure/graph)
2624
* [hashTable.py](./dataStructure/hashTable.py)
2725
* [huffman](./dataStructure/huffman)
2826
* [intervalTree.py](./dataStructure/intervalTree.py)
2927
* [leftHeap.py](./dataStructure/leftHeap.py)
28+
* [linkedList.py](./dataStructure/linkedList.py)
3029
* [loserTree.py](./dataStructure/loserTree.py)
3130
* [map.cc](./dataStructure/map.cc)
3231
* [polynomial.cpp](./dataStructure/polynomial.cpp)
@@ -35,6 +34,7 @@ So,if you wannt to view the notes which contain latex math formulas and are in m
3534
* [redBlackTree0.py](./dataStructure/redBlackTree0.py)
3635
* [splayTree.py](./dataStructure/splayTree.py)
3736
* [trie](./dataStructure/trie)
37+
* [unionFindSet](./dataStructure/unionFindSet)
3838
* [winnerTree.py](./dataStructure/winnerTree.py)
3939
* [divideAndConquer](./divideAndConquer)
4040
* [min_distance_of_n_points.py](./divideAndConquer/min_distance_of_n_points.py)
@@ -59,29 +59,15 @@ So,if you wannt to view the notes which contain latex math formulas and are in m
5959
* [stoneGame.py](./dynamicProgramming/stoneGame.py)
6060
* [testVec2d.hs](./dynamicProgramming/testVec2d.hs)
6161
* [wildcard_matching.py](./dynamicProgramming/wildcard_matching.py)
62+
* [graph](./graph)
63+
* [isBipartGraph.py](./graph/isBipartGraph.py)
6264
* [math](./math)
6365
* [README.md](./math/README.md)
64-
* [euler.py](./math/euler.py)
65-
* [factor.py](./math/factor.py)
66-
* [gcd.py](./math/gcd.py)
67-
* [isPrime.py](./math/isPrime.py)
68-
* [modulo_equation.py](./math/modulo_equation.py)
69-
* [num_weight.py](./math/num_weight.py)
70-
* [permute_back_track.py](./math/permute_back_track.py)
71-
* [permute_cantor.c](./math/permute_cantor.c)
72-
* [permute_divide_and_conquer.py](./math/permute_divide_and_conquer.py)
73-
* [permute_next_arrangement.c](./math/permute_next_arrangement.c)
74-
* [primesLEn.hs](./math/primesLEn.hs)
75-
* [numericalAnalysis](./numericalAnalysis)
76-
* [README.md](./numericalAnalysis/README.md)
77-
* [interplotion.py](./numericalAnalysis/interplotion.py)
78-
* [iteration.py](./numericalAnalysis/iteration.py)
79-
* [least_square.py](./numericalAnalysis/least_square.py)
80-
* [linear_equation.py](./numericalAnalysis/linear_equation.py)
81-
* [numerical_differential.py](./numericalAnalysis/numerical_differential.py)
82-
* [numerical_integration.py](./numericalAnalysis/numerical_integration.py)
83-
* [solve-linear-by-iteration.py](./numericalAnalysis/solve-linear-by-iteration.py)
84-
* [vector_norm.py](./numericalAnalysis/vector_norm.py)
66+
* [convertWeight.py](./math/convertWeight.py)
67+
* [fastPow.py](./math/fastPow.py)
68+
* [numberTheory](./math/numberTheory)
69+
* [numericalAnalysis](./math/numericalAnalysis)
70+
* [permute](./math/permute)
8571
* [search](./search)
8672
* [8Astar.py](./search/8Astar.py)
8773
* [BFS_knight.hs](./search/BFS_knight.hs)
@@ -91,6 +77,7 @@ So,if you wannt to view the notes which contain latex math formulas and are in m
9177
* [sort](./sort)
9278
* [binaryTree.py](./sort/binaryTree.py)
9379
* [heapSort.py](./sort/heapSort.py)
80+
* [quickSort.c](./sort/quickSort.c)
9481
* [quickSort.py](./sort/quickSort.py)
9582
* [radixSort.py](./sort/radixSort.py)
9683
* [select.py](./sort/select.py)

‎dataStructure/binaryHeap1.py‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
from functools import partial
2+
class heap:
3+
def __init__(self,lst,reverse = False):
4+
self.data= heapify(lst,reverse)
5+
self.cmp = partial(lambda i,j,r:cmp(self.data[i],self.data[j],r),r= reverse)
6+
def getTop(self):
7+
return self.data[0]
8+
def __getitem__(self,idx):
9+
return self.data[idx]
10+
def __bool__(self):
11+
return self.data != []
12+
def popTop(self):
13+
ret = self.data[0]
14+
n = len(self.data)
15+
cur = 1
16+
while cur * 2<=n:
17+
chd = cur-1
18+
r_idx = cur*2
19+
l_idx = r_idx-1
20+
if r_idx==n:
21+
self.data[chd] = self.data[l_idx]
22+
break
23+
j = l_idx if self.cmp(l_idx,r_idx)<0 else r_idx
24+
self.data[chd] = self.data[j]
25+
cur = j+1
26+
self.data[cur-1] = self.data[-1]
27+
self.data.pop()
28+
return ret
29+
30+
def addNode(self,val):
31+
self.data.append(val)
32+
self.data = one_heapify(len(self.data)-1)
33+
34+
35+
def cmp(n1,n2,reverse=False):
36+
fac = -1 if reverse else 1
37+
if n1 < n2: return -fac
38+
elif n1 > n2: return fac
39+
return 0
40+
41+
def heapify(lst,reverse = False):
42+
for i in range(len(lst)):
43+
lst = one_heapify(lst,i,reverse)
44+
return lst
45+
def one_heapify(lst,cur,reverse = False):
46+
cur +=1
47+
while cur>1:
48+
chd = cur-1
49+
prt = cur//2-1
50+
if cmp(lst[prt],lst[chd],reverse)<0:
51+
break
52+
lst[prt],lst[chd] = lst[chd], lst[prt]
53+
cur = prt+1
54+
return lst
55+
def heapSort(lst,reverse = False):
56+
lst = lst.copy()
57+
hp = heap(lst,reverse)
58+
ret = []
59+
while hp:
60+
ret.append(hp.popTop())
61+
return ret
62+
63+
64+
if __name__ == '__main__':
65+
from random import randint
66+
n = randint(10,20)
67+
lst = [randint(0,100) for i in range(n)]
68+
print('random : ', lst)
69+
print('small-heap: ', heapify(lst))
70+
print('big-heap : ', heapify(lst,True))
71+
print('ascend : ', heapSort(lst))
72+
print('descend : ', heapSort(lst,True))

‎dataStructure/circularQueue.py‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
class MyCircularQueue:
2+
3+
def __init__(self, k):
4+
"""
5+
Initialize your data structure here. Set the size of the queue to be k.
6+
:type k: int
7+
"""
8+
self.size = k+1
9+
self.data = [0]*self.size
10+
self.head = self.rear = 0
11+
12+
def enQueue(self, value):
13+
"""
14+
Insert an element into the circular queue. Return true if the operation is successful.
15+
:type value: int
16+
:rtype: bool
17+
"""
18+
if self.isFull():
19+
return False
20+
self.data[self.rear] = value
21+
self.rear = (self.rear+1)%self.size
22+
return True
23+
def deQueue(self):
24+
"""
25+
Delete an element from the circular queue. Return true if the operation is successful.
26+
:rtype: bool
27+
"""
28+
if self.isEmpty():
29+
return False
30+
self.head = (self.head+1)%self.size
31+
return True
32+
33+
def Front(self):
34+
"""
35+
Get the front item from the queue.
36+
:rtype: int
37+
"""
38+
if self.isEmpty():
39+
return -1
40+
return self.data[self.head]
41+
42+
43+
def Rear(self):
44+
"""
45+
Get the last item from the queue.
46+
:rtype: int
47+
"""
48+
if self.isEmpty():
49+
return -1
50+
return self.data[(self.rear-1)%self.size]
51+
52+
def isEmpty(self):
53+
"""
54+
Checks whether the circular queue is empty or not.
55+
:rtype: bool
56+
"""
57+
return self.head ==self.rear
58+
59+
60+
def isFull(self):
61+
"""
62+
Checks whether the circular queue is full or not.
63+
:rtype: bool
64+
"""
65+
return (self.head - self.rear)%self.size ==1
66+
67+
68+
69+
# Your MyCircularQueue object will be instantiated and called as such:
70+
# obj = MyCircularQueue(k)
71+
# param_1 = obj.enQueue(value)
72+
# param_2 = obj.deQueue()
73+
# param_3 = obj.Front()
74+
# param_4 = obj.Rear()
75+
# param_5 = obj.isEmpty()
76+
# param_6 = obj.isFull()

‎dataStructure/linkedList.py‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
class node:
2+
def __init__(self,val,follow=None):
3+
self.val = val
4+
self.follow = follow
5+
class MyLinkedList:
6+
7+
def __init__(self):
8+
"""
9+
Initialize your data structure here.
10+
"""
11+
12+
self.tail = self.head = node(None)
13+
14+
def get(self, index):
15+
"""
16+
Get the value of the index-th node in the linked list. If the index is invalid, return -1.
17+
:type index: int
18+
:rtype: int
19+
"""
20+
nd = self.head
21+
for i in range(index+1):
22+
nd = nd.follow
23+
if nd is None:return -1
24+
return nd.val
25+
26+
def addAtHead(self, val):
27+
"""
28+
Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
29+
:type val: int
30+
:rtype: void
31+
"""
32+
nd = node(val,self.head.follow)
33+
self.head .follow = nd
34+
if self.tail.val is None:self.tail = nd
35+
def addAtTail(self, val):
36+
"""
37+
Append a node of value val to the last element of the linked list.
38+
:type val: int
39+
:rtype: void
40+
"""
41+
self.tail.follow = node(val)
42+
self.tail = self.tail.follow
43+
44+
45+
def addAtIndex(self, index, val):
46+
"""
47+
Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
48+
:type index: int
49+
:type val: int
50+
:rtype: void
51+
"""
52+
nd = self.head
53+
for i in range(index):
54+
nd = nd.follow
55+
if nd is None:
56+
return
57+
new = node(val,nd.follow)
58+
nd.follow = new
59+
if self.tail == nd:
60+
self.tail = new
61+
62+
63+
def deleteAtIndex(self, index):
64+
"""
65+
Delete the index-th node in the linked list, if the index is valid.
66+
:type index: int
67+
:rtype: void
68+
"""
69+
nd = self.head
70+
for i in range(index):
71+
nd = nd.follow
72+
if nd is None:return
73+
if self.tail == nd.follow:self.tail = nd
74+
if nd.follow:nd.follow = nd.follow.follow
75+
76+
77+
78+
# Your MyLinkedList object will be instantiated and called as such:
79+
# obj = MyLinkedList()
80+
# param_1 = obj.get(index)
81+
# obj.addAtHead(val)
82+
# obj.addAtTail(val)
83+
# obj.addAtIndex(index,val)
84+
# obj.deleteAtIndex(index)

‎dataStructure/trie/mapSum.py‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,6 @@ def insert(self, key, val):
6161
nd[i] = node(i)
6262
nd = nd[i]
6363
nd.n = val
64-
6564
def visit(self,nd):
6665
ret = nd.n
6766
for chd in nd:

0 commit comments

Comments
 (0)