'''
PROJECT 6 - Heaps
Name:
PID:
'''
class Node:
"""
Class definition shouldn't be modified in anyway
"""
__slots__ = ('_key', '_val')
def __init__(self, key, val):
self._key = key
self._val = val
def __lt__(self, other):
return self._key < other._key or (self._key == other._key and self._val < other._val)
def __gt__(self, other):
return self._key > other._key or (self._key == other._key and self._val > other._val)
def __eq__(self, other):
return self._key == other._key and self._val == other._val
def __str__(self):
return '(k: {0} v: {1})'.format(self._key, self._val)
__repr__ = __str__
@property
def val(self):
"""
:return: underlying value of node
"""
return self._val
class Heap:
"""
Class definition is partially completed.
Method signatures and provided methods may not be edited in any way.
"""
__slots__ = ('_size', '_capacity', '_data')
def __init__(self, capacity):
self._size = 0
self._capacity = capacity + 1 # additional element space for push
self._data = [None for _ in range(self._capacity)]
def __str__(self):
return ', '.join(str(el) for el in self._data if el is not None)
__repr__ = __str__
def __len__(self): # allows for use of len(my_heap_object)
return self._size
# DO NOT MODIFY ANYTHING ABOVE THIS LINE
# Start of Student Modifications
def _percolate_up(self):
"""
When an element initially exists in the last spot of the
underlying data list, percolate it up to its valid spot
in the heap representation.
Time Complexity: O(log(N))
Space Complexity: O(1)
:return: type None
"""
pass
def _percolate_down(self):
"""
When an element initially exists in the first spot of the
underlying data list, percolate it down to its valid
spot in the heap representation.
Time Complexity: O(log(N))
Space Complexity: O(1)
:return: type None
"""
pass
def _min_child(self, i):
"""
Given an index of a node, return the index of the smaller child.
In the event that the index is a leaf, return -1.
Time Complexity: O(1)
Space Complexity: O(1)
:param i:
:return: type int
"""
pass
def push(self, key, val):
"""
Use the key and value parameters to add a Node to the heap.
In the event that pushing will exceed the limit, you must pop
the smallest element out after pushing in the new element.
Time Complexity: O(log(N))
Space Complexity: O(1)
:param key:
:param val:
:return: type None
"""
pass
def pop(self):
"""
Removes the smallest element from the heap.
Time Complexity: O(log(N))
Space Complexity: O(1)
:return: type same as Node.val
if no elements exist, return None
"""
pass
@property # do not remove
def empty(self):
"""
Checks if the heap is empty.
Time Complexity: O(1)
Space Complexity: O(1)
:return: type Bool
"""
pass
@property # do not remove
def top(self):
"""
Gives the root value.
Time Complexity: O(1)
Space Complexity: O(1)
:return: type same as Node.val
if no root value exists, return None
"""
pass
@property # do not remove
def levels(self):
"""
Returns all Node values on a single level into a list
i.e. All node values in the first level go in list at index 0,
All node values in the second level, go in list at index 1,
and so on and so forth.
If there are no nodes, return a single empty list
Time complexity: O(N)
Space complexity: O(N)
You may use any list methods in this function
:return: type List[List[Node.val]]
"""
pass
def most_x_common(vals, X):
"""
Given a list of elements, return the X most commonly occurring
elements.
Example: most_x_common(['a', 'a', 'a', 'b', 'b', 'c'], 2)
== {'a','b'}
Time Complexity: O(Nlog(x))
N is len(vals)
You are guaranteed that x is always <= N
Space Complexity: O(N)
Using any kind of sorting algorithm will result in a zero,
including built in sort.
In the case of ties (i.e. some elements occur the same amount of times)
Pick the greater element, lexicographically
Must use your heap class.
No processing/validating should or needs to be done on the string,
such as striping for whitespace, etc.
It is allowed (and encouraged) to use a dictionary to achieve
the optimal run time.
:param vals: type List[string]
:param X: type int
:return: type Set[string]
"""
pass