Dado que los enteros se leen de un flujo de datos. Encuentre la mediana de todos los elementos leídos hasta ahora desde el primer entero hasta el último entero. Esto también se llama la Mediana de Enteros Corrientes. El flujo de datos puede ser cualquier fuente de datos, por ejemplo, un archivo, una array de enteros, un flujo de entrada, etc.
¿Qué es Mediano?
C++
// C++ program to find med in
// stream of running integers
#include<bits/stdc++.h>
using namespace std;
// function to calculate med of stream
void printMedians(double arr[], int n)
{
// max heap to store the smaller half elements
priority_queue<double> s;
// min heap to store the greater half elements
priority_queue<double,vector<double>,greater<double> > g;
double med = arr[0];
s.push(arr[0]);
cout << med << endl;
// reading elements of stream one by one
/* At any time we try to make heaps balanced and
their sizes differ by at-most 1. If heaps are
balanced,then we declare median as average of
min_heap_right.top() and max_heap_left.top()
If heaps are unbalanced,then median is defined
as the top element of heap of larger size */
for (int i=1; i < n; i++)
{
double x = arr[i];
// case1(left side heap has more elements)
if (s.size() > g.size())
{
if (x < med)
{
g.push(s.top());
s.pop();
s.push(x);
}
else
g.push(x);
med = (s.top() + g.top())/2.0;
}
// case2(both heaps are balanced)
else if (s.size()==g.size())
{
if (x < med)
{
s.push(x);
med = (double)s.top();
}
else
{
g.push(x);
med = (double)g.top();
}
}
// case3(right side heap has more elements)
else
{
if (x > med)
{
s.push(g.top());
g.pop();
g.push(x);
}
else
s.push(x);
med = (s.top() + g.top())/2.0;
}
cout << med << endl;
}
}
// Driver program to test above functions
int main()
{
// stream of integers
double arr[] = {5, 15, 10, 20, 3};
int n = sizeof(arr)/sizeof(arr[0]);
printMedians(arr, n);
return 0;
}
Java
// Java program to find med in
// stream of running integers
import java.util.Collections;
import java.util.PriorityQueue;
public class MedianMaintain
{
// method to calculate med of stream
public static void printMedian(int[] a)
{
double med = a[0];
// max heap to store the smaller half elements
PriorityQueue<Integer> smaller = new PriorityQueue<>
(Collections.reverseOrder());
// min-heap to store the greater half elements
PriorityQueue<Integer> greater = new PriorityQueue<>();
smaller.add(a[0]);
System.out.println(med);
// reading elements of stream one by one
/* At any time we try to make heaps balanced and
their sizes differ by at-most 1. If heaps are
balanced,then we declare median as average of
min_heap_right.top() and max_heap_left.top()
If heaps are unbalanced,then median is defined
as the top element of heap of larger size */
for(int i = 1; i < a.length; i++)
{
int x = a[i];
// case1(left side heap has more elements)
if(smaller.size() > greater.size())
{
if(x < med)
{
greater.add(smaller.remove());
smaller.add(x);
}
else
greater.add(x);
med = (double)(smaller.peek() + greater.peek())/2;
}
// case2(both heaps are balanced)
else if(smaller.size() == greater.size())
{
if(x < med)
{
smaller.add(x);
med = (double)smaller.peek();
}
else
{
greater.add(x);
med = (double)greater.peek();
}
}
// case3(right side heap has more elements)
else
{
if(x > med)
{
smaller.add(greater.remove());
greater.add(x);
}
else
smaller.add(x);
med = (double)(smaller.peek() + greater.peek())/2;
}
System.out.println(med);
}
}
// Driver code
public static void main(String []args)
{
// stream of integers
int[] arr = new int[]{5, 15, 10, 20, 3};
printMedian(arr);
}
}
// This code is contributed by Kaustav kumar Chanda.
Python3
# python3 program to find med in # stream of running integers from heapq import * # function to calculate med of stream def printMedians(arr, n): # max heap to store the smaller half elements s = [] # min heap to store the greater half elements g = [] heapify(s) heapify(g) med = arr[0] heappush(s, arr[0]) print(med) # reading elements of stream one by one for i in range(1, n): x = arr[i] # case1(left side heap has more elements) if len(s) > len(g): if x < med: heappush(g, heappop(s)) heappush(s, x) else: heappush(g, x) med = (nlargest(1, s)[0] + nsmallest(1, g)[0])/2 # case2(both heaps are balanced) elif len(s) == len(g): if x < med: heappush(s, x) med = nlargest(1, s)[0] else: heappush(g, x) med = nsmallest(1, g)[0] # case3(right side heap has more elements) else: if x > med: heappush(s, heappop(g)) heappush(g, x) else: heappush(s, x) med = (nlargest(1, s)[0] + nsmallest(1, g)[0])/2 print(med) # Driver program to test above functions arr = [5, 15, 10, 20, 3] printMedians(arr, len(arr)) # This code is contributed by cavi4762.
C#
// C# program to find med in
// stream of running integers
using System;
using System.Collections.Generic;
public class MedianMaintain
{
// method to calculate med of stream
public static void printMedian(int[] a)
{
double med = a[0];
// max heap to store the smaller half elements
List<int> smaller = new List<int>();
// min-heap to store the greater half elements
List<int> greater = new List<int>();
smaller.Add(a[0]);
Console.WriteLine(med);
// reading elements of stream one by one
/* At any time we try to make heaps balanced and
their sizes differ by at-most 1. If heaps are
balanced,then we declare median as average of
min_heap_right.top() and max_heap_left.top()
If heaps are unbalanced,then median is defined
as the top element of heap of larger size */
for(int i = 1; i < a.Length; i++)
{
int x = a[i];
// case1(left side heap has more elements)
if(smaller.Count > greater.Count)
{
if(x < med)
{
smaller.Sort();
smaller.Reverse();
greater.Add(smaller[0]);
smaller.RemoveAt(0);
smaller.Add(x);
}
else
greater.Add(x);
smaller.Sort();
smaller.Reverse();
greater.Sort();
med = (double)(smaller[0] + greater[0])/2;
}
// case2(both heaps are balanced)
else if(smaller.Count == greater.Count)
{
if(x < med)
{
smaller.Add(x);
smaller.Sort();
smaller.Reverse();
med = (double)smaller[0];
}
else
{
greater.Add(x);
greater.Sort();
med = (double)greater[0];
}
}
// case3(right side heap has more elements)
else
{
if(x > med)
{
greater.Sort();
smaller.Add(greater[0]);
greater.RemoveAt(0);
greater.Add(x);
}
else
smaller.Add(x);
smaller.Sort();
smaller.Reverse();
med = (double)(smaller[0] + greater[0])/2;
}
Console.WriteLine(med);
}
}
// Driver code
public static void Main(String []args)
{
// stream of integers
int[] arr = new int[]{5, 15, 10, 20, 3};
printMedian(arr);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find med in
// stream of running integers
// method to calculate med of stream
function printMedian(a)
{
let med = a[0];
// max heap to store the smaller half elements
let smaller = [];
// min-heap to store the greater half elements
let greater = [];
smaller.push(a[0]);
document.write(med+"<br>");
// reading elements of stream one by one
/* At any time we try to make heaps balanced and
their sizes differ by at-most 1. If heaps are
balanced,then we declare median as average of
min_heap_right.top() and max_heap_left.top()
If heaps are unbalanced,then median is defined
as the top element of heap of larger size */
for(let i = 1; i < a.length; i++)
{
let x = a[i];
// case1(left side heap has more elements)
if(smaller.length > greater.length)
{
if(x < med)
{
smaller.sort(function(a,b){return b-a;});
greater.push(smaller.shift());
smaller.push(x);
}
else
{ greater.push(x);}
smaller.sort(function(a,b){return b-a;});
greater.sort(function(a,b){return a-b;});
med = (smaller[0] + greater[0])/2;
}
// case2(both heaps are balanced)
else if(smaller.length == greater.length)
{
if(x < med)
{
smaller.push(x);
smaller.sort(function(a,b){return b-a;});
med = smaller[0];
}
else
{
greater.push(x);
greater.sort(function(a,b){return a-b;});
med = greater[0];
}
}
// case3(right side heap has more elements)
else
{
if(x > med)
{
greater.sort(function(a,b){return a-b;});
smaller.push(greater.shift());
greater.push(x);
}
else
{
smaller.push(x);}
smaller.sort(function(a,b){return b-a;});
med = (smaller[0] + greater[0])/2;
}
document.write(med+"<br>");
}
}
// Driver code
// stream of integers
let arr=[5, 15, 10, 20, 3];
printMedian(arr);
// This code is contributed by avanitrachhadiya2155
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA