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.
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static SortedSet sortedSet = new SortedSet();
static void Main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
int Q = int.Parse(Console.ReadLine().TrimEnd());
for (int i = 1; i <= Q; i++) {
string[] arr = Console.ReadLine().Split(' ');
switch(arr[0]){
case "1":
sortedSet.Add(int.Parse(arr[1]));
break;
case "2":
sortedSet.Remove(int.Parse(arr[1]));
break;
case "3":
textWriter.WriteLine(sortedSet.Min);
break;
}
}
textWriter.Flush();
textWriter.Close();
}
Simple algorithm. The idea is just to store the deleted values in a set or dict. And then when it comes to print the minimum, check if the current heap minimum has been deleted or not. If it has, deleted it from the heap and from the deleted set. If not, then, that's the min.
C++ with a real heap. Using something like std::set instead works, but it's possible with a heap and STL. The problem is designed for learning about heaps, so IMHO using a heap is better than using a set.
The trick is that for delete, you can optimize how you re-heapify the heap after finding and deleting the element. If the new element at the index you deleted is less than the old element, you only need to re-heapify the first half. If it's greater, you only need to re-heapify the second half. https://en.wikipedia.org/wiki/Binary_heap#Delete
Using the "raw" algorithms std::make_heap, std::push_heap, std::pop_heap, etc., rather than std::priority_queue, let you express these optimizations. std::priority_queue doesn't give you enough interface to do them, and also doesn't do them for you.
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])
C# code using SortedSet
using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static SortedSet sortedSet = new SortedSet();
}
c# using sortedlist
Simple algorithm. The idea is just to store the deleted values in a set or dict. And then when it comes to print the minimum, check if the current heap minimum has been deleted or not. If it has, deleted it from the heap and from the deleted set. If not, then, that's the min.
C++ with a real heap. Using something like std::set instead works, but it's possible with a heap and STL. The problem is designed for learning about heaps, so IMHO using a heap is better than using a set.
The trick is that for delete, you can optimize how you re-heapify the heap after finding and deleting the element. If the new element at the index you deleted is less than the old element, you only need to re-heapify the first half. If it's greater, you only need to re-heapify the second half. https://en.wikipedia.org/wiki/Binary_heap#Delete
Using the "raw" algorithms std::make_heap, std::push_heap, std::pop_heap, etc., rather than std::priority_queue, let you express these optimizations. std::priority_queue doesn't give you enough interface to do them, and also doesn't do them for you.
This implementation passes all the tests.