【数据结构】堆

当删除一个最大的元素也就是堆中的第一个元素，我们首先将堆中的最后一个元素放在放到第一个位置，然后将其与逻辑上的孩子节点比较，如果小于孩子节点，则一直重复与最大的孩子节点交换，直到满足最大堆的条件或者没有孩子，

下滤操作其实也可以理解成是通过插入一个元素将两个小的最大堆合并成一个大的最大堆的过程。具体的可参考下图

创建堆

上述代码中共列举了两种创建最大堆的方法

1.自上而下的上溢

public void createHeap(int[] heapArr) {
		System.arraycopy(heapArr,heapArr.length);
		n = heapArr.length;
		for (int i = 0; i < n; i++) {
			percolateUP(i);
		}
	}

遍历堆中的所有元素，对其进行上溢操作。于是共有n个元素，每个元素上溢的时间复杂度为O(lgn)。因此时间复杂度为T(n)=O(nlgn)

实际上时间复杂度详细的为T(n)= n∑depth(i)，我们知道完全二叉树中超过一半的都是叶子结点深度为O(lgn)，因此T(n)也是nlgn数量级的。

2.自下而上的下滤

public void createHeapFloyd(int [] heapArr){ 
		System.arraycopy(heapArr,heapArr.length);
		n = heapArr.length;
		for (int i = (n - 1) >> 1; i >= 0; i--) {
			percolateDown(i);
		}
	}

下滤操作我们是在删除堆中的最大元素时使用到，其实也可以理解成是将两个小的最大堆合并成一个大的最大堆的过程。

实际上也可以用在建堆操作中。

由于一个完全二叉树的从下标(n-1)/2+1开始就是叶子结点。于是每个叶子结点都可以堪称是一个只有一个元素的最大堆。所以从下标(n-1)/2开始倒序的进行下滤操作。

这种算法的时间复杂度为T(n)=O(n)。实际上，时间复杂度详细的为T(n)= (n-1)/2∑height(i)=O(n)

（编辑：常州站长网）

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