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.
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();
}
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.
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
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.