Tweeted twitter.com/#!/StackProgrammer/status/610737224515211265
3 Removed [interview], cleaned up language
source | link

I read a question in one book: Numbers are randomly generated and stored into an (expanding) array, How would you keep track of the median?and I'm looking for input on how to solve it:

Numbers are randomly generated and stored into an (expanding) array, How would you keep track of the median?

There are two data structures can solve the problem. One is the balanced binary tree, the other is two heaps which keep trace of the biggest half and the smallest half of the elements. I think these two solutions hashave the same running time as O(n lg n)O(n lg n), but I am not sure of my judgement.

In your opinions, What is the best way to keep track of the median?

————————————————————————————continue

My attempt:

In this question,I think the heapsa heap is the best way to keep track of the median. There are two heaps, the big heap and the small heap, which need not to be sequential. First, we calculate the mean value of the elements in the array. If the element is less than the mean value, we put the num to the small heap. On the contrary, we put the num to the big heap. If the number of the big heap is equal to the number of the small heap, the biggest one in the small heap and the smallest one in the big heap are the median. If the two heaps have different size, we just pop the root element from the heap with bigger size and push it to the root of the smaller size heap. For big heap, the root element is the smallest one, and for small heap, the root element is the biggest one. In this way, if the two heaps have the same size or a digital difference, we find the medium in the root.

I think this solution has the running time as O(m*n), m means the times we adjust the unbalance heaps.

Is this the best way to keep tracetrack of the median?

I read a question in one book: Numbers are randomly generated and stored into an (expanding) array, How would you keep track of the median?

There are two data structures can solve the problem. One is the balanced binary tree, the other is two heaps which keep trace of the biggest half and the smallest half of the elements. I think these two solutions has the same running time as O(n lg n), but I am not sure of my judgement.

In your opinions, What is the best way to keep track of the median?

————————————————————————————continue

In this question,I think the heaps is the best way to keep track of the median. There are two heaps, the big heap and the small heap, which need not to be sequential. First, we calculate the mean value of the elements in the array. If the element is less than the mean value, we put the num to the small heap. On the contrary, we put the num to the big heap. If the number of the big heap is equal to the number of the small heap, the biggest one in the small heap and the smallest one in the big heap are the median. If the two heaps have different size, we just pop the root element from the heap with bigger size and push it to the root of the smaller size heap. For big heap, the root element is the smallest one, and for small heap, the root element is the biggest one. In this way, if the two heaps have the same size or a digital difference, we find the medium in the root.

I think this solution has the running time as O(m*n), m means the times we adjust the unbalance heaps.

Is this the best way to keep trace of the median?

I read a question, and I'm looking for input on how to solve it:

Numbers are randomly generated and stored into an (expanding) array, How would you keep track of the median?

There are two data structures can solve the problem. One is the balanced binary tree, the other is two heaps which keep trace of the biggest half and the smallest half of the elements. I think these two solutions have the same running time as O(n lg n), but I am not sure of my judgement.

What is the best way to keep track of the median?

My attempt:

In this question,I think a heap is the best way to keep track of the median. There are two heaps, the big heap and the small heap, which need not to be sequential. First, we calculate the mean value of the elements in the array. If the element is less than the mean value, we put the num to the small heap. On the contrary, we put the num to the big heap. If the number of the big heap is equal to the number of the small heap, the biggest one in the small heap and the smallest one in the big heap are the median. If the two heaps have different size, we just pop the root element from the heap with bigger size and push it to the root of the smaller size heap. For big heap, the root element is the smallest one, and for small heap, the root element is the biggest one. In this way, if the two heaps have the same size or a digital difference, we find the medium in the root.

I think this solution has the running time as O(m*n), m means the times we adjust the unbalance heaps.

Is this the best way to keep track of the median?

2 add my own solution to the question
source | link

I read a question in one book: Numbers are randomly generated and stored into an (expanding) array, How would you keep track of the median?

There are two data structures can solve the problem. One is the balanced binary tree, the other is two heaps which keep trace of the biggest half and the smallest half of the elements. I think these two solutions has the same running time as O(n lg n), but I am not sure of my judgement.

In your opinions, What is the best way to keep track of the median?

————————————————————————————continue

In this question,I think the heaps is the best way to keep track of the median. There are two heaps, the big heap and the small heap, which need not to be sequential. First, we calculate the mean value of the elements in the array. If the element is less than the mean value, we put the num to the small heap. On the contrary, we put the num to the big heap. If the number of the big heap is equal to the number of the small heap, the biggest one in the small heap and the smallest one in the big heap are the median. If the two heaps have different size, we just pop the root element from the heap with bigger size and push it to the root of the smaller size heap. For big heap, the root element is the smallest one, and for small heap, the root element is the biggest one. In this way, if the two heaps have the same size or a digital difference, we find the medium in the root.

I think this solution has the running time as O(m*n), m means the times we adjust the unbalance heaps.

Is this the best way to keep trace of the median?

I read a question in one book: Numbers are randomly generated and stored into an (expanding) array, How would you keep track of the median?

There are two data structures can solve the problem. One is the balanced binary tree, the other is two heaps which keep trace of the biggest half and the smallest half of the elements. I think these two solutions has the same running time as O(n lg n), but I am not sure of my judgement.

In your opinions, What is the best way to keep track of the median?

I read a question in one book: Numbers are randomly generated and stored into an (expanding) array, How would you keep track of the median?

There are two data structures can solve the problem. One is the balanced binary tree, the other is two heaps which keep trace of the biggest half and the smallest half of the elements. I think these two solutions has the same running time as O(n lg n), but I am not sure of my judgement.

In your opinions, What is the best way to keep track of the median?

————————————————————————————continue

In this question,I think the heaps is the best way to keep track of the median. There are two heaps, the big heap and the small heap, which need not to be sequential. First, we calculate the mean value of the elements in the array. If the element is less than the mean value, we put the num to the small heap. On the contrary, we put the num to the big heap. If the number of the big heap is equal to the number of the small heap, the biggest one in the small heap and the smallest one in the big heap are the median. If the two heaps have different size, we just pop the root element from the heap with bigger size and push it to the root of the smaller size heap. For big heap, the root element is the smallest one, and for small heap, the root element is the biggest one. In this way, if the two heaps have the same size or a digital difference, we find the medium in the root.

I think this solution has the running time as O(m*n), m means the times we adjust the unbalance heaps.

Is this the best way to keep trace of the median?

    Post Undeleted by Steven Mou
    Post Deleted by Steven Mou
1
source | link

What is the best way to keep track of the median?

I read a question in one book: Numbers are randomly generated and stored into an (expanding) array, How would you keep track of the median?

There are two data structures can solve the problem. One is the balanced binary tree, the other is two heaps which keep trace of the biggest half and the smallest half of the elements. I think these two solutions has the same running time as O(n lg n), but I am not sure of my judgement.

In your opinions, What is the best way to keep track of the median?