高效堆结构实现(pairing_heap)

[eiclpy]

普通堆所有操作复杂度O(logn)，pairing_heap除pop操作复杂度O(logn)，其余操作复杂度O(1)。

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

struct pheap
{
	struct node
	{
		node *fa, *l, *r; //父节点指针，左右子节点指针
		int k;			  //节点数据
		node(int key)
		{
			fa = l = r = 0;
			k = key;
		}
	} * root; //根节点指针
	pheap() { root = 0; }
#define merge(u, v) (u->k > v->k ? _merge(u, v) : _merge(v, u))
	node *_merge(node *u, node *v) //将子树v合并到子树u中
	{
		(v->r = u->l) != 0 ? v->r->fa = v : 0;
		return u->l = v, v->fa = u;
	}
	node *combine(node *rt) //合并rt及所有右子树为二叉堆
	{
		if (rt->r == 0)
			return rt;
		static node *arr[100000];
		int j = -1;
		for (; rt != 0; rt = rt->r)
			rt->fa->r = 0, arr[++j] = rt;
		for (int i = 0; i < j; i += 2)
			arr[i] = merge(arr[i], arr[i | 1]);
		for (j & 1 != 0 ? j ^= 1 : 0; j > 0; j -= 2)
			arr[j - 2] = merge(arr[j - 2], arr[j]);
		return arr[0];
	}
	node *push(int x) //将节点加入堆
	{
		node *t = new node(x);
		root = root != 0 ? merge(root, t) : t;
		return t;
	}
	void pop() //弹出根节点
	{
		node *t = root;
		root = root->l != 0 ? combine(root->l) : 0;
		delete t;
	}
	void dec(node *x, int k) //减少x节点的值
	{
		x->k = k;
		if (x == root)
			return;
		x->r != 0 ? x->r->fa = x->fa : 0;
		x == x->fa->l ? x->fa->l = x->r : x->fa->r = x->r;
		x->r = 0;
		root = merge(root, x);
	}
};
pheap h;
priority_queue<int> q;
int main()
{
	srand(time(0));
	for (int i = 0; i < 1000000; ++i)
	{
		int x = rand() << 15 | rand();
		h.push(x);
		q.push(x);
		if (h.root->k != q.top())
			puts("WA");
		x = rand() << 15 | rand();
		h.push(x);
		q.push(x);
		if (h.root->k != q.top())
			puts("WA");
		h.pop();
		q.pop();
	}
	return 0;
}

[eiclpy]

普通堆

#include <iostream>
using namespace std;
int h[100000] = {-2147283647}, siz = 0;
int loc[100000];
void push(int x)
{
	int i, f;
	for (i = ++siz; x < h[f = i >> 1]; i = f)
		loc[h[i] = h[f]] = i;
	loc[h[i] = x] = i;
}
int pop()
{
	int i, c, ret = h[1], p = h[siz--];
	for (i = 1; (c = i << 1) <= siz; i = c)
	{
		(c | 1) <= siz &&h[c | 1] < h[c] ? c |= 1 : 0;
		if (h[c] < p)
			loc[h[i] = h[c]] = i;
		else
			break;
	}
	loc[h[i] = p] = i;
	return ret;
}
int main()
{
	push(666);
	cout << h[1] << endl;
	push(999);
	cout << h[1] << endl;
	push(233);
	cout << h[1] << endl;
	push(456);
	cout << h[1] << endl;
	push(31);
	cout << h[1] << endl;
	push(987);
	cout << h[1] << endl;
	cout << pop() << endl;
	cout << pop() << endl;
	cout << pop() << endl;
	cout << pop() << endl;
	cout << pop() << endl;
	cout << pop() << endl;
	return 0;
}