$30
CS261-Data Structures Solved
This method returns a number of empty buckets in the hash table.
Example #1:
m = HashMap(100, h ash_function_1) print(m.empty_buckets(), m.size, m.capacity) m.put('key1', 1 0) print(m.empty_buckets(), m.size, m.capacity) m.put('key2', 2 0) print(m.empty_buckets(), m.size, m.capacity) m.put('key1', 3 0) print(m.empty_buckets(), m.size, m.capacity) m.put('key4', 4 0)
print(m.empty_buckets(), m.size, m.capacity)
Output:
100 0 100
99 1 100
98 2 100
98 2 100
97 3 100
Example #2:
# this test assumes that put() has already been correctly implemented m = HashMap(50, hash_function_1) for i in range(150):
m.put('key' + str(i), i * 100) if i % 30 == 0:
print(m.empty_buckets(), m.size, m.capacity)
Output: 49 1 50
39 31 50
36 61 50
33 91 50
30 121 50
table_load (self) -> float:
This method returns t he current hash table load factor.
Example #1:
m = HashMap(100, h ash_function_1) print(m.table_load()) m.put('key1', 1 0) print(m.table_load()) m.put('key2', 2 0) print(m.table_load()) m.put('key1', 3 0) print(m.table_load())
Output:
0.0
0.01
0.02
0.02
Example #2:
m = HashMap(50, hash_function_1) for i in range(50):
m.put('key' + str(i), i * 100) if i % 10 == 0:
print(m.table_load(), m.size, m.capacity)
Output:
0.02 1 50
0.22 11 50
0.42 21 50
0.62 31 50
0.82 41 50
clear (self) -> None:
This method clears t he content of the hash map. It does not change underlying hash table capacity.
Example #1:
m = HashMap(100, h ash_function_1) print(m.size, m .capacity) m.put('key1', 1 0)
m.put('key2', 2 0)
m.put('key1', 3 0) print(m.size, m .capacity) m.clear()
print(m.size, m .capacity)
Output :
0 100
2 100
0 100
Example #2:
m = HashMap(50, hash_function_1) print(m.size, m .capacity) m.put('key1', 1 0) print(m.size, m .capacity) m.put('key2', 2 0) print(m.size, m .capacity) m.resize_table(100) print(m.size, m .capacity) m.clear()
print(m.size, m .capacity)
Output :
0 50
1 50
2 50
2 100
0 100
put (self, key: str, value: object) -> None:
This method updates t he key / value pair in the hash m ap. If a given key already exists in the hash map, its associated value should be replaced with the new value. If a given key is not in the hash map, a key / value pair should b e added.
Example #1:
m = HashMap(50, hash_function_1) for i in range(150):
m.put('str' + str(i), i * 100) if i % 25 = = 24:
print(m.empty_buckets(), m.table_load(), m.size, m.capacity)
Output:
39 0.5 25 50
37 1.0 50 50
35 1.5 75 50
32 2.0 100 50
30 2.5 125 50
30 3.0 150 50
Example #2:
m = HashMap(40, hash_function_2) for i in range(50):
m.put('str' + str(i // 3), i * 100) if i % 10 = = 9:
print(m.empty_buckets(), m.table_load(), m.size, m.capacity)
Output:
36 0.1 4 40
33 0.175 7 40
30 0.25 10 40
27 0.35 14 40 25 0.425 17 40
contains_key (self, key: str) -> bool:
This method returns T rue if the given key is in the hash map, otherwise it returns False. An empty hash map does not contain any keys.
Example #1:
m = HashMap(50, hash_function_1) print(m.contains_key('key1')) m.put('key1', 1 0)
m.put('key2', 2 0)
m.put('key3', 3 0) print(m.contains_key('key1')) print(m.contains_key('key4')) print(m.contains_key('key2')) print(m.contains_key('key3')) m.remove('key3') print(m.contains_key('key3'))
Output:
False
True
False
True
True
False
Example #2:
m = HashMap(75, hash_function_2) keys = [i for i in range(1, 1000, 20)] for key in keys:
m.put(str(key), key * 42) print(m.size, m .capacity) result = True for key in keys:
# all inserted keys must be present result &= m .contains_key(str(key)) # NOT inserted keys must be absent result &= n ot m.contains_key(str(key + 1)) print(result)
Output:
50 75
True
get (self, key: str) -> object:
This method returns t he value associated with the given key. If the key is not in the hash map, the method returns None.
Example #1:
m = HashMap(30, hash_function_1) print(m.get('key')) m.put('key1', 1 0) print(m.get('key1'))
Output:
None
10
Example #2:
m = HashMap(150, h ash_function_2) for i in range(200, 300, 7): m.put(str(i), i * 10) print(m.size, m .capacity) for i in range(200, 300, 21):
print(i, m.get(str(i)), m.get(str(i)) == i * 10)
print(i + 1 , m.get(str(i + 1)), m.get(str(i + 1)) == (i + 1) * 10)
Output:
15 150
200 2000 True
201 None False
221 2210 True
222 None False
242 2420 True
243 None False
263 2630 True
264 None False
284 2840 True
285 None False
remove (self, key: str) -> None:
This method removes the given key and its a ssociated value from the hash map. If a given key is not in the hash m ap, the method does nothing (no exception needs to be raised).
Example #1:
m = HashMap(50, hash_function_1) print(m.get('key1')) m.put('key1', 1 0) print(m.get('key1')) m.remove('key1') print(m.get('key1')) m.remove('key4')
Output:
None
10
None
resize_table (self, new_capacity: int) -> None:
This method changes t he capacity of the internal hash table. All existing key / value pairs must remain in the new hash map and all hash table links must be rehashed. If new_capacity is less than 1, this method should do nothing.
Example #1:
m = HashMap(20, hash_function_1) m.put('key1', 1 0)
print(m.size, m .capacity, m.get('key1'), m.contains_key('key1')) m.resize_table(30)
print(m.size, m .capacity, m.get('key1'), m.contains_key('key1'))
Output:
1 20 10 True
1 30 10 True
Example #2:
m = HashMap(75, hash_function_2) keys = [i for i in range(1, 1000, 13)] for key in keys:
m.put(str(key), key * 42) print(m.size, m .capacity)
for capacity in range(111, 1000, 117): m.resize_table(capacity)
m.put('some key', 'some value') result = m.contains_key('some key') m.remove('some key') for key in keys:
result &= m.contains_key(str(key)) result &= not m.contains_key(str(key + 1))
print(capacity, result, m.size, m.capacity, round(m.table_load(), 2 ))
Output:
77 75
111 True 77 111 0.69
228 True 77 228 0.34
345 True 77 345 0.22
462 True 77 462 0.17
579 True 77 579 0.13
696 True 77 696 0.11
813 True 77 813 0.09
930 True 77 930 0.08
get_keys (self) -> DynamicArray:
This method returns a DynamicArray that contains all keys stored in your hash map. The order of the keys in the DA does not matter.
Example #1:
m = HashMap(10, hash_function_2) for i in range(100, 200, 10):
m.put(str(i), str(i * 10)) print(m.get_keys())
m.resize_table(1) print(m.get_keys())
m.put('200', '2000')
m.remove('100')
m.resize_table(2) print(m.get_keys())
Output:
['160', '110', '170', '120', '180', '130', '190', '140', '150', '100']
['100', '150', '140', '190', '130', '180', '120', '170', '110', '160'] ['200', '160', '110', '170', '120', '180', '130', '190', '140', '150']
Part 2 - Summary and Specific Instructions
1. Implement the MinHeap class by completing provided skeleton code i n the file min_heap.py . Once completed, your implementation will include the following methods:
add() get_min() remove_min() build_heap()
2. P rewritten DynamicArray class is provided for you in the skeleton code (file a5_include.py ). You should use objects of this class in your MinHeap class implementation for storing heap content.
3. Prewritten DynamicArray class may provide different f unctionality than that described in the lectures or implemented in prior homework assignments. Review docstrings in the skeleton code to understand available methods, their use, a nd input / output parameters.
4. The number of objects stored in the MinHeap will be between 0 and 1,000,000 inclusive.
5. RESTRICTIONS: You are NOT a llowed to use ANY built-in Python data structures and/or their methods.
You are NOT allowed to directly access any variables of the DynamicArray class. All work must be done only by using class methods.
6. Variables in the MinHeap class are not private. You ARE allowed to access and change their values directly. You do not need to write any getter or setter methods for the MinHeap class.
7. You may assume all methods of the provided DynamicArray class have O(1) runtime complexity.
add (self, node: object) -> None:
This method adds a new object to the MinHeap maintaining heap property.
Runtime complexity o f this implementation must be O(logN).
Example #1:
h = MinHeap() print(h, h.is_empty()) for value in range(300, 200, -15): h.add(value) print(h)
Output:
HEAP [] True
HEAP [300]
HEAP [285, 300]
HEAP [270, 300, 285]
HEAP [255, 270, 285, 300]
HEAP [240, 255, 285, 300, 270]
HEAP [225, 255, 240, 300, 270, 285]
HEAP [210, 255, 225, 300, 270, 285, 240]
Example #2: h = MinHeap(['fish', 'bird']) print(h) for value in ['monkey', 'zebra', 'elephant', 'horse', ' bear']: h.add(value) print(h)
Output:
HEAP ['bird', ' fish']
HEAP ['bird', ' fish', 'monkey']
HEAP ['bird', ' fish', 'monkey', 'zebra']
HEAP ['bird', ' elephant', 'monkey', 'zebra', 'fish']
HEAP ['bird', ' elephant', 'horse', 'zebra', 'fish', 'monkey']
HEAP ['bear', ' elephant', 'bird', 'zebra', 'fish', 'monkey', 'horse']
get_min (self) -> object:
This method returns a n object with a minimum key without r emoving it from the heap. If the heap is empty, the method r aises a MinHeapException.
Runtime complexity o f this implementation must be O(1).
Example #1: h = MinHeap(['fish', 'bird']) print(h)
print(h.get_min(), h.get_min())
Output:
HEAP ['bird', ' fish'] bird bird
remove_min (self) -> object:
This method returns a n object with a minimum key and removes it from the heap. If the heap is empty, the method raises a MinHeapException.
Runtime complexity o f this implementation must be O(logN).
Example #1:
h = MinHeap([1, 10, 2, 9, 3, 8, 4, 7, 5, 6]) while not h.is_empty(): print(h, end=' ') print(h.remove_min())
Output:
HEAP [1, 3, 2, 5, 6, 8, 4, 10, 7, 9] 1
HEAP [2, 3, 4, 5, 6, 8, 9, 10, 7] 2
HEAP [3, 5, 4, 7, 6, 8, 9, 10] 3
HEAP [4, 5, 8, 7, 6, 10, 9] 4
HEAP [5, 6, 8, 7, 9, 10] 5
HEAP [6, 7, 8, 10, 9] 6
HEAP [7, 9, 8, 10] 7
HEAP [8, 9, 10] 8
HEAP [9, 10] 9
HEAP [10] 10
build_heap (self, da: DynamicArray) -> None:
This method receives a dynamic array with objects in any order and builds a proper MinHeap from them. Current content of the MinHeap is lost.
Runtime complexity o f this implementation must be O(N). I f the runtime complexity is O(NlogN), you will not receive any points for this portion of the assignment, even if you pass Gradescope.
Example #1:
da = DynamicArray([100, 20, 6, 200, 90, 150, 300]) h = MinHeap(['zebra', 'apple']) print(h)
h.build_heap(da) print(h)
da.set_at_index(0, 500) print(da) print(h)
Output:
HEAP ['apple', 'zebra']
HEAP [6, 20, 100, 200, 90, 150, 300] [500, 20, 6, 200, 90, 150, 300]
HEAP [6, 20, 100, 200, 90, 150, 300]
