使用优先队列计算中位数

Question

我需要计算中位数。被告知在这个特定应用程序中，使用优先队列是最好的方法。我不知道如何继续下去。真的很感激任何帮助。

- Zechariah Schneider

---

std::priority_queue<> - WhozCraig

Answer 1

这应该可以解决问题。维护两个优先队列，一个存储大于中位数的数字，另一个存储小于中位数的数字。在两个队列之间移动值，使它们保持平衡或接近平衡，并且基于优先队列的顶部值定义中位数。

#include <queue>
#include <vector>
#include <functional>
#include <limits>
#include <iostream>

template<class T>
class RunningMedian {
 private:
  //Values greater than the median sorted so that smallest is on top
  std::priority_queue<T, std::vector<T>, std::greater<T> > upper;
  //Values smaller than the median sorted so that greatest is on top
  std::priority_queue<T, std::vector<T>, std::less<T> > lower;

 public:
  RunningMedian(){
    //Seed the queues
    upper.push(std::numeric_limits<T>::max());
    lower.push (std::numeric_limits<T>::min());
  }
  void push(T val){
    //Add number to the property queue

    //If number is greater than the least upper number, it is an upper number
    if(val>=upper.top())
      upper.push(val);
    else //Otherwise it is a lower number
      lower.push(val);

    //Rebalance
    //If the queues sizes differ by 2, they need to be rebalanced so that they
    //differ by 1.
    if(upper.size()-lower.size()==2){ //Upper queue is larger
      lower.push(upper.top());        //Move value from upper to lower
      upper.pop();                    //Remove same value from upper
    } else if(lower.size()-upper.size()==2){ //Lower queue is larger
      upper.push(lower.top());               //Move value from lower to upper
      lower.pop();                           //Remove same value
    }
  }

  T getMedian() const {
    if(upper.size()==lower.size())               //Upper and lower are same size
      return(upper.top()+lower.top())/((T)2.0);  //so median is average of least upper and greatest lower
    else if(upper.size()>lower.size())           //Upper size greater
      return upper.top();
    else                                         //Lower size greater
      return lower.top();
  }
};

int main(){
  RunningMedian<int> rm;
  rm.push(10);
  rm.push(3);
  rm.push(1);
  rm.push(20);
  rm.push(5);
  rm.push(8);
  rm.push(-1);
  std::cout<<rm.getMedian()<<std::endl; //Gives 5
}

- Richard

---

没问题。非常感谢！ - Zechariah Schneider

不客气。如果您认为这回答了您的问题，可以自由地接受这个答案。否则，请让我知道您问题中还有哪些部分没有得到解答。 - Richard

Answer 2

@Richard的代码会产生未定义行为。您可以参考this。总之，当您在空优先级队列上调用PQ.top时，将会产生未定义行为。

我将使用取反方法来使原始上半部分中最小的数字成为最大值。

class FindMedian{
    /* the largest number in lower half */
    std::priority_queue<int> small;
    /* the largest negative number in upper half */
    std::priority_queue<int> large;
    public:
        void add(int num) {
            small.push(num);
            large.push(-small.top());
            /*In order to rearrange small.top() later
            * e.g., assume that small = {2} and large = {-4}
            * Now, we want to push 5 into the small, so small = {5, 2} and 
            * large = {-4, -5}
            * However, the small.top() is larger than (-large.top()).
            * Thus, we need to rearrange them and first pop out in small container
            */
            small.pop();
            //we ensure that the size of small is equal to or one more than large
            if (small.size() < large.size()) {
                small.push(-large.top());
                large.pop();
            }

        }
        double findMedian() {
            return small.size() > large.size() ?
               //if total size is odd or if total size is even 
                small.top() : ((small.top() - large.top()) >> 1);
        }
    };

基本上，代码背后的原理与Richard的相同。

- asdfjoe

Answer 3

#include <iostream>

using namespace std;

#define size 5

class Queue {

private:

    int arr[size];

    int rear, front;

public:

    Queue()
    {
        front = -1;
        rear = -1;
    }

    bool isfull()
    {
        return (rear == size - 1);
    }

    bool empty()
    {
        return (front == -1 && rear == -1);
    }

    void enqueue(int temp)
    {
        if (isfull())
        {
            cout << "Queue Overflow" << endl;
        }
        if (empty())
        {
            front = 0;
            rear = 0;
        }
        else {
            rear++;
        }
        arr[rear] = temp;
    }

    void dequeue()
    {
        if (empty())
        {
            cout << "Queue Underflow" << endl;
        }
        if (front==rear)
        {
            front = -1;
            rear = -1;
        }
        else {
            front++;
        }
    }

    int peek()
    {
        if (empty())
        {
            cout << "Queue is empty" << endl;
        }
        return arr[front];
    }

    void display()
    {
        if (empty())
        {
            cout << "Queue is empty" << endl;
        }
        cout << "Queue Element=" << endl;
        for (int i = front; i <= rear; i++)
        {
            cout << arr[i] << endl;
        }
        cout << endl;
    }

    //Find the median of the Queue
    int median()
    {
        int median;
        if (empty())
        {
            cout << "Queue is empty" << endl;
            return 0;
        }
        median = arr[size / 2];
        return median;
        
    }

};

int main()
{

    Queue q;

    cout << "Insert the elements into the Queue=" << endl;

    q.enqueue(1);

    q.enqueue(2);

    q.enqueue(3);

    q.enqueue(4);

    q.enqueue(5);

    q.display();

    cout << "Median value of Queue is=" << q.median() << endl;

    return 0;

}

- Ahmed Raza