It is a minimum binary heap. The main goal is to implement a minimum binary using a python list. Please help with the bold codes. All the not bold parts shouldn't be modified.
Only the bold parts should be modified.
I've said that no other methods should be added and no (pos) shouldn't be used. Please help me with not adding the other methods(def) to the code, it needs to work only by modifying the code provided above... I need to have an expected output just by having added the code below the sentence #YOUR CODE STARTS HERE. No other added methods(def).
Also, I haven't learned the (pos) function in python, so can you help me without using that function? Not allowed to use index() method as well.
getMin(self) needs to return the minimum value in the heap
_parent(self, index) it needs to return value of the parent of the element at the specific index
_leftChild(self, index) and _right Child(self,index) return value of the left/right child of the element at the specific index
insert(self, item) needs to insert an item into the heap while maintaining the minimum heap property. It must use the _parent method.
deleteMin(self) it needs to remove the minimum element of the heap and returns the value of the element that was just removed. The special cases where the heap is empty or contains only one element has been implemented for you already, your task is to implement the general case. According to the minimum heap property, the minimum element is the root node. When percolating down, if both children have the same value, swap with the left child. It must use the _leftChild and _rightChild methods.
heapSort(numList) It takes a list of numbers and uses the heap sort algorithm to return a list with the elements of numList sorted in ascending order. It does not modify the original list. Not allowed to use the sorted() method or the sort operator. It should use an instance of the MinBinaryHeap class to complete the sorting process.
Image is for input and output description.
Starter Code
class MinBinaryHeap:
def __init__(self):
self._heap=[]
def __str__(self):
return f'{self._heap}'
__repr__=__str__
def __len__(self):
return len(self._heap)
@property
def getMin(self):
# YOUR CODE STARTS HERE
pass
def _parent(self,index):
# YOUR CODE STARTS HERE
pass
def _leftChild(self,index):
# YOUR CODE STARTS HERE
pass
def _rightChild(self,index):
# YOUR CODE STARTS HERE
pass
def insert(self,item):
# YOUR CODE STARTS HERE
pass
def deleteMin(self):
# Remove from an empty heap or a heap of size 1
if len(self)==0:
return None
elif len(self)==1:
deleted=self._heap[0]
self._heap=[]
return deleted
else:
# YOUR CODE STARTS HERE
pass
def heapSort(numList):
'''
>>> heapSort([9,1,7,4,1,2,4,8,7,0,-1,0])
[-1, 0, 0, 1, 1, 2, 4, 4, 7, 7, 8, 9]
>>> heapSort([-15, 1, 0, -15, -15, 8 , 4, 3.1, 2, 5])
[-15, -15, -15, 0, 1, 2, 3.1, 4, 5, 8]
'''
# YOUR CODE STARTS HERE
The image is for a note.
Expected output
>>> h = MinBinaryHeap()
>>> h.insert(10)
>>> h.insert(5)
>>> h
[5, 10]
>>> h.insert(14)
>>> h._heap
[5, 10, 14]
>>> h.insert(9)
>>> h
[5, 9, 14, 10]
>>> h.insert(2)
>>> h
[2, 5, 14, 10, 9]
>>> h.insert(11)
>>> h
[2, 5, 11, 10, 9, 14]
>>> h.insert(14)
>>> h
[2, 5, 11, 10, 9, 14, 14]
>>> h.insert(20)
>>> h
[2, 5, 11, 10, 9, 14, 14, 20]
>>> h.insert(20)
>>> h
[2, 5, 11, 10, 9, 14, 14, 20, 20]
>>> h.getMin
2
>>> h._leftChild(1)
5
>>> h._rightChild(1)
11
>>> h._parent(1)
>>> h._parent(6)
11
>>> h._leftChild(6)
>>> h._rightChild(9)
>>> h.deleteMin()
2
>>> h._heap
[5, 9, 11, 10, 20, 14, 14, 20]
>>> h.deleteMin()
5
>>> h
[9, 10, 11, 20, 20, 14, 14]
>>> len(h)
7
>>> h.getMin
9
'''
Extracted text: deleteMin(self) Removes the minimum element of the heap and returns the value of the element that was just removed. The special cases where the heap is empty or contains only one element has been implemented for you already, your task is to implement the general case. As a reminder, according to the minimum heap property, the minimum element is the root node. When percolating down, if both children have the same value, swap with the left child. It must use the _leftChild and _rightChild methods, so make sure to test them before using them in this method Output int or float The minimum value of the heap before deletion heapSort(numList) Takes a list of numbers and uses the heap sort algorithm to return a list with the elements of numList sorted in ascending order. It does not modify the original list. Input list numList A sequence of numerical values. You cannot make assumptions about its size Output list Values of numList sorted in ascending order using the heap sort algorithm
Extracted text: _parent(self, index) Returns the value of the parent of the element at the specified index. Please see the above note about heap and list indices. Input index The heap index to find a child of int Output int or float Value of that element’s parent None None is returned if that element does not have the specified child _leftChild(self, index) and _rightChild(self, index) Returns the value of the left/right child of the element at the specified index. Please see the above note about heap and list indices. Input index The heap index to find a child of int Output Value of that element's left/right child None is returned if that element does not have the specified child int or float None getMin(self) A property method that returns the minimum value in the heap. You are not allowed to use the min method. Output int or float The minimum value in the heap None None is returned if the heap is empty insert(self, item) Inserts an item into the heap while maintaining the minimum heap property. It must use the _parent(self, index) method, so make sure to test it before using it in this method. Input int or float item | The value to add to the heap