ACM-ICPC寒假算法训练2:高级数据结构2:二叉堆的模板类实现!!(好开心!)

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

收获:

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

My code:

#include <iostream>
/* 第三次测试需要算法库头文件: */
#include <algorithm>
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 <typename T>
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<int> 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<int> 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<int> 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测试:洛谷 1631 合并序列

仔细讲解上、下滤算法:

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

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

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

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

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

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

需要注意的是:

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

感谢阅读!如果有其他的问题,可以留言!
上一篇:PTA basic 1059 C语言竞赛 (20 分) c++语言实现(g++)


下一篇:[LeetCode] 1331. Rank Transform of an Array