Find the median in a running stream of integers
Here given code implementation process.
// C Program
// Find the median in a running stream of integers
#include <stdio.h>
//Swap two element in array
void swap(int arr[],int first,int second)
{
int auxiliary=arr[first];
arr[first]=arr[second];
arr[second]=auxiliary;
}
int compare(int arr[],int left,int right,int root,int size)
{
int location = -1;
if(left < size && arr[left] > arr[root] )
{
if(right < size && arr[right] > arr[left])
{
swap(arr,right,root);
location = right;
}
else
{
swap(arr,left,root);
location = left;
}
}
else if(right < size && arr[right] > arr[root])
{
swap(arr,right,root);
location = right;
}
return location;
}
void heap(int arr[],int size,int root)
{
//Get location of left and right child
int left = 2*root+1;
int right = 2*root+2;
int next = compare(arr, left, right, root, size);
if(next != -1)
{
heap(arr,size,next);
}
}
void build_heap(int arr[],int size)
{
if(size<=1)
{
return;
}
for (int i = (size/2)-1; i >= 0; i--)
{
heap(arr,size,i);
}
for (int i = size; i >= 0; i--)
{
swap(arr, 0, i);
heap(arr, i, 0);
}
}
// Find medians
void median(int arr[],int size)
{
//Auxiliary space which will used to find median
int auxiliary[size];
for (int i = 0; i < size; ++i)
{
//Assign array element arr[i] value to auxiliary array
auxiliary[i]=arr[i];
if(i==0)
{
//When single element into array
printf("%d ", arr[i]);
}
else
{
//Perform heap sort in auxiliary array
build_heap(auxiliary,i);
if((i+1) % 2 ==0)
{
//When index location is Even
printf("%d ", (auxiliary[(i+1)/2]+auxiliary[((i+1)/2)-1])/2);
}
else
{
//When index location is Odd
printf("%d ", auxiliary[(i+1)/2]);
}
}
}
}
int main()
{
//Collection of array elements
int arr[] = {4,8,3,10,9,5,2,6,7};
//Get the size of array
int size = sizeof(arr)/sizeof(arr[0]);
median(arr,size);
return 0;
}
Output
4 6 4 7 8 6 5 5 6/*
C++ Program
Find the median in a running stream of integers
*/
#include<iostream>
using namespace std;
class MyHeap {
public:
//Swap two element in array
void swap(int arr[], int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
int compare(int arr[], int left, int right, int root, int size) {
int location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
this->swap(arr, right, root);
location = right;
} else {
this->swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
this->swap(arr, right, root);
location = right;
}
return location;
}
void heap(int arr[], int size, int root) {
//Get location of left and right child
int left = 2 *root + 1;
int right = 2 *root + 2;
int next_in = this->compare(arr, left, right, root, size);
if (next_in != -1) {
this->heap(arr, size, next_in);
}
}
void build_heap(int arr[], int size) {
if (size <= 1) {
return;
}
for (int i = (size / 2) - 1; i >= 0; i--) {
this->heap(arr, size, i);
}
for (int i = size; i >= 0; i--) {
this->swap(arr, 0, i);
this->heap(arr, i, 0);
}
}
// Find medians
void median(int arr[], int size) {
int *auxiliary = new int[size];
for (int i = 0; i < size; ++i) {
//Assign array element arr[i] value to auxiliary array
auxiliary[i] = arr[i];
if (i == 0) {
//When single element into array
cout << " " << arr[i];
} else {
//Perform heap sort in auxiliary array
this->build_heap(auxiliary, i);
if ((i + 1) % 2 == 0) {
//When index location is Even
cout << " " << (auxiliary[(i + 1) / 2] + auxiliary[((i + 1) / 2) - 1]) / 2;
} else {
//When index location is Odd
cout << " " << auxiliary[(i + 1) / 2];
}
}
}
}
};
int main() {
MyHeap obj = MyHeap();
int arr[] = {
4,
8,
3,
10,
9,
5,
2,
6,
7
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.median(arr, size);
return 0;
}
Output
4 6 4 7 8 6 5 5 6/*
Java Program
Find the median in a running stream of integers
*/
public class MyHeap {
//Swap two element in array
public void swap(int []arr,int first,int second)
{
int auxiliary=arr[first];
arr[first]=arr[second];
arr[second]=auxiliary;
}
public int compare(int []arr,int left,int right,int root,int size)
{
int location = -1;
if(left < size && arr[left] > arr[root] )
{
if(right < size && arr[right] > arr[left])
{
swap(arr,right,root);
location = right;
}
else
{
swap(arr,left,root);
location = left;
}
}
else if(right < size && arr[right] > arr[root])
{
swap(arr,right,root);
location = right;
}
return location;
}
public void heap(int []arr,int size,int root)
{
//Get location of left and right child
int left = 2*root+1;
int right = 2*root+2;
int next_in = compare(arr, left, right, root, size);
if(next_in != -1)
{
heap(arr,size,next_in);
}
}
public void build_heap(int []arr,int size)
{
if(size<=1)
{
return;
}
for (int i = (size/2)-1; i >= 0; i--)
{
heap(arr,size,i);
}
for (int i = size; i >= 0; i--)
{
swap(arr, 0, i);
heap(arr, i, 0);
}
}
// Find medians
public void median(int []arr,int size)
{
//Auxiliary space which will used to find median
int []auxiliary= new int[size];
for (int i = 0; i < size; ++i)
{
//Assign array element arr[i] value to auxiliary array
auxiliary[i]=arr[i];
if(i==0)
{
//When single element into array
System.out.print(" "+ arr[i]);
}
else
{
//Perform heap sort in auxiliary array
build_heap(auxiliary,i);
if((i+1) % 2 ==0)
{
//When index location is Even
System.out.print(" "+ (auxiliary[(i+1)/2]+auxiliary[((i+1)/2)-1])/2);
}
else
{
//When index location is Odd
System.out.print(" "+ auxiliary[(i+1)/2]);
}
}
}
}
public static void main(String[] args) {
MyHeap obj = new MyHeap();
//Define Collection of integer values
int []arr = {4,8,3,10,9,5,2,6,7};
//Get the size of array
int size = arr.length;
obj.median(arr,size);
}
}
Output
4 6 4 7 8 6 5 5 6/*
C# Program
Find the median in a running stream of integers
*/
using System;
public class MyHeap {
//Swap two element in array
public void swap(int[] arr, int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
public int compare(int[] arr, int left, int right, int root, int size) {
int location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
swap(arr, right, root);
location = right;
} else {
swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
swap(arr, right, root);
location = right;
}
return location;
}
public void heap(int[] arr, int size, int root) {
//Get location of left and right child
int left = 2 * root + 1;
int right = 2 * root + 2;
int next_in = compare(arr, left, right, root, size);
if (next_in != -1) {
heap(arr, size, next_in);
}
}
public void build_heap(int[] arr, int size) {
if (size <= 1) {
return;
}
for (int i = (size / 2) - 1; i >= 0; i--) {
heap(arr, size, i);
}
for (int i = size; i >= 0; i--) {
swap(arr, 0, i);
heap(arr, i, 0);
}
}
// Find medians
public void median(int[] arr, int size) {
int[]
//Auxiliary space which will used to find median
auxiliary = new int[size];
for (int i = 0; i < size; ++i) {
//Assign array element arr[i] value to auxiliary array
auxiliary[i] = arr[i];
if (i == 0) {
Console.Write(" " + arr[i]);
} else {
build_heap(auxiliary, i);
if ((i + 1) % 2 == 0) {
Console.Write(" " + (auxiliary[(i + 1) / 2] + auxiliary[((i + 1) / 2) - 1]) / 2);
} else {
Console.Write(" " + auxiliary[(i + 1) / 2]);
}
}
}
}
public static void Main(String[] args) {
MyHeap obj = new MyHeap();
int[]
//Define Collection of integer values
arr = {
4,
8,
3,
10,
9,
5,
2,
6,
7
};
//Get the size of array
int size = arr.Length;
obj.median(arr, size);
}
}
Output
4 6 4 7 8 6 5 5 6<?php
/*
Php Program
Find the median in a running stream of integers
*/
class MyHeap {
//Swap two element in array
public function swap(&$arr, $first, $second) {
$auxiliary = $arr[$first];
$arr[$first] = $arr[$second];
$arr[$second] = $auxiliary;
}
public function compare(&$arr, $left, $right, $root, $size) {
$location = -1;
if ($left < $size && $arr[$left] > $arr[$root]) {
if ($right < $size && $arr[$right] > $arr[$left]) {
$this->swap($arr, $right, $root);
$location = $right;
} else {
$this->swap($arr, $left, $root);
$location = $left;
}
} else
if ($right < $size && $arr[$right] > $arr[$root]) {
$this->swap($arr, $right, $root);
$location = $right;
}
return $location;
}
public function heap(&$arr, $size, $root) {
//Get location of left and right child
$left = 2 *$root + 1;
$right = 2 *$root + 2;
$next_in = $this->compare($arr, $left, $right, $root, $size);
if ($next_in != -1) {
$this->heap($arr, $size, $next_in);
}
}
public function build_heap(&$arr, $size) {
if ($size <= 1) {
return;
}
for ($i = (intval($size / 2)) - 1; $i >= 0; $i--) {
$this->heap($arr, $size, $i);
}
for ($i = $size; $i >= 0; $i--) {
$this->swap($arr, 0, $i);
$this->heap($arr, $i, 0);
}
}
// Find medians
public function median($arr, $size) {
//Auxiliary space which will used to find median
$auxiliary = array_fill(0, $size, 0);
for ($i = 0; $i < $size; ++$i) {
//Assign array element arr[i] value to auxiliary array
$auxiliary[$i] = $arr[$i];
if ($i == 0) {
//When single element into array
echo(" ". $arr[$i]);
} else {
//Perform heap sort in auxiliary array
$this->build_heap($auxiliary, $i);
if (($i + 1) % 2 == 0) {
//When index location is Even
echo(" ". intval(($auxiliary[intval(($i + 1) / 2)] + $auxiliary[(intval(($i + 1) / 2)) - 1]) / 2));
} else {
//When index location is Odd
echo(" ". $auxiliary[intval(($i + 1) / 2)]);
}
}
}
}
}
function main() {
$obj = new MyHeap();
//Define Collection of integer values
$arr = array(4, 8, 3, 10, 9, 5, 2, 6, 7);
//Get the size of array
$size = count($arr);
$obj->median($arr, $size);
}
main();
Output
4 6 4 7 8 6 5 5 6/*
Node Js Program
Find the median in a running stream of integers
*/
class MyHeap {
//Swap two element in array
swap(arr, first, second) {
var auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
compare(arr, left, right, root, size) {
var location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
this.swap(arr, right, root);
location = right;
} else {
this.swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
this.swap(arr, right, root);
location = right;
}
return location;
}
heap(arr, size, root) {
//Get location of left and right child
var left = 2 *root + 1;
var right = 2 *root + 2;
var next_in = this.compare(arr, left, right, root, size);
if (next_in != -1) {
this.heap(arr, size, next_in);
}
}
build_heap(arr, size) {
if (size <= 1) {
return;
}
for (var i = (parseInt(size / 2)) - 1; i >= 0; i--) {
this.heap(arr, size, i);
}
for (var i = size; i >= 0; i--) {
this.swap(arr, 0, i);
this.heap(arr, i, 0);
}
}
// Find medians
median(arr, size) {
//Auxiliary space which will used to find median
var auxiliary = Array(size).fill(0);
for (var i = 0; i < size; ++i) {
//Assign array element arr[i] value to auxiliary array
auxiliary[i] = arr[i];
if (i == 0) {
//When single element into array
process.stdout.write(" " + arr[i]);
} else {
//Perform heap sort in auxiliary array
this.build_heap(auxiliary, i);
if ((i + 1) % 2 == 0) {
//When index location is Even
process.stdout.write(" " + parseInt((auxiliary[parseInt((i + 1) / 2)] + auxiliary[(parseInt((i + 1) / 2)) - 1]) / 2));
} else {
//When index location is Odd
process.stdout.write(" " + auxiliary[parseInt((i + 1) / 2)]);
}
}
}
}
}
function main(args) {
var obj = new MyHeap();
//Define Collection of integer values
var arr = [4, 8, 3, 10, 9, 5, 2, 6, 7];
//Get the size of array
var size = arr.length;
obj.median(arr, size);
}
main();
Output
4 6 4 7 8 6 5 5 6#
# Python 3 Program
# Find the median in a running stream of integers
class MyHeap :
# Swap two element in array
def swap(self, arr, first, second) :
auxiliary = arr[first]
arr[first] = arr[second]
arr[second] = auxiliary
def compare(self, arr, left, right, root, size) :
location = -1
if (left < size and arr[left] > arr[root]) :
if (right < size and arr[right] > arr[left]) :
self.swap(arr, right, root)
location = right
else :
self.swap(arr, left, root)
location = left
elif (right < size and arr[right] > arr[root]) :
self.swap(arr, right, root)
location = right
return location
def heap(self, arr, size, root) :
left = 2 * root + 1
right = 2 * root + 2
next_in = self.compare(arr, left, right, root, size)
if (next_in != -1) :
self.heap(arr, size, next_in)
def build_heap(self, arr, size) :
if (size <= 1) :
return
i = (int(size / 2)) - 1
while (i >= 0) :
self.heap(arr, size, i)
i -= 1
i = size
while (i >= 0) :
self.swap(arr, 0, i)
self.heap(arr, i, 0)
i -= 1
# Find medians
def median(self, arr, size) :
auxiliary = [0] * size
i = 0
result = 0
while (i < size) :
# Assign array element arr[i] value to auxiliary array
auxiliary[i] = arr[i]
if (i == 0) :
print(" ", arr[i], end = "")
else :
self.build_heap(auxiliary, i)
if ((i + 1) % 2 == 0) :
result = int((auxiliary[int((i + 1) / 2)] + auxiliary[(int((i + 1) / 2)) - 1]) / 2)
else :
result = auxiliary[int((i + 1) / 2)]
print(" ", result, end = "")
i += 1
def main() :
obj = MyHeap() # Define Collection of integer values
arr = [4, 8, 3, 10, 9, 5, 2, 6, 7] # Get the size of array
size = len(arr)
obj.median(arr, size)
if __name__ == "__main__":
main()
Output
4 6 4 7 8 6 5 5 6# Ruby Program
# Find the median in a running stream of integers
class MyHeap
# Swap two element in array
def swap(arr, first, second)
auxiliary = arr[first]
arr[first] = arr[second]
arr[second] = auxiliary
end
def compare(arr, left, right, root, size)
location = -1
if (left < size && arr[left] > arr[root])
if (right < size && arr[right] > arr[left])
self.swap(arr, right, root)
location = right
else
self.swap(arr, left, root)
location = left
end
elsif (right < size && arr[right] > arr[root])
self.swap(arr, right, root)
location = right
end
return location
end
def heap(arr, size, root)
left = 2 * root + 1
right = 2 * root + 2
next_in = self.compare(arr, left, right, root, size)
if (next_in != -1)
self.heap(arr, size, next_in)
end
end
def build_heap(arr, size)
if (size <= 1)
return
end
i = (size / 2) - 1
while (i >= 0)
self.heap(arr, size, i)
i -= 1
end
i = size
while (i >= 0)
self.swap(arr, 0, i)
self.heap(arr, i, 0)
i -= 1
end
end
# Find medians
def median(arr, size)
auxiliary = Array.new(size, 0)
i = 0
result = 0
while (i < size)
# Assign array element arr[i] value to auxiliary array
auxiliary[i] = arr[i]
if (i == 0)
print(" ", arr[i])
else
self.build_heap(auxiliary, i)
if ((i + 1) % 2 == 0)
result = (auxiliary[(i + 1) / 2] + auxiliary[((i + 1) / 2) - 1]) / 2
else
result = auxiliary[(i + 1) / 2]
end
print(" ", result)
end
i += 1
end
end
end
def main()
obj = MyHeap.new()
# Define Collection of integer values
arr = [4, 8, 3, 10, 9, 5, 2, 6, 7]
# Get the size of array
size = arr.length
obj.median(arr, size)
end
main()
Output
4 6 4 7 8 6 5 5 6/*
Scala Program
Find the median in a running stream of integers
*/
class MyHeap {
//Swap two element in array
def swap(arr: Array[Int], first: Int, second: Int): Unit = {
val auxiliary: Int = arr(first);
arr(first) = arr(second);
arr(second) = auxiliary;
}
def compare(arr: Array[Int], left: Int, right: Int, root: Int, size: Int): Int = {
var location: Int = -1;
if (left < size && arr(left) > arr(root)) {
if (right < size && arr(right) > arr(left)) {
this.swap(arr, right, root);
location = right;
} else {
this.swap(arr, left, root);
location = left;
}
} else
if (right < size && arr(right) > arr(root)) {
this.swap(arr, right, root);
location = right;
}
return location;
}
def heap(arr: Array[Int], size: Int, root: Int): Unit = {
val left: Int = 2 * root + 1;
val right: Int = 2 * root + 2;
val next_in: Int = this.compare(arr, left, right, root, size);
if (next_in != -1) {
this.heap(arr, size, next_in);
}
}
def build_heap(arr: Array[Int], size: Int): Unit = {
if (size <= 1) {
return;
}
var i: Int = ((size / 2).toInt) - 1;
while (i >= 0) {
this.heap(arr, size, i);
i -= 1;
}
i = size;
while (i >= 0) {
this.swap(arr, 0, i);
this.heap(arr, i, 0);
i -= 1;
}
}
// Find medians
def median(arr: Array[Int], size: Int): Unit = {
var auxiliary: Array[Int] = Array.fill[Int](size)(0);
var i: Int = 0;
var result: Int = 0;
while (i < size) {
//Assign array element arr[i] value to auxiliary array
auxiliary(i) = arr(i);
if (i == 0) {
print(" " + arr(i));
} else {
this.build_heap(auxiliary, i);
if ((i + 1) % 2 == 0) {
result = ((auxiliary(((i + 1) / 2).toInt) + auxiliary((((i + 1) / 2).toInt) - 1)) / 2).toInt;
} else {
result = auxiliary(((i + 1) / 2).toInt);
}
print(" " + result);
}
i += 1;
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyHeap = new MyHeap();
//Define Collection of integer values
val arr: Array[Int] = Array(4, 8, 3, 10, 9, 5, 2, 6, 7);
//Get the size of array
val size: Int = arr.length;
obj.median(arr, size);
}
}
Output
4 6 4 7 8 6 5 5 6/*
Swift Program
Find the median in a running stream of integers
*/
class MyHeap {
//Swap two element in array
func swap(_ arr: inout [Int], _ first: Int, _ second: Int) {
let auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
func compare(_ arr: inout [Int], _ left: Int, _ right: Int, _ root: Int, _ size: Int) -> Int {
var location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
self.swap(&arr, right, root);
location = right;
} else {
self.swap(&arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
self.swap(&arr, right, root);
location = right;
}
return location;
}
func heap(_ arr: inout [Int], _ size: Int, _ root: Int) {
let left = 2 * root + 1;
let right = 2 * root + 2;
let next_in = self.compare(&arr, left, right, root, size);
if (next_in != -1) {
self.heap(&arr, size, next_in);
}
}
func build_heap(_ arr: inout [Int], _ size: Int) {
if (size <= 1) {
return;
}
var i = (size / 2) - 1;
while (i >= 0) {
self.heap(&arr, size, i);
i -= 1;
}
i = size;
while (i >= 0) {
self.swap(&arr, 0, i);
self.heap(&arr, i, 0);
i -= 1;
}
}
// Find medians
func median(_ arr: [Int], _ size: Int) {
var auxiliary = Array(repeating: 0, count: size);
var i = 0;
var result = 0;
while (i < size) {
//Assign array element arr[i] value to auxiliary array
auxiliary[i] = arr[i];
if (i == 0) {
print(" ", arr[i], terminator: "");
} else {
self.build_heap(&auxiliary, i);
if ((i + 1) % 2 == 0) {
result = (auxiliary[(i + 1) / 2] + auxiliary[((i + 1) / 2) - 1]) / 2;
} else {
result = auxiliary[(i + 1) / 2];
}
print(" ", result, terminator: "");
}
i += 1;
}
}
}
func main() {
let obj = MyHeap();
//Define Collection of integer values
let arr = [4, 8, 3, 10, 9, 5, 2, 6, 7];
//Get the size of array
let size = arr.count;
obj.median(arr, size);
}
main();
Output
4 6 4 7 8 6 5 5 6
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment