leetcode 295. The median of the data stream

Ideas

Using two heaps, the data currently obtained from the data stream is divided into two parts. The number of data in the two parts differs by at most 1. One part is placed in a large top pile A, and the other part is placed in a small top pile B. When adding the numbers in the data stream to the heap, ensure that all numbers in A are less than or equal to the numbers in B. See method for specific details

. In this way, calculating the median is simple.

The answer to the question on Likou is given below (submitted for approval). On this basis, the solution of the Niuke problem can be slightly modified.

type MedianFinder struct {
maxHeap *MaxHeap
minHeap *MinHeap
}

/** initialize your data structure here. */
func  Constructor ()  MedianFinder {
return MedianFinder{
maxHeap: NewMaxHeap(),
minHeap: NewMinHeap(),
}
}

FUNC  (the this MedianFinder *)  AddNum (NUM int )   {
IF this.maxHeap.IsEmpty () {//stack top priority into a large
this.maxHeap.Push(num)
} else  if num <= this.maxHeap.Top() { //Put the big top heap first
this.maxHeap.Push(num)
} else {
this.minHeap.Push(num)
}
total := this.maxHeap.Len() + this.minHeap.Len()
half := total/2
//When total&1 == 0, total is an even number, and each heap is divided into exactly half of the data.
//When total&1 != 0, the result of total&1 is 1, and total is an odd number,
//Make the number of data in the large top heap 1 more than that in the small top heap, simplifying the logic when obtaining the median (see the function FindMedian ).
if this.maxHeap.Len()> half+total& 1 { //adjust when the number is too large
this.minHeap.Push(this.maxHeap.Top())
this.maxHeap.Pop()
}
if this.minHeap.Len()> half { //adjust if there are more
this.maxHeap.Push(this.minHeap.Top())
this.minHeap.Pop()
}
}

func  (this *MedianFinder)  FindMedian ()  float64 {
//The amount of data in the two heaps is the same
if this.maxHeap.Len() == this.minHeap.Len() {
return ( float64 (this.maxHeap.Top() )+ float64 (this.minHeap.Top()))/ 2
}
//If the amount of data is different, take the top of the large top heap directly
return  float64 (this.maxHeap.Top())
}

/**
* Your MedianFinder object will be instantiated and called as such:
* obj := Constructor();
* param_2 := obj.FindMedian();
*/

//Extract the common part of the large top heap and the small top heap and implement it as Heap
type Heap struct {
data [] int
size int
//Whether the parent node and child node are in "positive order".
//true-"positive sequence".
//Determined by the characteristics of the large top heap/small top heap.
isParentAndChildOrdered func (parentVal, childVal int )  bool
//When comparing sibling nodes, determine whether to select the sibling node "to the right" (larger index value).
//true-select the "right" node.
//Determined by the characteristics of the large top heap/small top heap.
shouldChooseRightSibling func (leftVal, rightVal int )  bool
}

func  NewHeap (isParentAndChildOrdered func (parentVal, childVal int )  bool ,
shouldChooseRightSibling func (leftVal, rightVal int )  bool ) * Heap {
return &Heap{
isParentAndChildOrdered: isParentAndChildOrdered,
shouldChooseRightSibling: shouldChooseRightSibling,
}
}

func  (o *Heap)  Len ()  int {
return o.size
}

func  (o *Heap)  IsEmpty ()  bool {
return o.size == 0
}

func  (o *Heap)  Top ()  int {
if o.IsEmpty() {
panic ( "Heap is empty" )
}
return o.data[ 0 ]
}

func  (o *Heap)  Push (n int ) {
if o.size < len (o.data) {
o.data[o.size] = n
} else {
o.data = append (o.data, n)
}
o.size++
o.siftUp()
}

func  (o *Heap)  siftUp () {
if o.size < 2 {
return
}
var (
child = o.size -1
childV = o.data[child]
)
for child> 0 {
p := (child -1 )>> 1
pV := o.data[p]
if o.isParentAndChildOrdered(pV, childV) {
break
}
o.data[child] = pV
child = p
}
o.data[child] = childV
}

func  (o *Heap)  Pop () {
if o.IsEmpty() {
panic ( "Heap is empty" )
}
o.data[ 0 ] = o.data[o.size -1 ]
o.size--
o.siftDown()
}

func  (o *Heap)  siftDown () {
if o.size < 2 {
return
}
var (
p int
pV = o.data[p]
)
for {
child := 2 *p + 1
if child >= o.size {
break
}
if child+ 1 <o.size &&
o.shouldChooseRightSibling(o.data[child], o.data[child+ 1 ]) {
child++
}
childV := o.data[child]
if o.isParentAndChildOrdered(pV, childV) {
break
}
o.data[p] = childV
p = child
}
o.data[p] = pV
}

//
type MaxHeap struct {
*Heap
}

func  NewMaxHeap () * MaxHeap {
o := &MaxHeap{}
o.Heap = NewHeap(o.isParentAndChildOrdered, o.shouldChooseRightSibling)
return o
}

func  (MaxHeap)  isParentAndChildOrdered (parentVal, childVal int )  bool {
return parentVal >= childVal
}

func  (MaxHeap)  shouldChooseRightSibling (leftVal, rightVal int )  bool {
return leftVal <rightVal
}

//
type MinHeap struct {
*Heap
}

func  NewMinHeap () * MinHeap {
o := &MinHeap{}
o.Heap = NewHeap(o.isParentAndChildOrdered, o.shouldChooseRightSibling)
return o
}

func  (MinHeap)  isParentAndChildOrdered (parentVal, childVal int )  bool {
return parentVal <= childVal
}

func  (MinHeap)  shouldChooseRightSibling (leftVal, rightVal int )  bool {
return leftVal> rightVal
}
Copy code

Two heaps, holding all known data, the space complexity is$O(n)$ .
method

,time complexity$O(logn)$ .
method
func (this *MedianFinder) FindMedian() float64
,time complexity$O(1)$ .

The above code is "embedding (inheritance) + function pointer", the following implementation is changed to "embedding (combination) + interface" (submitted for approval).

type MedianFinder struct {
maxHeap *Heap
minHeap *Heap
}

/** initialize your data structure here. */
func  Constructor ()  MedianFinder {
return MedianFinder{
maxHeap: NewHeap(&MaxHeapCompare{}),
minHeap: NewHeap(&MinHeapCompare{}),
}
}

FUNC  (the this MedianFinder *)  AddNum (NUM int )   {
IF this.maxHeap.IsEmpty () {
this.maxHeap.Push(num)
} else  if num <= this.maxHeap.Top() {
this.maxHeap.Push(num)
} else {
this.minHeap.Push(num)
}

total := this.maxHeap.Len() + this.minHeap.Len()
half := total/2
if total& 1 == 0 { //even number
for this.maxHeap.Len()> half {
this.minHeap.Push(this.maxHeap.Top())
this.maxHeap.Pop()
}
for this.minHeap.Len()> half {
this.maxHeap.Push(this.minHeap.Top())
this.minHeap.Pop()
}
} else {
oneMore := half+ 1
for this.maxHeap.Len()> oneMore {
this.minHeap.Push(this.maxHeap.Top())
this.maxHeap.Pop()
}
for this.minHeap.Len()> half {
this.maxHeap.Push(this.minHeap.Top())
this.minHeap.Pop()
}
}
}

func  (this *MedianFinder)  FindMedian ()  float64 {
if this.maxHeap.Len() == this.minHeap.Len() {
return ( float64 (this.maxHeap.Top())+ float64 (this.minHeap.Top( )))/ 2
}
return  float64 (this.maxHeap.Top())
}

/**
* Your MedianFinder object will be instantiated and called as such:
* obj := Constructor();
* param_2 := obj.FindMedian();
*/

type HeapCompare interface {
IsParentAndChildOrdered(parentVal, childVal int ) bool
ShouldChooseRightSibling(leftVal, rightVal int ) bool
}

type Heap struct {
data [] int
size int
HeapCompare
}

func  NewHeap (cmp HeapCompare) * Heap {
return &Heap{
HeapCompare: cmp,
}
}

func  (o *Heap)  Len ()  int {
return o.size
}

func  (o *Heap)  IsEmpty ()  bool {
return o.size == 0
}

func  (o *Heap)  Top ()  int {
if o.IsEmpty() {
panic ( "Heap is empty" )
}
return o.data[ 0 ]
}

func  (o *Heap)  Push (n int ) {
if o.size < len (o.data) {
o.data[o.size] = n
} else {
o.data = append (o.data, n)
}
o.size++
o.siftUp()
}

func  (o *Heap)  siftUp () {
if o.size < 2 {
return
}
var (
child = o.size -1
childV = o.data[child]
)
for child> 0 {
p := (child -1 )>> 1
pV := o.data[p]
if o.IsParentAndChildOrdered(pV, childV) {
break
}
o.data[child] = pV
child = p
}
o.data[child] = childV
}

func  (o *Heap)  Pop () {
if o.IsEmpty() {
panic ( "Heap is empty" )
}
o.data[ 0 ] = o.data[o.size -1 ]
o.size--
o.siftDown()
}

func  (o *Heap)  siftDown () {
if o.size < 2 {
return
}
var (
p int
pV = o.data[p]
)
for {
child := 2 *p + 1
if child >= o.size {
break
}
if child+ 1 <o.size &&
o.ShouldChooseRightSibling(o.data[child], o.data[child+ 1 ]) {
child++
}
childV := o.data[child]
if o.IsParentAndChildOrdered(pV, childV) {
break
}
o.data[p] = childV
p = child
}
o.data[p] = pV
}

type MaxHeapCompare struct {}

func  (o *MaxHeapCompare)  IsParentAndChildOrdered (parentVal, childVal int )  bool {
return parentVal >= childVal
}

func  (o *MaxHeapCompare)  ShouldChooseRightSibling (leftVal, rightVal int )  bool {
return leftVal <rightVal
}

type MinHeapCompare struct {}

func  (o *MinHeapCompare)  IsParentAndChildOrdered (parentVal, childVal int )  bool {
return parentVal <= childVal
}

func  (o *MinHeapCompare)  ShouldChooseRightSibling (leftVal, rightVal int )  bool {
return leftVal> rightVal
}
Copy code