I've been trying to solve this question. The problem statement is bit of a customized heap binary tree if you compare it with ADT definition of heap binary tree. In Heap binary tree you always do deleteMax/deletetMin depending upon the kind of heap tree it is but here they want you to delete a specific node instead in this problem.
Well my solution is failing only one test case which is happening when I delete a value which is a leaf node:
Here is the effort I've made so far while writing the Heap class. Although the source code is big but you might want to focus on the DeleteSpecificValueFromHeap method where I'm facing the problem.
I've implemented the heap binary tree using an array (List in C# are backed by arrays). Consider the current state of a heap binary tree in the array:
-1 12 5 13 20 6 7
The heap binary tree looks something like this:
-1
/ \
12 5
/ \ / \
13 20 6 7
Now I want to delete node with value 13. This case fails in my heap binary tree. Can you point out on how to fix it? DeleteSpecificValueFromHeap method is the one which is struggling currently.
public class Heap
{
List<int> items;
public int Root
{
get { return items[0]; }
}
public Heap()
{
items = new List<int>();
}
public void Insert(int item)
{
items.Add(item);
if (items.Count <= 1)
return;
var i = items.Count - 1;
while (i > 0)
{
var parentNodeValue = items[(i - 1) / 2];
var newNodeValue = items[i];
if (newNodeValue < parentNodeValue)
{
//we need to percolate up this node. so swap it with parent.
items[(i - 1) / 2] = newNodeValue;
items[i] = parentNodeValue;
//update the position of newly inserted node after swapping
i = (i - 1) / 2;
}
else
break;
}
}
public void DeleteSpecificValueFromHeap(int val)
{
for (var i = 0; i < items.Count; i++)
{
if (items[i] == val)
{
items[i] = items[items.Count - 1];
items.RemoveAt(items.Count - 1);
//reheapify : percolate down this node ith position
var leftChildIndex = (i * 2) + 1;
var rightChildIndex = (i * 2) + 2;
while (leftChildIndex <= items.Count - 1) //chilren are there in the array.
{
//child nodes of node at ith position
var child1Value = items[leftChildIndex];
if (rightChildIndex <= items.Count - 1)
{
var child2Value = items[rightChildIndex];
var currentNodeValue = items[i];
if (child1Value < child2Value)
{
//swap ith node with child 1
items[i] = child1Value;
items[leftChildIndex] = currentNodeValue;
i = leftChildIndex;
}
else
{
items[i] = child2Value;
items[rightChildIndex] = currentNodeValue;
i = rightChildIndex;
}
}
else
{
//case of only one child
var currentNodeValue = items[i];
items[i] = child1Value;
items[leftChildIndex] = currentNodeValue;
i = leftChildIndex;
}
leftChildIndex = (i * 2) + 1;
rightChildIndex = (i * 2) + 2;
}
break;
}
}
}
Update:
I changed my DeleteSpecificValueFromHeap method as below as per @Raudel's recommendation after which the test case I've mentioned in the post is ok now but test case # 9 on the link is still failing. I'm really sorry for not being able to provide the input cases as it has .1 million inputs which will not be possible to put here. I need an eagle eye now who can dry run my code and help me if there is still anything wrong?
public void DeleteSpecificValueFromHeap(int val)
{
for (var i = 0; i < items.Count; i++)
{
if (items[i] == val)
{
items[i] = items[items.Count - 1];
if (i == items.Count - 1)
{
//you are deleting the right most leaf node at the lowest level
//so nothing needs to be done apart from deleting the node.
items.RemoveAt(items.Count - 1);
break;
}
items.RemoveAt(items.Count - 1);
if (i == 0)
//it is the root node. The only option is to percolate down.
PercolateDownTheNode(i);
else
{
var parentNodeValue = items[(i - 1) / 2];
if (items[i] < parentNodeValue)
PercolateUpTheNode(i);
else
PercolateDownTheNode(i);
}
break;
}
}
}
private void PercolateDownTheNode(int i)
{
//reheapify : percolate down this node ith position
var leftChildIndex = (i * 2) + 1;
var rightChildIndex = (i * 2) + 2;
while (leftChildIndex <= items.Count - 1) //chilren are there in the array.
{
//child nodes of node at ith position
var child1Value = items[leftChildIndex];
if (rightChildIndex <= items.Count - 1)
{
var child2Value = items[rightChildIndex];
var currentNodeValue = items[i];
if (child1Value < child2Value)
{
//swap ith node with child 1
items[i] = child1Value;
items[leftChildIndex] = currentNodeValue;
i = leftChildIndex;
}
else
{
items[i] = child2Value;
items[rightChildIndex] = currentNodeValue;
i = rightChildIndex;
}
}
else
{
//case of only one child
var currentNodeValue = items[i];
items[i] = child1Value;
items[leftChildIndex] = currentNodeValue;
i = leftChildIndex;
}
leftChildIndex = (i * 2) + 1;
rightChildIndex = (i * 2) + 2;
}
}
private void PercolateUpTheNode(int i)
{
while (i > 0)
{
var parentNodeValue = items[(i - 1) / 2];
var newNodeValue = items[i];
if (newNodeValue < parentNodeValue)
{
//we need to percolate up this node. so swap it with parent.
items[(i - 1) / 2] = newNodeValue;
items[i] = parentNodeValue;
//update the position of newly inserted node after swapping
i = (i - 1) / 2;
}
else
break;
}
}
The problem is that when you remove at any position but the last one, all the elements to the right are shifted left by one position and this may end up in the heap to stop being a heap. From the 3 steps down below you are doing the first two but you are not doing the 3rd one properly.
1, Delete the value from the array but do not remove it (this creates a "hole" and the tree is no longer "complete")
2. Replace the deleted value with the "fartest right node" on the lowest level of the heap.
//you can see the first two steps like a swap
3. Heapify (fix the heap)://but you have two possible cases now
if ( newValue < its parent node )
Do an UPHeap
else
Do a DownHeap
In the 3rd step, you compare with the parent and this tells you what to do, either go UP or DOWN. For this, I recommend you to create methods for UpHeap and DownHeap separately because you will be using them more than once and the code will become more clear.
I should also point out that you are finding the value with a loop and this makes each deletion O(n). As you can see in the problem statement they can ask you up to 1e5 question. That will probably give you Time Limit Exceeded (TLE) depending on the size of the array. As a thumb rule, for almost any online judge, the expected time to solve a problem is around 1 sec. So, for an array with size 1e5 you will have to wait longer than that which makes you think there should be something better, which it's true.
The thing is that you can keep track of the position inside the heap a value has. You can save it in a HashTable<int, int> (for example) so you can ask for a given value to get the position inside the heap. In this way you avoid the loop to get the position inside the heap, but you have to update it any time you move that value within the heap. In order to update it, you have to add a couple of lines inside both UpHeap and DownHeap methods, and every time you move a value UP/DOWN the heap you update the positions of the swapped elements in the HashTable.
UPDATE
I took your code and change a couple of things, then I went online and accepted the problem, now you can be sure this works. I think the error was in the DownHeap method, that's the only method I really changed.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ContestLibrary
{
public class Heap
{
List<int> items;
public int Root
{
get { return items[0]; }
}
public Heap()
{
items = new List<int>();
}
public int GetMin()
{
if(items.Count == 0)
throw new Exception("Empty Heap");
return items[0];
}
public void Insert(int item)
{
items.Add(item);
PercolateUpTheNode(items.Count - 1);
}
public void DeleteSpecificValueFromHeap(int val)
{
for (var i = 0; i < items.Count; i++)
{
if (items[i] == val)
{
items[i] = items[items.Count - 1];
items.RemoveAt(items.Count - 1);
if (i == items.Count)
return;//cause you deleted the right most node
var parentNodeValue = items[(i - 1) / 2];
if (items[i] < parentNodeValue)
PercolateUpTheNode(i);
else
PercolateDownTheNode(i);
return;
}
}
}
private void PercolateDownTheNode(int i)
{
while (i < items.Count / 2) {
//get the min child first
int minChildIndex = 2 * i + 1;
if (minChildIndex < items.Count - 1 && items[minChildIndex] > items[minChildIndex + 1]) {
minChildIndex++;
}
if (items[i] <= items[minChildIndex])
return;//I'm smaller than the minimum of my children
//swap
int temp = items[i];
items[i] = items[minChildIndex];
items[minChildIndex] = temp;
i = minChildIndex;
}
}
private int ParentIndex(int i)
{
return (i - 1) / 2;
}
private void PercolateUpTheNode(int i)
{
while (i > 0)
{
var parentValue = items[ParentIndex(i)];
var currentValue = items[i];
if (currentValue < parentValue)//swap
{
items[ParentIndex(i)] = currentValue;
items[i] = parentValue;
i = ParentIndex(i);
}
else
return;
}
}
}
public class Problem
{
static void Main(string[] args)
{
Heap heap = new Heap();
int q = int.Parse(Console.ReadLine());
while (q-->0)
{
var line = Console.ReadLine().Split();
int type = int.Parse(line[0]);
switch (type)
{
case 1:
heap.Insert(int.Parse(line[1]));
break;
case 2:
heap.DeleteSpecificValueFromHeap(int.Parse(line[1]));
break;
default:
Console.WriteLine(heap.GetMin());
break;
}
}
}
}
}