如何将c++ 优先队列求中位数代码修改为模板类?

问题描述:

#include <stdio.h>
#include <queue>
class MedianFinder {
public:
        MedianFinder() {
        }
        void addNum(int num) {
        if (big_queue.empty()){
	big_queue.push(num);
	return;
	}
        if (big_queue.size() == small_queue.size()){
                if (num < big_queue.top()){
	        big_queue.push(num);
	        }
	else{
        small_queue.push(num);
        }
        }
        else if(big_queue.size() > small_queue.size()){
        	if (num > big_queue.top()){
	        	small_queue.push(num);
	        }
	        else{
        		small_queue.push(big_queue.top());
        		big_queue.pop();
        		big_queue.push(num);
        	}
        }
        else if(big_queue.size() < small_queue.size()){
        	if (num < small_queue.top()){
	                big_queue.push(num);
	        }
	        else{
        	        big_queue.push(small_queue.top());
        	        small_queue.pop();
        	        small_queue.push(num);
        	}
                }
        }
        double findMedian(){
    	if (big_queue.size() == small_queue.size()){
        	return (big_queue.top() + small_queue.top()) / 2;
        }
        else if (big_queue.size() > small_queue.size()){
        	return big_queue.top();
        }
        return small_queue.top();
    }
private:
	std::priority_queue<double> big_queue;
	std::priority_queue<double, std::vector<double>,
					std::greater<double>> small_queue;
};
int main(){
	MedianFinder M;
	int test[] = {6, 10, 1, 7, 99, 4, 33};
	for (int i = 0; i < 7; i++){
		M.addNum(test[i]);
		printf("%lf\n", M.findMedian());
	}
	return 0;
}

#include<iostream>
#include<queue>

template <typename T>
class MedianFinder {
private:
	std::priority_queue<T> big_queue;
	std::priority_queue<T, std::vector<T>,
		std::greater<T>> small_queue;
public:
	MedianFinder(){}
	template <typename U>
	void addNum(U& num) {
		if (big_queue.empty()) {
			big_queue.push(num);
			return;
		}
		if (big_queue.size() == small_queue.size()) {
			if (num < big_queue.top())
				big_queue.push(num);
			else small_queue.push(num);
		}
		else if (big_queue.size() > small_queue.size()) {
			if (num > big_queue.top())
				small_queue.push(num);
			else {
				small_queue.push(big_queue.top());
				big_queue.pop();
				big_queue.push(num);
			}
		}
		else if (big_queue.size() < small_queue.size()) {
			if (num < small_queue.top())
				big_queue.push(num);
			else {
				big_queue.push(small_queue.top());
				small_queue.pop();
				small_queue.push(num);
			}
		}
	}
	T  findMedian() {
		if (big_queue.size() == small_queue.size()) return (big_queue.top() + small_queue.top()) / 2;
		else if (big_queue.size() > small_queue.size()) return big_queue.top();
		else return small_queue.top();
	}
};

int main() {
	MedianFinder<double> M;
	int test[] = { 6, 10, 1, 7, 99, 4, 33 };
	for (auto i = 0; i < 7; i++) {
		M.addNum(test[i]);
		printf("%lf\n", M.findMedian());
	}
	return 0;
}

不知道对不对,我也是正在学习。