class MinHeap: def __init__(self): #Filler for zeroth element to have the actual start of indexing to our min heap at arr[1] self.arr = [None]
USE PYTHON PROGRAMMING!!
Use only the code template below (fill in what is required)
Check images for specs, constrains, inputs and intended outputs.
Will give thumbs up if working properly.
Will give thumbs down if not working or did not use temp
class MinHeap:
def __init__(self):
#Filler for zeroth element to have the actual start of indexing to our min heap at arr[1]
self.arr = [None]
self.size = 0
# Part A.
# Fill in the ff. functions such that, given an array implementation arr
# of a complete tree and a node at arr[idx], the following functions
# correctly return the indices of the left child, right child, and parent
# of the given node. Assume that the root node is at arr[1] (NOT arr[0]).
def _left_child(self, idx):
return __________ # Fill in the blank.
def _right_child(self, idx):
return __________ # Fill in the blank.
def _parent(self, idx):
return __________ # Fill in the blank.
def _swap_nodes(self, i, j):
'''Helper function for swapping two nodes at indices i and j.'''
self.arr[i], self.arr[j] = self.arr[j], self.arr[i]
def _bubble_down(self, idx):
'''
Bubbles down a node at arr[idx] to preserve min-heap properties.
Specifically, a node needs to be moved down the heap if its value is
greater than either of its children's values. To ensure that the
least node is at the top of the heap, the current node is swapped
with the lesser of its two children.
'''
# Part B.
# This is a standard implementation of a bubble down
# Modify this accordingly to accomodate Constraint #3 which indicates
# that you need to order alphabetically regardless of character case.
left_idx = self._left_child(idx)
right_idx = self._right_child(idx)
if (left_idx > self.size):
return
elif (right_idx > self.size):
left_val = self.arr[left_idx]
if (left_val < self.arr[idx]):
self._swap_nodes(left_idx, idx)
else:
left_val = self.arr[left_idx]
right_val = self.arr[right_idx]
if (left_val < self.arr[idx] and left_val < right_val):
self._swap_nodes(left_idx, idx)
self._bubble_down(left_idx)
elif (right_val < self.arr[idx] and right_val < left_val):
self._swap_nodes(right_idx, idx)
self._bubble_down(right_idx)
def _bubble_up(self, idx):
'''
Bubbles up a node at arr[idx] to preserve min-heap properties.
Specifically, a node needs to be moved up the heap if its value is
less than its parent's.
'''
# Part C.
# This is a standard implementation of a bubble up algorithm for min heap.
# Modify this accordingly to accomodate Constraint #3 which indicates
# that you need to order alphabetically regardless of character case.
parent_idx = self._parent(idx)
parent_val = self.arr[parent_idx]
if (idx == 1):
return
if (self.arr[idx] < parent_val):
self._swap_nodes(parent_idx, idx)
if (parent_idx > 1):
self._bubble_up(parent_idx)
# Part C.
# Complete the following function to perform the following operations:
# - pop the top node from the min-heap
# (i.e. remove the node and return its value)
# - swap nodes in the heap to preserve the heap's order and shape
# - adjust the count for the number of nodes in the heap
def extract(self):
'''Removes the minimum element from the heap and returns its value.'''
# Extract the results by doing something here. Hint: swap nodes and pop the array
result = _________
self.size = __________ # No. of nodes after the top node is popped
if (__________): # If the heap still contains nodes...
# --- Do something here. ---
return result
# Part D.
# Complete the following function to perform the following operations:
# - insert a new node (with value val) into the heap
# - swap nodes in the heap to preserve the heap's order and shape
# - adjust the count for the number of nodes in the heap
def insert(self, val):
'''Inserts a new value into the heap.'''
idx = __________ # Index where the new value should be placed
self.arr.insert(idx, val)
self.size = __________ # No. of nodes after insertion
if (__________): # If the new node is not the root...
# --- Do something here. ---
# NOTE: The following statements in main check for the correctness of
# your implementation. Do not modify anything beyond this point!
if __name__ == '__main__':
n = int(input())
ls = list()
for i in range(n):
ls.append(input().rstrip())
myHeap = MinHeap()
for x in ls:
myHeap.insert(x)
while(myHeap.size != 0):
print(myHeap.extract())
![You are going to create a data structure composed of strings as individual elements. You are required to
implement a MinHeap class that uses an array representation. This implementation is done such that getting
the top element always results in alphabetical order.
A partially implemented data structure is already shown in the sample code below. The comparison of
elements should be done alphabetically.
You may refer to this article for a visualization of heaps represented as arrays:
https://www.geeksforgeeks.org/array-representation-of-binary-heap/
Input Format
The first line of input contains a single integer, n, the number of lines to follow.
The next n lines of input each contain a string m, to be inserted into the min heap from first (m;) to last (m).
Constraints
Osns 100
1s len(m) s 10
All strings are composed of alphabetical characters only. However, they can be lowercase, uppercase, or a
combination of both. This should not affect their ordering.
Output Format
Your code should produce n lines of output containing the contents of the min heap arranged in alphabetical
order.
Sample Input 0
7
Williard
Rangel
Marcus
Her lan
Ferdinand
Darvy
Dale
Sample Output 0
Dale
Darvy
Ferdinand
Her lan
Marcus
Rangel
Williard](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F50530471-3d1d-446c-af31-a941cdfd5635%2Fda2807fe-605f-4200-859c-d6716417c3a7%2F51al6h_processed.png&w=3840&q=75)
![](/static/compass_v2/shared-icons/check-mark.png)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
![Computer Networking: A Top-Down Approach (7th Edi…](https://www.bartleby.com/isbn_cover_images/9780133594140/9780133594140_smallCoverImage.gif)
![Computer Organization and Design MIPS Edition, Fi…](https://www.bartleby.com/isbn_cover_images/9780124077263/9780124077263_smallCoverImage.gif)
![Network+ Guide to Networks (MindTap Course List)](https://www.bartleby.com/isbn_cover_images/9781337569330/9781337569330_smallCoverImage.gif)
![Computer Networking: A Top-Down Approach (7th Edi…](https://www.bartleby.com/isbn_cover_images/9780133594140/9780133594140_smallCoverImage.gif)
![Computer Organization and Design MIPS Edition, Fi…](https://www.bartleby.com/isbn_cover_images/9780124077263/9780124077263_smallCoverImage.gif)
![Network+ Guide to Networks (MindTap Course List)](https://www.bartleby.com/isbn_cover_images/9781337569330/9781337569330_smallCoverImage.gif)
![Concepts of Database Management](https://www.bartleby.com/isbn_cover_images/9781337093422/9781337093422_smallCoverImage.gif)
![Prelude to Programming](https://www.bartleby.com/isbn_cover_images/9780133750423/9780133750423_smallCoverImage.jpg)
![Sc Business Data Communications and Networking, T…](https://www.bartleby.com/isbn_cover_images/9781119368830/9781119368830_smallCoverImage.gif)