You are viewing a single comment's thread. Return to all comments →
I developed a min and max heap but I got timeout. What am I doing wrong ?
using System; using System.Collections.Generic; using System.Linq; using System.Text;
class Solution { static void Main(string[] args) { int n = Convert.ToInt32(Console.ReadLine()); int[] a = new int[n]; minHeap _minHeap = new minHeap((n / 2) + 2); maxHeap _maxHeap = new maxHeap((n / 2) + 2); for (int a_i = 0; a_i < n; a_i++) { a[a_i] = Convert.ToInt32(Console.ReadLine()); _maxHeap.add(a[a_i]); if(_maxHeap.position > (_minHeap.position+1)) { _minHeap.add(_maxHeap.maxValue(true)); } if(_maxHeap.maxValue(false) > _minHeap.minValue(false) && _minHeap.position > 0) { int aux = _minHeap.minValue(true); _minHeap.add(_maxHeap.maxValue(true)); _maxHeap.add(aux); } if (_maxHeap.position == _minHeap.position) Console.WriteLine(string.Format("{0:F1}", (Double)((Double)_minHeap.minValue(false)+(Double)_maxHeap.maxValue(false))/2)); else Console.WriteLine(string.Format("{0:F1}",(Double)_maxHeap.maxValue(false))); } } } class minHeap { public int position; public int[] minH; public minHeap(int size) { minH = new int[size]; position = 0; } public void add(int value) { if (position == 0) minH[++position] = value; else { minH[++position] = value; organize(); } } public void organize() { int pos = position; while ((pos-1) > 0 && minH[pos] > minH[pos - 1]) { int aux = minH[pos - 1]; minH[pos - 1] = minH[pos]; minH[pos] = aux; pos--; } } public int minValue(bool remove) { if(remove) { position--; return minH[position + 1]; } else return minH[position]; } } class maxHeap { public int position; public int[] maxH; public maxHeap(int size) { maxH = new int[size]; position = 0; } public void add(int value) { if (position == 0) maxH[++position] = value; else { maxH[++position] = value; organize(); } } public void organize() { int pos = position; while ((pos-1) > 0 && maxH[pos] < maxH[pos - 1]) { int aux = maxH[pos - 1]; maxH[pos - 1] = maxH[pos]; maxH[pos] = aux; pos--; } } public int maxValue(bool remove) { if (remove) { position--; return maxH[position + 1]; } else return maxH[position]; } }
Seems like cookies are disabled on this browser, please enable them to open this website
Heaps: Find the Running Median
You are viewing a single comment's thread. Return to all comments →
I developed a min and max heap but I got timeout. What am I doing wrong ?
using System; using System.Collections.Generic; using System.Linq; using System.Text;