Below is the min heap data structures. The minheap data type offers two methods: inserting an integer into the minheap, and deleting and returning the minimum value in the heap.

class MinHeap: def __init__(self): self.heap_list = [0] self.current_size = 0 def insert(self, k): assert(isinstance(k,int)) self.heap_list.append(k) self.current_size += 1 self.sift_up(self.current_size) def delete_min(self): if len(self.heap_list) == 1: return 'Empty heap' root = self.heap_list[1] self.heap_list[1] = self.heap_list[self.current_size] *self.heap_list, _ = self.heap_list self.current_size -= 1 self.sift_down(1) return root

def print_(self): return self.heap_list def sift_up(self, x): while x // 2 > 0: if self.heap_list[x] < self.heap_list[x // 2]: self.heap_list[x], self.heap_list[x // 2] = self.heap_list[x // 2], self.heap_list[x] x = x // 2

def sift_down(self, x): while (x * 2) <= self.current_size: a = self.min_child(x) if self.heap_list[x] > self.heap_list[a]: self.heap_list[x], self.heap_list[a] = self.heap_list[a], self.heap_list[x] x = a

def min_child(self, x): if (2 * x)+1 <= self.current_size: if self.heap_list[2*x] < self.heap_list[1 + (2*x)]: return 2 * x else: return 1 + (x * 2) elif 1 + (x * 2) > self.current_size: return 2 * x

Question: Implement a simple sorting algorithm that uses the minheap. This algorithm works simply by inserting all the values in the minheap, to then extract them one by one.

def heapSortFake(arr): assert(isinstance(arr,array.array)) pass