We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
value_index={};# Map to maintain the index of values in the heap.heap=[0]*500002heap_size=0definsert_val(val):globalheapglobalheap_sizeif(heap_size==0):heap[heap_size+1]=val;heap_size+=1value_index[val]=heap_size;return;heap[heap_size+1]=val# expands the heap by oneheap_size+=1value_index[val]=heap_size;temp=heap_size;while(temp>1):if(heap[temp]<heap[temp//2]):value_index[heap[temp]]=temp//2;# exchange value of index with parentvalue_index[heap[temp//2]]=temp;temp2=heap[temp];heap[temp]=heap[temp//2];# same thing but with heapheap[temp//2]=temp2;temp=temp//2;# proceed with parent nodeelse:breakdefdelete_val(val):globalheapglobalheap_sizeindex=value_index[val]value_index[val]=0value_index[heap[heap_size]]=index;# set the value index of the last item equal to the index of the removed valueheap[index]=heap[heap_size]# insert the second to largest value in the heap to the position of the removed itemheap_size-=1while(True):# move down the tree from the removed itemleft_child=2*indexright_child=2*index+1if(left_child<=heap_size):if(right_child<=heap_size):if(heap[index]>heap[left_child]orheap[index]>heap[right_child]):swap_index=left_childif(heap[left_child]<heap[right_child])elseright_childvalue_index[heap[swap_index]]=index# swap lowest value up to root node with the root node having the index "index"value_index[heap[index]]=swap_indextemp2=heap[index]heap[index]=heap[swap_index]# same for actual heapheap[swap_index]=temp2index=swap_index# move down to the next subtree that was altered else:breakelse:# right child > heap_size (there is no right child)if(heap[index]>heap[left_child]):value_index[heap[left_child]]=index# exchange left child index value with parentvalue_index[heap[index]]=left_childtemp2=heap[index]heap[index]=heap[left_child]# same with values in heapheap[left_child]=temp2index=left_child# proceed with left child treeelse:breakelse:breakq=int(input())foriinrange(q):query=input().split()q=query[0]iflen(query)==2:elem=int(query[1])# print(elem)ifq=='1':insert_val(elem)elifq=='2':delete_val(elem)elifq=='3':print(heap[1])
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
QHEAP1
You are viewing a single comment's thread. Return to all comments →