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

在优先级队列一中，我们发现无论采取无序法还是有序法，时间复杂度永远都是O(N)，所以能不能有一种方法能够达到插入和删除最大元素的时间复杂度都为O(logN)?

在这种情况下，大师们发明了二叉堆（binary heap）。也是整个优先级队列的核心，也是之后堆排序的核心。

二叉堆的设计和前面所讲的的数组稍有不同，因为这里是要用数组来模拟二叉树，而二叉树的根节点为1，所以我们将数组的首个元素置空，从第二个元素也就是key[1]开始放节点。所以我们建立的数组的大小就要相应加1。

	PriorityQueue(int capacity) {
		key = new int[capacity+1];
	}

即把x先放到数组的最后一位，即堆里面的最右下方，然后将这个数往上游，直到合适的位置就结束。

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

如何在数组中寻找父节点和子节点呢？这里就是二叉堆最牛的地方，因为二叉堆是一颗完全二叉树，所以必定有左子节点=父节点*2，右子节点等于父节点*2+1。所以父节点等于子节点/2。

所以是k==1||more(key[k/2]，key[k])的时候跳出循环即可。

	public void swim(int k) {
		while (k > 1 && more(key[k],key[k / 2])) {
			exchange(k,k / 2);
			k = k / 2;
		}
	}

因为删除的元素一定是最大的，所以只需要把最顶上的元素交换到最右下方（即数组的第二位元素和最后一位元素交换），然后删掉最后一位元素即可，

	public int deleteMax() {
		if(isEmpty())
			return 0;
		int max = key[1];
		exchange(1,N--);
		sink(1);
		key[N+1] = 0;
		return max;
	}

然后把交换到最顶上的元素往下沉，直到沉到最后一位或者沉到比子节点大就算沉到位了。即more(当前节点，子节点)，结束。

我们用j来代表左子节点（目标节点）j=2k,当然2k是需要小于等于N的，k为当前节点，只要more(key[k],key[j])。说明沉到位了，跳出循环即可。

如果没有达到目标，继续下滑，至于是滑向左子结点还是右子节点，当然，常识告诉我们，肯定选择滑向大得节点。即if(j<N&&more(k[j+1],k[j])) 那么就j++吧，然后交换j和k。

当然，这里要求j<N，如果j已经等于N了就没什么悬念了，说明目标节点已经到最右子树位（数组的最后元素位），不能在往后走了，直接交换j和N即可。

交换完后，当前节点k从目标节点开始继续寻找下一个目标节点。

	public void sink(int k) {
		while (2 * k <= N) {
			int j = 2 * k;
			if (j < N && more(key[j + 1],key[j]))
				j++;
			if (more(key[k],key[j]))
				break;
			
			exchange(j,k);
			k = j;
		}
	}

（编辑：李大同）

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