It is a minimum binary heap. The main goal is to implement a minimum binary using a p
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
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
'''
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 2 images
