本文共 5269 字，大约阅读时间需要 17 分钟。

数据结构之二叉堆

一、什么是二叉堆

二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。

二叉堆有两种：最大堆和最小堆。

最大堆：父结点的键值总是大于或等于任何一个子节点的键值；

最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

二、二叉堆的基本操作

1.插入

假设在最大堆[90,80,70,60,40,30,20,10,50]种插入85，需要执行的步骤如下：

插入分为两步：

(1).将data添加到表尾

/*	 * 将data插入到二叉堆中	 */	public void insert(T data) {		int size = mHeap.size();		mHeap.add(data); // 将"数组"插在表尾		filterup(size); // 向上调整堆	}

(2).调用向上调整算法

/*	 * 最大堆的向上调整算法(从start开始向上直到0，调整堆)	 *	 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。	 * 	 * 传入当前节点的索引start，然后(start-1)/2拿到它父节点的索引，将当前start节点记下来 比较它与父节点的大小，	 * 若大于父节点，先将start节点值set为父节点的值，然后两个指针同步上移，（把父节点赋值给当前节点，父节点上移找父节点） 直到走到不满足start>0	 * 将记下来的值set到新start处 参数说明： start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)	 */	protected void filterup(int start) {		int c = start; // 当前节点(current)的位置		int p = (c - 1) / 2; // 父(parent)结点的位置		T tmp = mHeap.get(c); // 当前节点(current)的大小		while (c > 0) {			int cmp = mHeap.get(p).compareTo(tmp);			if (cmp >= 0)				break;			else {				mHeap.set(c, mHeap.get(p));				c = p;				p = (p - 1) / 2;			}		}		mHeap.set(c, tmp);	}

2.删除

也是分为两步：

/*	 * 删除最大堆中的data	 *	 * 先将data删除，将最后一个元素放上来， 调用向下调算法	 *	 *	 * 返回值： 0，成功 -1，失败	 */	public int remove(T data) {		if (mHeap.isEmpty()) {			return -1;		}		int index = mHeap.indexOf(data);		if (index == -1) {			return -1;		}		int size = mHeap.size();		mHeap.set(index, mHeap.get(size - 1));// size-1索引处的值是最后一个元素，将这个元素放到删除元素处		mHeap.remove(size - 1);// 把最后一个元素删除，然后调用向下调整算法		filterdown(index, mHeap.size() - 1);		return 0;	}

（2）调用向下调整算法

/*	 * 最大堆的向下调整算法	 *	 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。	 *	 * 从start位置，向下找它最大的孩子，与它自己比较 如果孩子大于它，将此孩子值set到start位置 start下移 反复执行直至条件不满足	 * 最后把初始start处的值set到新位置	 *	 *	 * 参数说明： start -- 被下调节点的起始位置(一般为0，表示从第1个开始) end -- 截至范围(一般为数组中最后一个元素的索引)	 */	protected void filterdown(int start, int end) {		int c = start; // 当前(current)节点的位置		int l = 2 * c + 1; // 左(left)孩子的位置		T tmp = mHeap.get(c); // 当前(current)节点的大小		while (l <= end) {			int cmp = mHeap.get(l).compareTo(mHeap.get(l + 1)); // "l"是左孩子，"l+1"是右孩子			if (l < end && cmp < 0)				l++; // 左右两孩子中选择较大者，即mHeap[l+1]			cmp = tmp.compareTo(mHeap.get(l));			if (cmp >= 0)				break; // 调整结束			else {				mHeap.set(c, mHeap.get(l));				c = l;				l = 2 * l + 1;			}		}		mHeap.set(c, tmp);	}

下面是完整代码：

package priv.qcy.heap;import java.util.ArrayList;import java.util.List;public class MaxHeap
   
    > {	private List
    
      mHeap; // 队列(实际上是动态数组ArrayList的实例)	public MaxHeap() {		this.mHeap = new ArrayList
     
      ();	}	/*	 * 最大堆的向下调整算法	 *	 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。	 *	 * 从start位置，向下找它最大的孩子，与它自己比较 如果孩子大于它，将此孩子值set到start位置 start下移 反复执行直至条件不满足	 * 最后把初始start处的值set到新位置	 *	 *	 * 参数说明： start -- 被下调节点的起始位置(一般为0，表示从第1个开始) end -- 截至范围(一般为数组中最后一个元素的索引)	 */	protected void filterdown(int start, int end) {		int c = start; // 当前(current)节点的位置		int l = 2 * c + 1; // 左(left)孩子的位置		T tmp = mHeap.get(c); // 当前(current)节点的大小		while (l <= end) {			int cmp = mHeap.get(l).compareTo(mHeap.get(l + 1)); // "l"是左孩子，"l+1"是右孩子			if (l < end && cmp < 0)				l++; // 左右两孩子中选择较大者，即mHeap[l+1]			cmp = tmp.compareTo(mHeap.get(l));			if (cmp >= 0)				break; // 调整结束			else {				mHeap.set(c, mHeap.get(l));				c = l;				l = 2 * l + 1;			}		}		mHeap.set(c, tmp);	}	/*	 * 删除最大堆中的data	 *	 * 先将data删除，将最后一个元素放上来， 调用向下调算法	 *	 *	 * 返回值： 0，成功 -1，失败	 */	public int remove(T data) {		if (mHeap.isEmpty()) {			return -1;		}		int index = mHeap.indexOf(data);		if (index == -1) {			return -1;		}		int size = mHeap.size();		mHeap.set(index, mHeap.get(size - 1));// size-1索引处的值是最后一个元素，将这个元素放到删除元素处		mHeap.remove(size - 1);// 把最后一个元素删除，然后调用向下调整算法		filterdown(index, mHeap.size() - 1);		return 0;	}		/*	 * 将data插入到二叉堆中	 */	public void insert(T data) {		int size = mHeap.size();		mHeap.add(data); // 将"数组"插在表尾		filterup(size); // 向上调整堆	}	/*	 * 最大堆的向上调整算法(从start开始向上直到0，调整堆)	 *	 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。	 * 	 * 传入当前节点的索引start，然后(start-1)/2拿到它父节点的索引，将当前start节点记下来 比较它与父节点的大小，	 * 若大于父节点，先将start节点值set为父节点的值，然后两个指针同步上移，（把父节点赋值给当前节点，父节点上移找父节点） 直到走到不满足start>0	 * 将记下来的值set到新start处 参数说明： start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)	 */	protected void filterup(int start) {		int c = start; // 当前节点(current)的位置		int p = (c - 1) / 2; // 父(parent)结点的位置		T tmp = mHeap.get(c); // 当前节点(current)的大小		while (c > 0) {			int cmp = mHeap.get(p).compareTo(tmp);			if (cmp >= 0)				break;			else {				mHeap.set(c, mHeap.get(p));				c = p;				p = (p - 1) / 2;			}		}		mHeap.set(c, tmp);	}	@Override	public String toString() {		StringBuilder sb = new StringBuilder();		for (int i = 0; i < mHeap.size(); i++)			sb.append(mHeap.get(i) + " ");		return sb.toString();	}	public static void main(String[] args) {		int i;		int a[] = { 10, 40, 30, 60, 90, 70, 20, 50, 80 };		MaxHeap
      
        tree = new MaxHeap
       
        ();		System.out.printf("== 依次添加: ");		for (i = 0; i < a.length; i++) {			System.out.printf("%d ", a[i]);			tree.insert(a[i]);		}		System.out.printf("\n== 最 大 堆: %s", tree);		i = 85;		tree.insert(i);		System.out.printf("\n== 添加元素: %d", i);		System.out.printf("\n== 最 大 堆: %s", tree);		i = 90;		tree.remove(i);		System.out.printf("\n== 删除元素: %d", i);		System.out.printf("\n== 最 大 堆: %s", tree);		System.out.printf("\n");	}}
       
      
     
    
   

运行结果：

emmmmm仅供个人复习所用，如有错误欢迎指正！

转载地址：http://ninwi.baihongyu.com/