FilesExpand file tree

 patch-1

/

MedianOfRunningArray.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

52 lines (43 loc) · 1.22 KB

 patch-1

/

MedianOfRunningArray.java

Top

File metadata and controls

• Code
• Blame

52 lines (43 loc) · 1.22 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

package Misc;

import java.util.Collections;

import java.util.PriorityQueue;

/**

* @author shrutisheoran

*/

public class MedianOfRunningArray {

private PriorityQueue<Integer> p1;

private PriorityQueue<Integer> p2;

//Constructor

public MedianOfRunningArray() {

this.p1 = new PriorityQueue<>(Collections.reverseOrder()); //Max Heap

this.p2 = new PriorityQueue<>(); //Min Heap

}

/*

Inserting lower half of array to max Heap

and upper half to min heap

*/

public void insert(Integer e) {

p2.add(e);

if (p2.size() - p1.size() > 1)

p1.add(p2.remove());

}

/*

Returns median at any given point

*/

public Integer median() {

if (p1.size() == p2.size())

return (p1.peek() + p2.peek()) / 2;

return p1.size() > p2.size() ? p1.peek() : p2.peek();

}

public static void main(String[] args) {

/*

Testing the median function

*/

MedianOfRunningArray p = new MedianOfRunningArray();

int arr[] = {10, 7, 4, 9, 2, 3, 11, 17, 14};

for (int i = 0; i < 9; i++) {

p.insert(arr[i]);

System.out.print(p.median() + " ");

}

}

}