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

Commita561e6f

Browse files
committed
max heap test updated
1 parentb4a7650 commita561e6f

File tree

2 files changed

+167
-4
lines changed

2 files changed

+167
-4
lines changed

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

Lines changed: 163 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@
77
root_folder=os.path.abspath(src_dir)
88
sys.path.append(root_folder)
99
fromdata_structures.heap.max_heapimportMaxHeap
10+
fromutils.comparatorimportComparator
1011

1112

1213
classTestCase(unittest.TestCase):
@@ -19,6 +20,168 @@ def test_create_empty_max_heap(self):
1920
self.assertIsNone(maxHeap.peek())
2021
self.assertTrue(maxHeap.isEmpty())
2122

23+
deftest_add_items_to_heap(self):
24+
"""
25+
Test to add items to the heap and heapify it up
26+
"""
27+
maxHeap=MaxHeap()
28+
29+
maxHeap.add(5)
30+
31+
self.assertFalse(maxHeap.isEmpty())
32+
self.assertEqual(maxHeap.peek(),5)
33+
self.assertEqual(maxHeap.toList(), [5])
34+
35+
maxHeap.add(3)
36+
37+
self.assertEqual(maxHeap.peek(),5)
38+
self.assertEqual(maxHeap.toList(), [5,3])
39+
40+
maxHeap.add(10)
41+
42+
self.assertEqual(maxHeap.peek(),10)
43+
self.assertEqual(maxHeap.toList(), [10,3,5])
44+
45+
deftest_poll_items_from_heap(self):
46+
"""
47+
Test to poll items from the heap and heapify it down
48+
"""
49+
maxHeap=MaxHeap()
50+
51+
maxHeap.add(5)
52+
maxHeap.add(3)
53+
maxHeap.add(10)
54+
maxHeap.add(11)
55+
maxHeap.add(1)
56+
57+
self.assertEqual(maxHeap.toList(), [11,10,5,3,1])
58+
59+
self.assertEqual(maxHeap.poll(),11)
60+
self.assertEqual(maxHeap.toList(), [10,3,5,1])
61+
62+
self.assertEqual(maxHeap.poll(),10)
63+
self.assertEqual(maxHeap.toList(), [5,3,1])
64+
65+
self.assertEqual(maxHeap.poll(),5)
66+
self.assertEqual(maxHeap.toList(), [3,1])
67+
68+
self.assertEqual(maxHeap.poll(),3)
69+
self.assertEqual(maxHeap.toList(), [1])
70+
71+
self.assertEqual(maxHeap.poll(),1)
72+
self.assertEqual(maxHeap.toList(), [])
73+
74+
self.assertEqual(maxHeap.poll(),None)
75+
self.assertEqual(maxHeap.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+
maxHeap=MaxHeap()
82+
83+
maxHeap.add(3)
84+
maxHeap.add(12)
85+
maxHeap.add(10)
86+
87+
self.assertEqual(maxHeap.toList(), [12,3,10])
88+
89+
maxHeap.add(11)
90+
self.assertEqual(maxHeap.toList(), [12,11,10,3])
91+
92+
self.assertEqual(maxHeap.poll(),12)
93+
self.assertEqual(maxHeap.toList(), [11,3,10])
94+
95+
deftest_find_item_indices_in_heap(self):
96+
"""
97+
Test to find item indices in heap
98+
"""
99+
maxHeap=MaxHeap()
100+
101+
maxHeap.add(3)
102+
maxHeap.add(12)
103+
maxHeap.add(10)
104+
maxHeap.add(11)
105+
maxHeap.add(11)
106+
107+
self.assertEqual(maxHeap.toList(), [12,11,10,3,11])
108+
109+
self.assertEqual(maxHeap.find(5), [])
110+
self.assertEqual(maxHeap.find(12), [0])
111+
self.assertEqual(maxHeap.find(11), [1,4])
112+
113+
deftest_remove_items_with_heapify_down_from_heap(self):
114+
"""
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
135+
"""
136+
maxHeap=MaxHeap()
137+
138+
maxHeap.add(3)
139+
maxHeap.add(10)
140+
maxHeap.add(5)
141+
maxHeap.add(6)
142+
maxHeap.add(7)
143+
maxHeap.add(4)
144+
maxHeap.add(6)
145+
maxHeap.add(8)
146+
maxHeap.add(2)
147+
maxHeap.add(1)
148+
149+
self.assertEqual(maxHeap.toList(), [10,8,6,7,6,4,5,3,2,1])
150+
151+
self.assertEqual(maxHeap.remove(4).toList(), [10,8,6,7,6,1,5,3,2])
152+
self.assertEqual(maxHeap.remove(3).toList(), [10,8,6,7,6,1,5,2])
153+
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])
158+
self.assertEqual(maxHeap.remove(7).toList(), [8])
159+
self.assertEqual(maxHeap.remove(8).toList(), [])
160+
161+
deftest_remove_items_with_custom_comparator_from_heap(self):
162+
"""
163+
Test to remove items from heap with custom finding comparator
164+
"""
165+
maxHeap=MaxHeap()
166+
167+
maxHeap.add("a")
168+
maxHeap.add("bb")
169+
maxHeap.add("ccc")
170+
maxHeap.add("dddd")
171+
172+
self.assertEqual(maxHeap.toList(), ["dddd","ccc","bb","a"])
173+
174+
defcustomFun(a,b):
175+
iflen(a)==len(b):
176+
return0
177+
178+
return-1if (len(a)<len(b))else1
179+
180+
comparator=Comparator(customFun)
181+
182+
maxHeap.remove("ccc",comparator)
183+
self.assertEqual(maxHeap.toList(), ["dddd","a","bb"])
184+
22185

23186
if__name__=="__main__":
24187
unittest.main()

‎src/data_structures/heap/heap.py

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -69,7 +69,7 @@ def find(self, item, comparator=None):
6969
defisEmpty(self):
7070
returnnotlen(self.heapContainer)
7171

72-
defheapifyUp(self,customStartIndex):
72+
defheapifyUp(self,customStartIndex=None):
7373
# Take the last element (last in array or the bottom left in a tree)
7474
# in the heap container and lift it up until it is in the correct
7575
# order with respect to its parent element.
@@ -115,7 +115,7 @@ def poll(self):
115115
returnNone
116116

117117
iflen(self.heapContainer)==1:
118-
returnself.heapContainer.pop
118+
returnself.heapContainer.pop()
119119

120120
item=self.heapContainer[0]
121121

@@ -165,5 +165,5 @@ def remove(self, item, comparator=None):
165165

166166
returnself
167167

168-
deftoString(self):
169-
returnself.heapContainer.__str__()
168+
deftoList(self):
169+
returnself.heapContainer

0 commit comments

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