Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2817964

Browse files
committed
heap and priority queue added
1 parenta561e6f commit2817964

File tree

7 files changed

+297
-51
lines changed

7 files changed

+297
-51
lines changed

‎src/data_structures/heap/__test__/max_heap.test.py

Lines changed: 7 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -110,28 +110,9 @@ def test_find_item_indices_in_heap(self):
110110
self.assertEqual(maxHeap.find(12), [0])
111111
self.assertEqual(maxHeap.find(11), [1,4])
112112

113-
deftest_remove_items_with_heapify_down_from_heap(self):
113+
deftest_remove_items_from_heap(self):
114114
"""
115-
Test to remove items from heap with heapify down
116-
"""
117-
maxHeap=MaxHeap()
118-
119-
maxHeap.add(3)
120-
maxHeap.add(12)
121-
maxHeap.add(10)
122-
maxHeap.add(11)
123-
maxHeap.add(11)
124-
125-
self.assertEqual(maxHeap.toList(), [12,11,10,3,11])
126-
127-
self.assertEqual(maxHeap.remove(12).toList(), [11,11,10,3])
128-
self.assertEqual(maxHeap.remove(12).peek(),11)
129-
self.assertEqual(maxHeap.remove(11).toList(), [10,3])
130-
self.assertEqual(maxHeap.remove(10).peek(),3)
131-
132-
deftest_remove_items_with_heapify_up_from_heap(self):
133-
"""
134-
Test to remove items from heap with heapify up
115+
Test to remove items from heap
135116
"""
136117
maxHeap=MaxHeap()
137118

@@ -151,10 +132,11 @@ def test_remove_items_with_heapify_up_from_heap(self):
151132
self.assertEqual(maxHeap.remove(4).toList(), [10,8,6,7,6,1,5,3,2])
152133
self.assertEqual(maxHeap.remove(3).toList(), [10,8,6,7,6,1,5,2])
153134
self.assertEqual(maxHeap.remove(5).toList(), [10,8,6,7,6,1,2])
154-
self.assertEqual(maxHeap.remove(10).toList(), [2,8,6,7,6,1])
155-
self.assertEqual(maxHeap.remove(6).toList(), [2,8,1,7])
156-
self.assertEqual(maxHeap.remove(2).toList(), [7,8,1])
157-
self.assertEqual(maxHeap.remove(1).toList(), [7,8])
135+
self.assertEqual(maxHeap.remove(10).toList(), [8,7,6,2,6,1])
136+
137+
self.assertEqual(maxHeap.remove(6).toList(), [8,7,1,2])
138+
self.assertEqual(maxHeap.remove(2).toList(), [8,7,1])
139+
self.assertEqual(maxHeap.remove(1).toList(), [8,7])
158140
self.assertEqual(maxHeap.remove(7).toList(), [8])
159141
self.assertEqual(maxHeap.remove(8).toList(), [])
160142

Lines changed: 168 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,168 @@
1+
importos
2+
importsys
3+
importunittest
4+
5+
file_path=os.path.abspath(__file__)
6+
src_dir=os.path.dirname(os.path.dirname(os.path.dirname(os.path.dirname(file_path))))
7+
root_folder=os.path.abspath(src_dir)
8+
sys.path.append(root_folder)
9+
fromdata_structures.heap.min_heapimportMinHeap
10+
fromutils.comparatorimportComparator
11+
12+
13+
classTestCase(unittest.TestCase):
14+
deftest_create_empty_max_heap(self):
15+
"""
16+
Test to create an empty minHeap
17+
"""
18+
minHeap=MinHeap()
19+
20+
self.assertIsNone(minHeap.peek())
21+
self.assertTrue(minHeap.isEmpty())
22+
23+
deftest_add_items_to_heap(self):
24+
"""
25+
Test to add items to the heap and heapify it up
26+
"""
27+
minHeap=MinHeap()
28+
29+
minHeap.add(5)
30+
31+
self.assertFalse(minHeap.isEmpty())
32+
self.assertEqual(minHeap.peek(),5)
33+
self.assertEqual(minHeap.toList(), [5])
34+
35+
minHeap.add(3)
36+
37+
self.assertEqual(minHeap.peek(),3)
38+
self.assertEqual(minHeap.toList(), [3,5])
39+
40+
minHeap.add(10)
41+
42+
self.assertEqual(minHeap.peek(),3)
43+
self.assertEqual(minHeap.toList(), [3,5,10])
44+
45+
deftest_poll_items_from_heap(self):
46+
"""
47+
Test to poll items from the heap and heapify it down
48+
"""
49+
minHeap=MinHeap()
50+
51+
minHeap.add(5)
52+
minHeap.add(3)
53+
minHeap.add(10)
54+
minHeap.add(11)
55+
minHeap.add(1)
56+
57+
self.assertEqual(minHeap.toList(), [1,3,10,11,5])
58+
59+
self.assertEqual(minHeap.poll(),1)
60+
self.assertEqual(minHeap.toList(), [3,5,10,11])
61+
62+
self.assertEqual(minHeap.poll(),3)
63+
self.assertEqual(minHeap.toList(), [5,11,10])
64+
65+
self.assertEqual(minHeap.poll(),5)
66+
self.assertEqual(minHeap.toList(), [10,11])
67+
68+
self.assertEqual(minHeap.poll(),10)
69+
self.assertEqual(minHeap.toList(), [11])
70+
71+
self.assertEqual(minHeap.poll(),11)
72+
self.assertEqual(minHeap.toList(), [])
73+
74+
self.assertEqual(minHeap.poll(),None)
75+
self.assertEqual(minHeap.toList(), [])
76+
77+
deftest_heapify_down_from_right_beanch_in_heap(self):
78+
"""
79+
Test to heapify down through the right branch as well
80+
"""
81+
minHeap=MinHeap()
82+
83+
minHeap.add(3)
84+
minHeap.add(12)
85+
minHeap.add(10)
86+
87+
self.assertEqual(minHeap.toList(), [3,12,10])
88+
89+
minHeap.add(11)
90+
self.assertEqual(minHeap.toList(), [3,11,10,12])
91+
92+
self.assertEqual(minHeap.poll(),3)
93+
self.assertEqual(minHeap.toList(), [10,11,12])
94+
95+
deftest_find_item_indices_in_heap(self):
96+
"""
97+
Test to find item indices in heap
98+
"""
99+
minHeap=MinHeap()
100+
101+
minHeap.add(3)
102+
minHeap.add(12)
103+
minHeap.add(10)
104+
minHeap.add(11)
105+
minHeap.add(11)
106+
107+
self.assertEqual(minHeap.toList(), [3,11,10,12,11])
108+
109+
self.assertEqual(minHeap.find(5), [])
110+
self.assertEqual(minHeap.find(3), [0])
111+
self.assertEqual(minHeap.find(11), [1,4])
112+
113+
deftest_remove_items_from_heap(self):
114+
"""
115+
Test to remove items from heap
116+
"""
117+
minHeap=MinHeap()
118+
119+
minHeap.add(3)
120+
minHeap.add(10)
121+
minHeap.add(5)
122+
minHeap.add(6)
123+
minHeap.add(7)
124+
minHeap.add(4)
125+
minHeap.add(6)
126+
minHeap.add(8)
127+
minHeap.add(2)
128+
minHeap.add(1)
129+
130+
self.assertEqual(minHeap.toList(), [1,2,4,6,3,5,6,10,8,7])
131+
132+
self.assertEqual(minHeap.remove(8).toList(), [1,2,4,6,3,5,6,10,7])
133+
self.assertEqual(minHeap.remove(7).toList(), [1,2,4,6,3,5,6,10])
134+
self.assertEqual(minHeap.remove(1).toList(), [2,3,4,6,10,5,6])
135+
self.assertEqual(minHeap.remove(2).toList(), [3,6,4,6,10,5])
136+
self.assertEqual(minHeap.remove(6).toList(), [3,5,4,10])
137+
self.assertEqual(minHeap.remove(10).toList(), [3,5,4])
138+
self.assertEqual(minHeap.remove(5).toList(), [3,4])
139+
self.assertEqual(minHeap.remove(3).toList(), [4])
140+
self.assertEqual(minHeap.remove(4).toList(), [])
141+
142+
deftest_remove_items_with_custom_comparator_from_heap(self):
143+
"""
144+
Test to remove items from heap with custom finding comparator
145+
"""
146+
minHeap=MinHeap()
147+
148+
minHeap.add("a")
149+
minHeap.add("bb")
150+
minHeap.add("ccc")
151+
minHeap.add("dddd")
152+
153+
self.assertEqual(minHeap.toList(), ["a","bb","ccc","dddd"])
154+
155+
defcustomFun(a,b):
156+
iflen(a)==len(b):
157+
return0
158+
159+
return-1if (len(a)<len(b))else1
160+
161+
comparator=Comparator(customFun)
162+
163+
minHeap.remove("ccc",comparator)
164+
self.assertEqual(minHeap.toList(), ["a","bb","dddd"])
165+
166+
167+
if__name__=="__main__":
168+
unittest.main()

‎src/data_structures/heap/heap.py

Lines changed: 20 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,3 @@
1-
importmath
21
importos
32
importsys
43

@@ -21,7 +20,7 @@ def getRightChildIndex(self, parentIndex):
2120
return (2*parentIndex)+2
2221

2322
defgetParentIndex(self,childIndex):
24-
returnmath.floor((childIndex-1)/2)
23+
return(childIndex-1)//2
2524

2625
defhasParent(self,childIndex):
2726
returnself.getParentIndex(childIndex)>=0
@@ -42,10 +41,10 @@ def parent(self, childIndex):
4241
returnself.heapContainer[self.getParentIndex(childIndex)]
4342

4443
defswap(self,indexOne,indexTwo):
45-
temp=self.heapContainer[indexTwo]
46-
47-
self.heapContainer[indexTwo]=self.heapContainer[indexOne]
48-
self.heapContainer[indexOne]=temp
44+
self.heapContainer[indexOne],self.heapContainer[indexTwo]= (
45+
self.heapContainer[indexTwo],
46+
self.heapContainer[indexOne],
47+
)
4948

5049
defpairIsInCorrectOrder(self,firstElement,secondElement):
5150
# Checks if pair of heap elements is in correct order.
@@ -73,10 +72,18 @@ def heapifyUp(self, customStartIndex=None):
7372
# Take the last element (last in array or the bottom left in a tree)
7473
# in the heap container and lift it up until it is in the correct
7574
# order with respect to its parent element.
76-
currentIndex=customStartIndexorlen(self.heapContainer)-1
75+
currentIndex= (
76+
customStartIndex
77+
if (customStartIndexisnotNone)
78+
elselen(self.heapContainer)-1
79+
)
7780

78-
whileself.hasParent(currentIndex)andnotself.pairIsInCorrectOrder(
79-
self.parent(currentIndex),self.heapContainer[currentIndex]
81+
while (
82+
self.hasParent(currentIndex)
83+
andself.pairIsInCorrectOrder(
84+
self.parent(currentIndex),self.heapContainer[currentIndex]
85+
)
86+
==False
8087
):
8188
self.swap(currentIndex,self.getParentIndex(currentIndex))
8289
currentIndex=self.getParentIndex(currentIndex)
@@ -151,17 +158,11 @@ def remove(self, item, comparator=None):
151158

152159
parentItem=self.parent(indexToRemove)
153160

154-
# If there is no parent or parent is in correct order with the node
155-
# we're going to delete then heapify down. Otherwise heapify up.
156-
ifself.hasLeftChild(indexToRemove)and (
157-
notparentItem
158-
orself.pairIsInCorrectOrder(
159-
parentItem,self.heapContainer[indexToRemove]
160-
)
161-
):
161+
# If there is a left child and left child is not
162+
# in correct order with the node
163+
# we're going to delete then heapify down.
164+
ifself.hasLeftChild(indexToRemove):
162165
self.heapifyDown(indexToRemove)
163-
else:
164-
self.heapifyUp(indexToRemove)
165166

166167
returnself
167168

‎src/data_structures/priority_queue/__init__.py

Whitespace-only changes.
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
importos
2+
importsys
3+
importunittest
4+
5+
file_path=os.path.abspath(__file__)
6+
src_dir=os.path.dirname(os.path.dirname(os.path.dirname(os.path.dirname(file_path))))
7+
root_folder=os.path.abspath(src_dir)
8+
sys.path.append(root_folder)
9+
fromdata_structures.priority_queue.priority_queueimportPriorityQueue
10+
11+
12+
classTestCase(unittest.TestCase):
13+
deftest_create_default_priority_queue(self):
14+
"""
15+
Test to create a default PriorityQueue
16+
"""
17+
priorityQueue=PriorityQueue()
18+
19+
self.assertIsInstance(priorityQueue,PriorityQueue)
20+
21+
deftest_insert_items_to_queue(self):
22+
"""
23+
Test to insert items to the queue and respect priorities
24+
"""
25+
priorityQueue=PriorityQueue()
26+
27+
priorityQueue.add(10,1)
28+
self.assertEqual(priorityQueue.peek(),10)
29+
30+
priorityQueue.add(5,2)
31+
self.assertEqual(priorityQueue.peek(),10)
32+
33+
priorityQueue.add(100,0)
34+
self.assertEqual(priorityQueue.peek(),100)
35+
36+
deftest_objects_in_queue(self):
37+
"""
38+
Test to use objects in priority queue
39+
"""
40+
priorityQueue=PriorityQueue()
41+
42+
user1= {"name":"Ram"}
43+
user2= {"name":"Krishna"}
44+
user3= {"name":"Shiva"}
45+
46+
priorityQueue.add(user1,1)
47+
self.assertEqual(priorityQueue.peek(),user1)
48+
49+
50+
if__name__=="__main__":
51+
unittest.main()
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
importos
2+
importsys
3+
4+
file_path=os.path.abspath(__file__)
5+
src_dir=os.path.dirname(os.path.dirname(os.path.dirname(file_path)))
6+
root_folder=os.path.abspath(src_dir)
7+
sys.path.append(root_folder)
8+
fromutils.comparatorimportComparator
9+
fromdata_structures.heap.min_heapimportMinHeap
10+
11+
12+
classPriorityQueue(MinHeap):
13+
def__init__(self,comparatorFunction=None):
14+
super().__init__(comparatorFunction)
15+
16+
self.priorities=dict()
17+
18+
self.compare=Comparator(self.comparePriority)
19+
20+
defcompareValue(self,a,b):
21+
ifa==b:
22+
return0
23+
24+
return-1ifa<belse1
25+
26+
defcomparePriority(self,a,b):
27+
ifself.priorities.get(a)==self.priorities.get(b):
28+
return0
29+
30+
return-1ifself.priorities.get(a)<self.priorities.get(b)else1
31+
32+
defadd(self,item,priority=0):
33+
self.priorities[item]=priority
34+
super().add(item)
35+
returnself
36+
37+
defremove(self,item,comparator=None):
38+
super().remove(item,comparator)
39+
self.priorities.__delitem__(item)
40+
returnself
41+
42+
defchangePriority(self,item,priority):
43+
self.remove(item,Comparator(self.compareValue))
44+
self.add(item,priority)
45+
returnself
46+
47+
deffindByValue(self,item):
48+
returnself.find(item,Comparator(self.compareValue))
49+
50+
defhasValue(self,item):
51+
returnlen(self.findByValue(item))>0

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp