我需要计算中位数。有人告诉我,在这个特定的应用程序中,最好的方法是使用优先级队列。我不知道如何继续。我真的很感激任何帮助。
这应该可以。维护两个大于和小于中值的数字的优先级队列。在两个队列之间移动值,使它们保持平衡或接近平衡,并根据优先级队列的顶部值定义中值。
#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 的代码产生未定义的行为。你可以参考这个。综上所述,当您在空优先级队列上调用 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 的相同。
#包括
使用命名空间 std;
#定义尺寸 5
类队列{
私人:
int arr[size];
int rear, front;
公众:
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;
}