priority_queue删除

在STL中，priority_queue的底层实现是利用堆。

priority_queue没办法实现O(1)复杂度进行任意元素的删除操作，可用利用两个priority_queue来实现。具体代码如下所示。

push()  给队列中插入元素。

pop()    弹出队首元素。

top()     显示队首元素。

empty()  判断队列是否为空。

erase()  删除队列中任意元素，仅仅是任意元素（即参数为队列中元素）。

#include <queue>

typedef struct PRIORITY_QUEUE {
	struct DTYPE {
		int x;
		int y;
		int z;
		bool operator == (const DTYPE& temp) const {
			return this->x == temp.x && this->y == temp.y && this->z == temp.z;
		}
	};
	struct COMP	{
		bool operator ()(const DTYPE& a_ele, const DTYPE& b_ele) {
			if (a_ele.x == b_ele.x) {
				return a_ele.y > b_ele.y;
			}
			return a_ele.x < b_ele.x;
		}
	};

	priority_queue<DTYPE, vector<DTYPE>, COMP> save_queue, del_queue;
	void push(const DTYPE& elememt) {
		save_queue.emplace(elememt);
	}

	bool empty() {
		return save_queue.empty();
	}

	DTYPE top() {
		while (!del_queue.empty() && del_queue.top() == save_queue.top()) {
			del_queue.pop();
			save_queue.pop();
		}
		DTYPE zero = { NULL, NULL, NULL };
		return save_queue.empty() ? zero : save_queue.top();
	}

	void pop() {
		while (!del_queue.empty() && save_queue.top() == del_queue.top()) {
			save_queue.pop();
			del_queue.pop();
		}
		if (!save_queue.empty()) {
			save_queue.pop();
		}
	}

	void erase(const DTYPE& element) {
		del_queue.push(element);
	}

	void show(const DTYPE& temp) const {
		cout << temp.x << " " << temp.y << " " << temp.z << " " << endl;
	}

}priqueue;

int main() {
	priqueue p_queue;;

	p_queue.push({2,1,3});
	p_queue.push({ 255,43,3 });
	p_queue.push({ 23,1,56 });
	p_queue.push({ 212,5,3 });
	p_queue.push({ 12,234,234 });
	p_queue.push({ 27644,34556,34 });

	p_queue.erase({ 212,5,3 });

	p_queue.show(p_queue.top());
	p_queue.pop();
	p_queue.show(p_queue.top());
	p_queue.pop();
	p_queue.show(p_queue.top());
	p_queue.pop();
	p_queue.show(p_queue.top());
	p_queue.pop();
	p_queue.show(p_queue.top());
	p_queue.pop();

	return 0;
}