- We Saw How Min Heaps Can Efficiently Allow Us To Query The Least Element In A Heap Array We Would Like To Modify Minh 1 (174.43 KiB) Viewed 61 times
class MinHeap: def __init__(self): self.H = [None] def size(self): return len(self.H)-1 def __repr__(self): return str(self.H[1:]) def satisfies_assertions(self): for i in range(2, len(self.H)): assert self.H >=self.H[i//2], f'Min heap property fails at position {i//2},parent elt: {self.H[i//2]}, child elt: {self.H}' def min_element(self): return self.H[1]
## bubble_up function at index ## WARNING: this function has been cut and paste forthe next problem as well def bubble_up(self, index): assert index >= 1 if index == 1: return parent_index = index // 2 if self.H[parent_index] <self.H[index]: return else: self.H[parent_index],self.H[index] = self.H[index], self.H[parent_index] self.bubble_up(parent_index) ## bubble_down function at index ## WARNING: this function has been cut and paste forthe next problem as well def bubble_down(self, index): assert index >= 1 and index <len(self.H) lchild_index = 2 * index rchild_index = 2 * index + 1 # set up the value of left child to theelement at that index if valid, or else make it +Infinity lchild_value = self.H[lchild_index] iflchild_index < len(self.H) else float('inf') # set up the value of right child tothe element at that index if valid, or else make it +Infinity rchild_value = self.H[rchild_index] ifrchild_index < len(self.H) else float('inf') # If the value at the index is lessthanor equal to the minimum of two children, then nothing else todo if self.H[index] <=min(lchild_value, rchild_value): return # Otherwise, find the index and valueof the smaller of the two children. # A useful python trick is tocompare min_child_value, min_child_index = min((lchild_value, lchild_index), (rchild_value, rchild_index)) # Swap the current index with the leastof its two children self.H[index], self.H[min_child_index]= self.H[min_child_index], self.H[index] # Bubble down on the minimum childindex self.bubble_down(min_child_index) # Function: heap_insert # Insert elt into heap # Use bubble_up/bubble_down function def insert(self, elt): # your code here # Function: heap_delete_min # delete the smallest element in the heap. Usebubble_up/bubble_down def delete_min(self): # your code here
class TopKHeap: # The constructor of the class to initialize an emptydata structure def __init__(self, k): self.k = k self.A = [] self.H = MinHeap() def size(self): return len(self.A) +(self.H.size()) def get_jth_element(self, j): assert 0 <= j < self.k-1 assert j < self.size() return self.A[j] def satisfies_assertions(self): # is self.A sorted for i in range(len(self.A) -1 ): assert self.A <=self.A[i+1], f'Array A fails to be sorted at position {i},{self.A, self.A[i+1]}' # is self.H a heap (check min-heapproperty) self.H.satisfies_assertions() # is every element of self.A less thanor equal to each element of self.H for i in range(len(self.A)): assert self.A <=self.H.min_element(), f'Array element A[{i}] = {self.A} islarger than min heap element {self.H.min_element()}' # Function : insert_into_A # This is a helper function that inserts an element`elt` into `self.A`. # whenever size is < k, # append elt to the end of thearray A # Move the element that you just added at the veryend of # array A out into its proper place so that the arrayA is sorted. # return the "displaced last element" jHat (None ifno element was displaced) def insert_into_A(self, elt): print("k = ", self.k) assert(self.size() < self.k) self.A.append(elt) j = len(self.A)-1 while (j >= 1 and self.A[j] <self.A[j-1]): # Swap A[j] andA[j-1] (self.A[j], self.A[j-1])= (self.A[j-1], self.A[j]) j = j -1 return # Function: insert -- insert an element into the datastructure. # Code to handle when self.size < self.k isalready provided def insert(self, elt): size = self.size() # If we have fewer than k elements,handle that in a special manner if size <= self.k: self.insert_into_A(elt) return # Code up your algorithm here. # your code here # Function: Delete top k -- delete an element fromthe array A # In particular delete the j^{th} element where j = 0means the least element. # j must be in range 0 to self.k-1 def delete_top_k(self, j): k = self.k assert self.size() > k # we need nothandle the case when size is less than or equal to k assert j >= 0 assert j < self.k # your code here
h = TopKHeap(5)# Force the array Ah.A = [-10, -9, -8, -4, 0]# Force the heap to this heap[h.H.insert(elt) for elt in [1, 4, 5, 6, 15, 22, 31, 7]]
print('Initial data structure: ')print('\t A = ', h.A)print('\t H = ', h.H)
# Insert an element -2print('Test 1: Inserting element -2')h.insert(-2)print('\t A = ', h.A)print('\t H = ', h.H)# After insertion h.A should be [-10, -9, -8, -4, -2]# After insertion h.H should be [None, 0, 1, 5, 4, 15, 22, 31, 7,6]assert h.A == [-10,-9,-8,-4,-2]assert h.H.min_element() == 0 , 'Minimum element of the heap is nolonger 0'h.satisfies_assertions()
print('Test2: Inserting element -11')h.insert(-11)print('\t A = ', h.A)print('\t H = ', h.H)assert h.A == [-11, -10, -9, -8, -4]assert h.H.min_element() == -2h.satisfies_assertions()
print('Test 3 delete_top_k(3)')h.delete_top_k(3)print('\t A = ', h.A)print('\t H = ', h.H)h.satisfies_assertions()assert h.A == [-11,-10,-9,-4,-2]assert h.H.min_element() == 0h.satisfies_assertions()
print('Test 4 delete_top_k(4)')h.delete_top_k(4)print('\t A = ', h.A)print('\t H = ', h.H)assert h.A == [-11, -10, -9, -4, 0]h.satisfies_assertions()
print('Test 5 delete_top_k(0)')h.delete_top_k(0)print('\t A = ', h.A)print('\t H = ', h.H)assert h.A == [-10, -9, -4, 0, 1]h.satisfies_assertions()
print('Test 6 delete_top_k(1)')h.delete_top_k(1)print('\t A = ', h.A)print('\t H = ', h.H)assert h.A == [-10, -4, 0, 1, 4]h.satisfies_assertions()print('All tests passed - 15 points!')
We saw how min-heaps can efficiently allow us to query the least element in a heap (array). We would like to modify minheaps in this exercise to design a data structure to maintain the least k elements for a given k ≥ 1 with being the minheap data-structure. Our design is to hold two arrays: • (a) a sorted array A of k elements that forms our least k elements; and • (b) a minheap H with the remaining n - k elements. Our data structure will itself be a pair of arrays (A,H) with the following property: H must be a minheap • A must be sorted of size k. • Every element of A must be smaller than every element of H. The key operations to implement in this assignment include: • insert a new element into the data-structure • delete an existing element from the data-structure. We will first ask you to design the data structure and them implement it. k = 1 (A) Design Insertion Algorithm Suppose we wish to insert a new element with key j into this data structure. Describe the pseudocode. Your pseudocode must deal with two cases: when the inserted element j would be one of the least k elements i.e, it belongs to the array A; or when the inserted element belongs to the heap H. How would you distinguish between the two cases? • You can assume that heap operations such as insert (H, key) and delete (H, index) are defined. • Assume that the heap is indexed as H[1]... H[n -k] with H[0] being unused. • Assume n > k, i.e, there are already more than k elements in the data structure. What is the complexity of the insertion operation in the worst case in terms of k, n. Unfortunately, we cannot grade your answer. We hope you will use this to design your datastructure on paper before attempting to code it up YOUR ANSWER HERE (B) Design Deletion Algorithm Suppose we wish to delete an index j from the top-k array A. Design an algorithm to perform this deletion. Assume that the heap is not empty, in which case you can assume that the deletion fails. • You can assume that heap operations such as insert (H, key) and delete (H, index) are defined. • Assume that the heap is indexed as H[1]... H[n -k] with H[0] being unused. • Assume n > k, i.e, there are already more than k elements in the data structure. What is the complexity of the insertion operation in the worst case in terms of k, n. Unfortunately, we cannot grade your answer. We hope you will use this to design your datastructure on paper before attempting to code it up YOUR ANSWER HERE (C) Program your solution by completing the code below Note that although your algorithm design above assume that your are inserting and deleting from cases where n > k, the data structure implementation below must handle n <k as well. We have provided implementations for that portion to help you out.