【数据结构】优先级队列（一）

优先级队列的发明主要是用于删除最大数（最小数）

首先定义一个数组用于实现优先级队列，然后定义一个指针N来控制数组里的最后一个元素。

	int[] key;
	int N;

	Pq(int capacity) {
		key = new int[capacity];
	}

然后判空操作。

	public boolean isEmpty() {
		return N == 0;
	}

	public void exchange(int i,int j) {
		int temp = key[i];
		key[i] = key[j];
		key[j] = temp;
	}

	public boolean more(int v,int w) {
		return v > w;
	}

思路1： 无序插入O(1)，删除最大O(N)

插入

	public void insert(int x) {
		key[N++] = x;
	}

删除

	public int deleteMax() {
		if (isEmpty())
			return 0;
		int maxIndex = 0;
		for (int i = 1; i < N; i++) {
			if (more(key[i],key[maxIndex]))
				maxIndex = i;
		}
		exchange(N - 1,maxIndex);
		return key[--N];
	}

思路2：有序插入O(N)，删除最大O(1)

尽管可以采取二分查找的思路来寻找插入的位置，但是由于插入元素后，插入元素的后面所有元素都需要向后移动一位，因此时间复杂度依然为O(N)。

插入

	public void insert(int x) {
		if (isEmpty()) {
			key[N++] = x;
			return;
		}
		int left = 0;
		int right = N - 1;
		while (left <= right) {
			int middle = (left + right) / 2;
			if (key[middle] == x) {
				put(middle,x);
				return;
			}
			if (more(key[middle],x))
				right = middle - 1;
			else
				left = middle + 1;
		}
		put(left,x);
	}
	
	public void put(int middle,int x) {
		for (int i = N - 1; i >= middle; i--)
			key[i + 1] = key[i];
		key[middle] = x;
		N++;
	}

	public int deleteMax() {
		if (isEmpty())
			return 0;
		return key[--N];
	}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!