USE PYTHON PROGRAMMING!! TO MAKE IT EASIER, THERE'S A CODE TEMPLATE YOU CAN USE!! 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 algorithm for min heap. # 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())
USE PYTHON PROGRAMMING!!
TO MAKE IT EASIER, THERE'S A CODE TEMPLATE YOU CAN USE!!
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
USE THE CODE TEMPLATE TO MAKE IT EASIER!!
implement a MinHeap class that uses an array representation. This implementation is done such that getting
the top element always results in alphabetical order.
rclass MinHeap:
def init_(self):
#Filler for zeroth element to have the actual start of indexing to our mnin heap at arr[1]
self.arr = [None]
A partially implemented data structure is already shown in the sample code below. The comparison of
elements should be done alphabetically.
self.size = 0
: Part A.
Fill in the ff. functions such that, given an array implenentation ar
# 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]).
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
def left child(self, idx):
return ---- Fill 1n the blank.
def right_child(self, idx):
# Fill in
The first line of input contains a single integer, n, the number of lines to follow.
return
* Fill in the blank.
The next n lines of input each contain a string m, to be inserted into the min heap from first (m;) to last (m).
def parent (self, idx):
return
# Fill in the blank.
Constraints
def _swap_nodes(self, i, j):
'Helper function for swapping two nodes at indices i and j.'""
self.arr[1], self.arr[j] = self.arr[j], self.arr[1]
Osns 100
def _bubble_down(self, idx):
1s len(m) s 10
Bubbles down a node at arr[idx] to preserve min-heap properties.
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.
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
Output Format
with the lesser of its two children.
Your code should produce n lines of output containing the contents of the min heap arranged in alphabetical
order.
* Part B.
# This is a standard implementation of a bubble down algorithm for min heap.
* Modify this accordingly to accomodate Constraint #3 which indicates
* that you need to order alphabetically regardless of character case.
Sample Input 0
Sample Output 0
left_idx = self._left_child(idx)
right_idx = self._right_child(idx)
7
Dale
Williard
Darvy
if (left_idx > self.size):
return
Rangel
Ferdinand
Marcus
Herlan
Herlan
Ferdinand
elif (right_idx > self.size):
left_val = self.arr[left_idx]
Marcus
Rangel
Darvy
Dale
Williard
if (left_val < self.arr[idx]):
self. swap_nodes (left_idx, idx)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fef867b47-269c-4411-97a9-7125d900ede7%2F7d6db1d4-566c-41ee-84f4-b1a8bfde08b2%2Famj9upa_processed.png&w=3840&q=75)
![# 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
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. bubbledown (right_idx)
def insert(self, val):
'''Inserts a new value into the heap.''"
# Index where the new value should be placed
= xpL
self.arr.insert(idx, val)
def bubble_up(self, idx):
--------
Bubbles up a node at arr[idx] to preserve min-heap properties.
self.size =
# No. of nodes after insertion
Specifically, a node needs to be moved up the heap if its value is
less than its parent's.
if (--- -): # If the new node is not the root...
# --- Do something here. ---
* 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.
# NOTE: The following statements in main check for the correctness of
your implementation. Do not modify anything beyond this point!
== '_main_':
#3
--name_-
parent idx = self._parent (idx)
parent_val = self.arr[parent_idx]
n = int(input ())
ls = list()
if (idx == 1):
return
for i in range (n):
ls.append (input ().rstrip())
if (self.arr[idx] < parent_val):
self._swap_nodes (parent_idx, idx)
myHeap = MinHeap()
if (parent_idx > 1):
self. bubble_up(parent_idx)
for x in ls:
myHeap.insert(x)
Part C.
* Complete the following function to perform the following operations:
- pop the top node fron the min-heap
(1.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
while (myHeap.size != 0):
print(myHeap.extract())
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.
Comolete the followins function to perform the folloudng onerations:](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fef867b47-269c-4411-97a9-7125d900ede7%2F7d6db1d4-566c-41ee-84f4-b1a8bfde08b2%2F0jss85_processed.png&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
