首页 > 其他分享 >使用优先队列寻找中位数

使用优先队列寻找中位数

时间:2023-05-15 21:55:24浏览次数:37  
标签:优先 队列 smallerHalf 中位数 add largerHalf test MedianFinder public

Next, Suppose we would like to invent a new ADT called MedianFinder which is a collection of integers and supports finding the median of the collection.

MedianFinder

add(x); // adds x to the collection of numbers

median(); // returns the median from a collection of numbers Describe

how you could implement this ADT by using existing Java ADTs as building blocks. What’s the most efficient implementation you can come up with?

 

import java.util.Comparator;
import java.util.PriorityQueue;

public class MedianFinder {
    private PriorityQueue<Integer> smallerHalf;
    private PriorityQueue<Integer> largerHalf;

    public MedianFinder() {
        smallerHalf = new PriorityQueue<>(Comparator.reverseOrder());
        largerHalf = new PriorityQueue<>();
    }

    public void add(int x) {
        if (smallerHalf.isEmpty() || x <= smallerHalf.peek()) {
            smallerHalf.add(x);
        } else {
            largerHalf.add(x);
        }
        balanceHeaps();
    }

    private void balanceHeaps() {
        if (smallerHalf.size() > largerHalf.size() + 1) {
            largerHalf.add(smallerHalf.poll());
        } else if (largerHalf.size() > smallerHalf.size()) {
            smallerHalf.add(largerHalf.poll());
        }
    }

    public double median() {
        if (smallerHalf.size() == largerHalf.size()) {
            return (smallerHalf.peek() + largerHalf.peek()) / 2.0;
        } else {
            return smallerHalf.peek();
        }
    }

    public static void main(String[] args) {
        MedianFinder test = new MedianFinder();
        test.add(8);
        test.add(7);
        test.add(6);
        test.add(5);
        test.add(4);
        test.add(3);
        test.add(2);
        double median = test.median();
        System.out.println(median);
    }
}

 

这段代码实现了一个名为 `MedianFinder` 的类,用于找到一系列整数的中位数。在这个类中,我们使用了两个优先队列(`PriorityQueue`),`smallerHalf` 和 `largerHalf` 分别存储较小的一半和较大的一半数字。优先队列可以很方便地获取、添加和删除元素。

1. `public MedianFinder()`: 构造函数,初始化两个优先队列。`smallerHalf` 为大顶堆(通过使用 `Comparator.reverseOrder()` 反转默认的小顶堆),存储较小的一半数字;`largerHalf` 为小顶堆,存储较大的一半数字。

2. `public void add(int x)`: 向集合中添加一个整数 `x`。根据 `x` 和 `smallerHalf` 堆顶元素的大小关系,将 `x` 添加到适当的堆中。然后调用 `balanceHeaps()` 方法来平衡两个堆。

3. `private void balanceHeaps()`: 平衡两个堆的大小。确保两个堆的大小之差不超过 1,这样中位数可以在常数时间内找到。如果 `smallerHalf` 的大小比 `largerHalf` 大 2 个或以上,那么将 `smallerHalf` 的堆顶元素移动到 `largerHalf`。反之,如果 `largerHalf` 的大小比 `smallerHalf` 大,那么将 `largerHalf` 的堆顶元素移动到 `smallerHalf`。

4. `public double median()`: 计算并返回中位数。如果两个堆的大小相同,那么中位数是两个堆顶元素的平均值;如果 `smallerHalf` 的大小比 `largerHalf` 大 1,那么中位数就是 `smallerHalf` 的堆顶元素。

5. `public static void main(String[] args)`: 主方法,用于测试 `MedianFinder` 类的功能。向 `MedianFinder` 对象中添加一些整数,然后计算并打印中位数。

这个实现利用了数据结构优先队列(`PriorityQueue`),可以在对数时间内向集合中添加整数,并在常数时间内找到中位数。这种方法在处理大量数据时非常高效。

标签:优先,队列,smallerHalf,中位数,add,largerHalf,test,MedianFinder,public
From: https://www.cnblogs.com/xuenima/p/17403252.html

相关文章

  • LinkedList作为队列的常用方法
    queue接口中的方法Deque接口中的方法......
  • C语言之环形队列
    一、环形队列的优势环形队列是一种特殊的队列,它可以解决普通队列在使用时空间利用不充分的问题。在环形队列中,当队列满时,队列的尾指针指向队列的起始位置,而不是指向队列的最后一个元素。这样可以在不浪费空间的情况下存储更多的元素。下面我们来详细讲解一下环形队列的......
  • 单调队列算法模板及应用
    文章和代码已经归档至【Github仓库:https://github.com/timerring/algorithms-notes】或者【AIShareLab】回复算法笔记也可获取。队列算法模板//hh表示队头,tt表示队尾intq[N],hh=0,tt=-1;//向队尾插入一个数q[++tt]=x;//从队头弹出一个数hh++;//队头......
  • 洛谷 P8978 「DTOI-4」中位数
    首先考虑二分答案,把原序列变成01序列。那么问题就相当于转换成判断能否在\(k\)次操作内,将序列变成全\(1\)。由于每次操作一定可以做到把\(1\)的个数\(n\)变成\(n'=2n-1\)。因此可以得知操作一定是\(\logn\)级别的。但是这个问题仍然不太好做,很多贪心都是假的。考虑最......
  • 就业内推 | 上市公司招高级网工,HCIE/CCIE证书优先,最高35k
    01中软国际招聘岗位:中高级网络工程师职责描述:1、负责华为数通产品(交换机、路由器、WLAN)、安全产品(防火墙、入侵检测、AntiDDoS硬件设备等)项目售后实施,主要包括设备版本补丁升级、设备安装调测、业务割接上线、项目验收等;2、负责客户网络故障维护处理,设备巡检,版本整改等工作;3、负责......
  • 生产者消费者模型,队列
    主要用来解耦,适合高并发场景、爬虫栈先进后出FILO借助队列实现FIFO队列是安全的不用加锁q.get()阻塞等待或取数据,如果有数据直接获取,如果没有数据就阻塞等待q.put()阻塞或放数据,如果可以放数据继续放,不可以放阻塞等待(IO操作)q.get_nowait()不阻塞,如果有数据直接获......
  • 栈、数组、队列、串(408)
    栈、数组、队列、串栈定义:删除和输入都在同一端的线性表,后进先出顺序栈定义一个线性表,用栈顶指针来控制栈元素的进出。链式栈定义一个头结点,一直指向栈顶,插入新结点时,更新头结点。优点:不会溢出,空间无限共享栈两个栈分别放在栈顶和栈底,存入的数据向中间靠齐。优点:节省存储......
  • Radis--消息队列
    引用:消息队列_哔哩哔哩_bilibili 1.消息队列的概念: 2.消息队列的工作机制: 注:Broker也可主动推送给consumer.3.Redis--MesssageQueue4.Redis--Pub/Sub5.Redis--Stream......
  • 5、栈、队列、优先队列
    内容来自刘宇波老师玩转算法面试1、栈的基础应用20-有效的括号publicstaticbooleanisValid(Strings){Stack<Character>stack=newStack<>();char[]chars=s.toCharArray();for(charc:chars){if(c=='('||c=='{'|......
  • C语言之环形队列
    . 一、环形队列的优势环形队列是一种特殊的队列,它可以解决普通队列在使用时空间利用不充分的问题。在环形队列中,当队列满时,队列的尾指针指向队列的起始位置,而不是指向队列的最后一个元素。这样可以在不浪费空间的情况下存储更多的元素。      下面我们来详细讲解一下环形......