replace_in_heap.cs

using System;
					
public class Program
{
	public class Heap
	{
		int[] heap;
		int elements;

		public void Swap(ref int a, ref int b)
		{
			int temp = b;
			b = a;
			a = temp;
		}
		
		public void Insert(int val)
		{
			heap[elements] = val;
			
			int i=elements;
			while (heap[(i-1)/2] < heap[i])
			{
				Swap(ref heap[(i-1)/2], ref heap[i]);
				i = (i-1) /2;
			}
						
			elements++;
		}
		
		public void DeleteRoot()
		{
			int i = 0;
			Swap(ref heap[i], ref heap[elements-1]);
			elements--;
			
			while (2*i + 2 < elements)
			{
				int leftChild = 2*i + 1;
				int rightChild = 2*i + 2;
				
				if (heap[leftChild] > heap[rightChild])
				{
					Swap(ref heap[i], ref heap[leftChild]);	
					i = leftChild;
				} 
				else
				{
					Swap(ref heap[i], ref heap[rightChild]);
					i = rightChild;
				}
			}
		}
		
		public int Replace(int newElement) {
			int oldMax = heap[0];
			
			heap[0] = newElement;

			int i = 0;

			while (true) {
				int leftChild = 2 * i + 1;
				int rightChild = 2 * i + 2;
				
				if (leftChild >= elements && rightChild >= elements) {
					break;
				}

				if (leftChild >= elements && rightChild < elements && heap[rightChild] > heap[i]) {
					Swap(ref heap[i], ref heap[rightChild]);
					i = rightChild;
				} else if (rightChild >= elements && leftChild < elements && heap[leftChild] > heap[i]) {
					Swap(ref heap[i], ref heap[leftChild]);
					i = leftChild;
				} else if (heap[leftChild] > heap[i] && rightChild < elements && heap[leftChild] >= heap[rightChild]) {
					Swap(ref heap[i], ref heap[leftChild]);
					i = leftChild;
				} else if (heap[rightChild] > heap[i] && leftChild < elements && heap[rightChild] >= heap[leftChild]) {
					Swap(ref heap[i], ref heap[rightChild]);
					i = rightChild;
				} else {
					break;
				}
			}
			
			return oldMax;
		}
		
		public int GetMax() {
			return heap[0];
		}
		
		public void Display()
		{
			int levels = (int)Math.Log(elements, 2);
			int currentLevel = 0;
			
			int j=1;
			for (int i=0;i<elements;i++)
			{
				if (i == j)
				{
					j=j*2+1;
					Console.WriteLine();
					currentLevel++;
				}			

				Console.Write("{0, -5}", heap[i]);
			}
		}
		
		public Heap(int size)
		{
			heap = new int[size];
			elements = 0;
		}
	}
	
	public static void Main()
	{
		var x = new Random();
		int size = x.Next(10)+1;
		var h = new Heap(size);

		for (int i=0;i<size;i++)
		{
			h.Insert(x.Next(50)+1);
		} 
		int newElement = x.Next(20);
		h.Replace(newElement);
		h.Display();
	}
}