本文共 3755 字，大约阅读时间需要 12 分钟。

今天学习了上下滤算法，弄懂了优先队列的底层实现原理！

收获：

曾经总是一个 priority_queue 做优先队列的问题，虽然我知道优先队列是二叉堆是实现的，但是从来没有去研究过它的底层实现，今天我把它实现了！经过三次严格的测试，我可以大胆的说，我实现的面向对象的二叉堆是ok的！

My code:

#include 
   
    /* 第三次测试需要算法库头文件： */#include 
    
     using namespace std;typedef int Rank;const int maxn = 1e5 + 5;const Rank NoneEle = 0;inline Rank Parant(Rank i) {    return (i >> 1); }inline bool ParantIsVis(Rank i) {    return 0 != (i >> 1); }inline Rank GetLchild(Rank i) {    return (i << 1); }inline Rank GetRchild(Rank i) {    return ((i << 1) + 1); }template 
     
      class BinaryHeap {   private:	Rank size_;	T* _elem;protected:	T Max(T a_, T b_) {    return a_ > b_ ? a_ : b_; }	/* 如果需要重新定义优先级，请继承此类并重载 < 运算符 */	bool cmp(T a, T b) {    return a < b; }	/* 向上过滤 */	void percolateup(Rank i, T _e) {   		T data = _e; bool isTop = true;		while (ParantIsVis(i)) {   			Rank j = Parant(i);			if (cmp(data, _elem[j])) {   				_elem[i] = data;				isTop = false;				break;			}			// 孩子小于父亲，说明堆序维护成功			_elem[i] = _elem[j];			i = j;		}		if (isTop)	_elem[i] = data;	}	void percolatedown(T e_) {   		T data = e_; Rank r = 1;		while (GetLchild(r) <= size_) {   			Rank j = GetLchild(r);			if (j + 1 <= size_ && _elem[j + 1] > _elem[j]) // 小顶堆				j++;			if (data < _elem[j])				_elem[r] = _elem[j];			else				break;			r = j;		}		_elem[r] = data;	}public:	BinaryHeap() {   		size_ = 0;		_elem = new int[maxn];	}	void Insert(T e) {   		_elem[++size_] = e;		percolateup(size_, e);	}	bool Empty() {   		return (NoneEle == size_);	}	void Pop() {   		if (Empty())	return;		T e = _elem[size_--];		percolatedown(e);	}	T GetTop() {    return _elem[1]; }	Rank GetSize() {    return size_; }};/* 第三次测试的初始化： */const int maxv = 1e5;int n, a[maxn], b[maxn], res[maxn];int main() {   	// 第一次测试：	/* Test code:	int n, a;	BinaryHeap
      
        h;	cin >> n;	for (int i = 0; i < n; i++) {		cin >> a;		h.Insert(a);		cout << h.GetTop() << endl;	}*/	/*	Input		7		5 3 1 7 9 2 10	Output		5		5		5		7		9		9		10	*/	/* 第一次测试成功！*/	//第二次测试：	/*	int n, m, a;	BinaryHeap
       
         h;	cin >> n >> m;	for (int i = 0; i < n; i++) {		cin >> a;		h.Insert(a);	}	for (int i = 0; i < m; i++) {		int cmd;		cin >> cmd;		if (1 == cmd)			h.Pop();		else if (2 == cmd)			cout << h.GetTop() << endl;	}*/	/*	Input:		7 5		5 3 1 7 9 2 10		2 1 2 1 2	Output:		10		9		7	*/	/* 第二次测试成功！ */	// 第三次测试：洛谷OJ P1631 合并序列	cin >> n;	for (int i = 0; i < n; i++)		cin >> a[i];	sort(a, a + n);	for (int i = 0; i < n; i++)		cin >> b[i];	sort(b, b + n);	BinaryHeap
        
          MyHeap; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int sum = a[i] + b[j]; if (MyHeap.GetSize() < n) MyHeap.Insert(sum); else { if (sum < MyHeap.GetTop()) { MyHeap.Pop(); MyHeap.Insert(sum); } else break; } } } for (int i = n - 1; i >= 0; i--) { res[i] = MyHeap.GetTop(); MyHeap.Pop(); } for (int i = 0; i < n; i++) cout << res[i] << ' '; return 0; /* AC啦！第三次测试成功！！！ */}
        
       
      
     
    
   

我的测试用例也在上面，大家可以自行测试

oj测试：

仔细讲解上、下滤算法：

其实就是插入和删除操作不可避免的算法

我们以上滤算法为例，简要讲解

实现方法1：交换法，复杂度O(3*logn)

如果我们需要插入一个元素，由于我们的物理结构是用数组，所以我们的元素必然是插入在数组的尾部，实现复杂度：O(1)

然后我们需要维护堆的有序性！维护有序性，我们可以借助很多数据结构，比如BST、AVL、红黑树等等…… 但是考虑我们的优先队列，只需要维护堆顶即可！并不是整棵树都是有序的，只是保证了每个树及其子树在所在的树形结构里，根节点是整棵树最大的（大顶堆）所以并不需要那么高级的数据结构，只需要一颗完全二叉树就可以了。 我们知道，向完全二叉树中插入节点，是插入在最底层的最右侧！我们要维护堆的有序性，其实就是在维护这个节点与它的父节点的大小顺序。如果我们的这个新插入的节点比父节点大，那么我们这个节点就自然要向上过滤！所以我们就要交换这个节点与父节点的位置，如此下去，一直到它的父节点比它大了，堆的有序性就维护起来了！ 我们晓得，一颗完全二叉树的树高，最高不过：logn，所以我们这个算法的复杂度，整体来说，是O(logn)，但是考虑常数：我们的交换法，每次交换需要三次赋值，所以整个的具体复杂度是：O(3 * logn)

实现方法二：代替法，优化后的复杂度：O(logn + 2)

我们有没有一种更快的方法呢？

我们可以： 第一步：把插入的节点备份：data = NewNode 第二步：如果它的父节点比它小，就把它的父节点赋予给它，然后如此往复 第三步：直到它的父节点比它大了，那么就把data赋予给比它大的父节点的子节点，因为这个子节点与它的子节点是同样的值，所以不会丢失

需要注意的是：

如果我们一致上滤没有发现比它大的节点呢？那么这个节点就自然成为了根节点，所以此时我们直接把data赋予给根节点，因为根节点及其一下的节点已经全部完成了向下替代，所以我们可以放心大胆的去创造新的根节点！

感谢阅读！如果有其他的问题，可以留言！