README
¶
MedianHeap 
Implementation of the Running Median algorithm. The provided operations are for adding elements and retrieving the median. Time complexity for updating the median is O(log N), retrieving it – O(1).
Install
$ go get github.com/pietv/medianheap
Documentation
¶
Overview ¶
Package medianheap implements a running median algorithm for integers using 2 heaps. The provided operations are for adding elements and retrieving the median.
The time complexity for updating the median is O(logN), retrieving it O(1).
The median value is equal to the k/2th element of a sorted array of size k if k is odd, or (k/2)-1th element if size is even. No averages are computed.
Here is equivalent code (with time complexity O(N logN)):
sort.Ints(A)
if len(A) % 2 == 0 {
m = A[(len(A)-1) / 2]
} else {
m = A[len(A) / 2]
}
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type IntMedianHeap ¶
type IntMedianHeap struct {
// contains filtered or unexported fields
}
An IntMedianHeap maintains references to added elements.
Example ¶
package main
import (
"fmt"
"github.com/pietv/medianheap"
)
func main() {
h := medianheap.New()
h.Add(-1)
h.Add(0)
h.Add(1)
fmt.Println(h.Median())
}
Output: 0
func (IntMedianHeap) Add ¶
func (h IntMedianHeap) Add(n interface{})
Add inserts an integer into the medianheap.
func (IntMedianHeap) Median ¶
func (h IntMedianHeap) Median() int
Median returns a median value for added elements.
func (IntMedianHeap) Update ¶
func (h IntMedianHeap) Update(n interface{}) int
Update adds an element to the heap and returns the running median. It is a utility concatenation of Add(), followed by Median().
Source Files