Golang 2 heap solutions


  • 0

    The idea is pretty much described in the article below very well:
    https://leetcode.com/articles/find-median-from-data-stream/

    In Go, we need to write many boiler plates to suffice interface of heap, but it is relatively easy to understand and memorize.
    https://golang.org/pkg/container/heap/
    Also the important fact is that even though there is no Peek method, 0 th index value is always the minimum / maximum value.

    
    type MedianFinder struct {
    	Smaller ByDESC
    	Larger  ByASC
    }
    
    /** initialize your data structure here. */
    func Constructor() MedianFinder {
    	s, l := []int{}, []int{}
    	return MedianFinder{ByDESC(s), ByASC(l)}
    }
    
    func (this *MedianFinder) AddNum(num int) {
    	if len(this.Smaller) == 0 {
    		heap.Push(&this.Smaller, num)
    		return
    	}
    
    	if this.Smaller[0] >= num {
    		heap.Push(&this.Smaller, num)
    		if len(this.Smaller)-len(this.Larger) > 1 {
    			maxInSmaller := heap.Pop(&this.Smaller)
    			i, _ := maxInSmaller.(int)
    			heap.Push(&this.Larger, i)
    		}
    	} else {
    		heap.Push(&this.Larger, num)
    		if len(this.Larger)-len(this.Smaller) > 0 {
    			minInLarger := heap.Pop(&this.Larger)
    			i, _ := minInLarger.(int)
    			heap.Push(&this.Smaller, i)
    		}
    	}
    }
    
    func (this *MedianFinder) FindMedian() float64 {
    	slen, llen := len(this.Smaller), len(this.Larger)
    	if (slen+llen)%2 == 0 {
    		return float64(this.Smaller[0]+this.Larger[0]) / 2.0
    	} else {
    		return float64(this.Smaller[0])
    	}
    }
    
    type ByASC []int
    
    func (b ByASC) Len() int {
    	return len(b)
    }
    
    func (b ByASC) Swap(i, j int) {
    	b[i], b[j] = b[j], b[i]
    }
    
    func (b ByASC) Less(i, j int) bool {
    	return b[i] < b[j]
    }
    
    func (b *ByASC) Pop() interface{} {
    	bv := *b
    	val := bv[len(bv)-1]
    	*b = bv[:len(bv)-1]
    	return val
    }
    
    func (b *ByASC) Push(inte interface{}) {
    	i, _ := inte.(int)
    	*b = append(*b, i)
    }
    
    type ByDESC []int
    
    func (b ByDESC) Len() int {
    	return len(b)
    }
    
    func (b ByDESC) Swap(i, j int) {
    	b[i], b[j] = b[j], b[i]
    }
    
    func (b ByDESC) Less(i, j int) bool {
    	return b[i] > b[j]
    }
    
    func (b *ByDESC) Pop() interface{} {
    	bv := *b
    	val := bv[len(bv)-1]
    	*b = bv[:len(bv)-1]
    	return val
    }
    
    func (b *ByDESC) Push(inte interface{}) {
    	i, _ := inte.(int)
    	*b = append(*b, i)
    }
    
    

  • 0
    I

    My golang code, use embedding and interface to reduce the lines of code

    type PeekHeap interface {
        heap.Interface
        Peek() interface{}
    }
    
    type heapInt []int
    
    func (h heapInt) Len() int {
    	return len(h)
    }
    
    func (h heapInt) Less(i, j int) bool {
    	return h[i] < h[j]
    }
    
    func (h heapInt) Swap(i, j int) {
    	h[i], h[j] = h[j], h[i]
    }
    
    func (h *heapInt) Peek() interface{} {
    	
    	return (*h)[0]
    }
    
    func (h *heapInt) Push(x interface{}) {
    	*h = append(*h, x.(int))
    }
    
    func (h *heapInt) Pop() interface{} {
    	length := len(*h)
    	res := (*h)[length - 1]
    
    	*h = (*h)[0 : length - 1]
    	return res
    }
    
    type reverse struct {
        PeekHeap
    }
    
    func (r reverse) Less(i, j int) bool {
    	return r.PeekHeap.Less(j, i)
    }
    
    func Reverse(data PeekHeap) PeekHeap {
    	return &reverse{data}
    }
    
    type MedianFinder struct {
    	maxHeap PeekHeap
    	minHeap PeekHeap
    }
    
    
    /** initialize your data structure here. */
    func Constructor() MedianFinder {
    	minHeap := &heapInt{}
    	maxHeap := Reverse(&heapInt{})
    	heap.Init(minHeap)
    	heap.Init(maxHeap)
    	return MedianFinder{maxHeap, minHeap}
    }
    
    func (this *MedianFinder) AddNum(num int) {
    	if this.maxHeap.Len() == 0 || num <= this.maxHeap.Peek().(int) {
    		heap.Push(this.maxHeap, num)
    	} else {
    		heap.Push(this.minHeap, num)
    	}
    
    	if this.minHeap.Len() > this.maxHeap.Len() {
    		heap.Push(this.maxHeap, heap.Pop(this.minHeap))
    	} else if this.maxHeap.Len() - this.minHeap.Len() > 1 {
    		heap.Push(this.minHeap, heap.Pop(this.maxHeap))
    	}
    }
    
    func (this *MedianFinder) FindMedian() float64 {
         //fmt.Println(this.maxHeap.Len(), this.minHeap.Len())
        //fmt.Println(this.maxHeap.Peek().(int), this.minHeap.Peek().(int))
    	if this.maxHeap.Len() == this.minHeap.Len() {
    		return (float64(this.maxHeap.Peek().(int)) + float64(this.minHeap.Peek().(int))) / 2.0
    	} else {
    		return float64(this.maxHeap.Peek().(int))
    	}
    }
    
    
    /**
     * Your MedianFinder object will be instantiated and called as such:
     * obj := Constructor();
     * obj.AddNum(num);
     * param_2 := obj.FindMedian();
     */
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.