加载中…
个人资料
裴大帅2020
裴大帅2020
  • 博客等级:
  • 博客积分:0
  • 博客访问:698,928
  • 关注人气:63
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

Ordering结合PriorityQueue只有一个参数的使用案例

(2019-10-23 16:03:07)
标签:

ordering

priorityqueue

分类: IT技术
import scala.collection.mutable

// 随时找到数据流中的中位数
object MedianHolder {
val smallOrder = Ordering[Int].reverse // 大到小顺序
val bigOrder = Ordering[Int] // 小到大顺序

val smallHeap = mutable.PriorityQueue[Int]()(smallOrder) // 较大半部分
val bigHeap = mutable.PriorityQueue[Int]()(bigOrder) // 较小半部分

def main(args: Array[String]) = {
addNumber(1)
addNumber(2)
addNumber(3)
println(getMedian())
addNumber(4)
println(getMedian())
addNumber(5)
println(getMedian())
}

// 查找中位数
def getMedian(): Int = {
if(bigHeap.isEmpty) return -1
if(bigHeap.size == smallHeap.size) return (bigHeap.head + smallHeap.head) / 2
if(bigHeap.size > smallHeap.size){
return bigHeap.head
}else{
return smallHeap.head
}
}

// 往两个堆中添加元素
def addNumber(num: Int) = {
if(bigHeap.isEmpty || num < bigHeap.head){
bigHeap.enqueue(num)
}else{
smallHeap.enqueue(num)
}

if(bigHeap.size > smallHeap.size + 1){
val elem = bigHeap.dequeue()
smallHeap.enqueue(elem)
}else if(bigHeap.size + 1 < smallHeap.size){
val elem = smallHeap.dequeue()
bigHeap.enqueue(elem)
}
}

}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有