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







© 2021, kalkicode.com, All rights reserved