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.
classMinHeap:def__init__(self):self.heap=[]defadd(self,v):self.heap.append(v)self.__sift_up__(len(self.heap)-1)defdelete(self,v):h=self.heapifh:try:idx=self.heap.index(v)h[idx],h[-1]=h[-1],h[idx]h.pop()ifidx<len(h):self.__sift_down__(idx)self.__sift_up__(idx)exceptValueError:...defprint_min(self):ifself.heap:print(self.heap[0])def__sift_up__(self,idx):# compare and swap with parent upwards repeatedly: (idx-1)//2h=self.heapitem=h[idx]whileidx>0:parent_idx=(idx-1)//2ifitem<h[parent_idx]:h[idx]=h[parent_idx]idx=parent_idxelse:breakh[idx]=itemdef__sift_down__(self,idx):# compare and swap with children downwards repeatedly:h=self.heapsize=len(h)item=h[idx]whileTrue:l_idx,r_idx,min_idx=2*idx+1,2*idx+2,idxifl_idx<sizeandh[l_idx]<item:min_idx=l_idxifr_idx<sizeandh[r_idx]<h[min_idx]:min_idx=r_idxifmin_idx!=idx:h[idx]=h[min_idx]idx=min_idxelse:breakh[idx]=item# Initialize the min-heapminHeap=MinHeap()# Number of operationsnum_of_queries=int(input())# Execute operationsfor_inrange(num_of_queries):op=input().split()op_code=op[0]ifop_code=='1':minHeap.add(int(op[1]))elifop_code=='2':minHeap.delete(int(op[1]))elifop_code=='3':minHeap.print_min()
When you delete the root, you replace it with the last element, then perform heapifyDown, if the new Root is greater than either children.
But when you have to delete any arbitrary element, after replacing it with the last element, dont you need to take care of both the conditions below?
1) Heapify up - If the element is less than the parent
2) Heapify Down - If the element is greater than either children.
But the editorial only does a Heapify Down operation during deletion?
For instance, consider the tree :- 10, 20, 16, 40, 50, 18, 17, 80, 85, 55, 56, 19. If you want to delete node 40, you replace it with the last element i.e. 19. Now a heapify down operation wont
restore the heap property. You will need to do a heapify up operation and this is not covered in the Editorial code. Wanted to check if my understanding is correct.
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();
}
When you delete the root, you replace it with the last element, then perform heapifyDown, if the new Root is greater than either children.
But when you have to delete any arbitrary element, after replacing it with the last element, dont you need to take care of both the conditions below? 1) Heapify up - If the element is less than the parent 2) Heapify Down - If the element is greater than either children.
But the editorial only does a Heapify Down operation during deletion?
For instance, consider the tree :- 10, 20, 16, 40, 50, 18, 17, 80, 85, 55, 56, 19. If you want to delete node 40, you replace it with the last element i.e. 19. Now a heapify down operation wont restore the heap property. You will need to do a heapify up operation and this is not covered in the Editorial code. Wanted to check if my understanding is correct.
My Java solution
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