欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

左式堆学习

程序员文章站 2024-01-19 13:01:46
...

今天学习了一下左式堆,总结一下。

一、左式堆定义:

具有,如下性质

1、父节点属性值小于子节点属性值;

2、堆中的任何节点,其左儿子的零路径长>=右儿子的零路径长;

的二叉树。

注:零路径长(npl)是指:从一个节点X开始到一个不具有两个儿子的Y节点的最短路径的长,可以看出有0个或者一个儿子的节点的npl=0,并且定义npl(null)=-1;

二、左式对的节点定义:

class Node<T> {

		// 元素
		T element;
		// 左节点
		Node<T> left;
		// 右节点
		Node<T> right;
		// 零路径长
		int npl;

		public Node(T element) {
			this(element, null, null);
		}

		public Node(T element, Node<T> left, Node<T> right) {
			this.element = element;
			this.left = left;
			this.right = right;
			this.npl = 0;
		}
	}

 三、左式对的操作:

对于左式堆主要操作是“合并”,因为合并会破坏左式堆的特性,而insert、delete等操作,都会涉及到堆的合并,例如:delete根节点,相当于将一棵树边为了两个树,在将两棵树合并为一棵树。这里我们使用了一种递归的思想,若h1,h2本身是左式堆,则其子树也一定是左式堆,其子树的子树也一定是左式堆,一直退到树的每个叶子节点,都符合这个规则,那么我们合并时就可以从反方向思考,先形成一个个的小左式堆,然后在形成一棵大的左式堆。

四、左式堆定义代码:

public class LeftistHeap<T extends Comparable<T>> {
	// 左式堆节点定义
	private static class Node<T> {

		// 元素
		T element;
		// 左节点
		Node<T> left;
		// 右节点
		Node<T> right;
		// 零路径长
		int npl;

		public Node(T element) {
			this(element, null, null);
		}

		public Node(T element, Node<T> left, Node<T> right) {
			this.element = element;
			this.left = left;
			this.right = right;
			this.npl = 0;
		}
	}

	private Node<T> root;

	public LeftistHeap() {
		this.root = null;
	}

	// 合并兩個左式堆
	public void merge(LeftistHeap<T> rhs) {
		if (rhs == null)
			return;
		root = merge(root, rhs.root);
		rhs.root = null;
	}

	// 向左式堆中添加元素
	public void insert(T element) {
		root = merge(new Node<T>(element), root);
	}

	// 找寻左式堆中最小节点
	public T findMin() {
		if (isEmpty())
			return null;
		return root.element;
	}

	/**
	 * 删除堆中最小节点,由于堆的最小节点就在根上,所以可以直接删除,但是删除根后,需要在将左右子树合并
	 * 
	 * @return
	 */
	public T deleteMin() {
		if (isEmpty())
			return null;
		T minItem = root.element;
		root = merge(root.left, root.right);
		return minItem;
	}

	// 判断左式堆是否为空
	public boolean isEmpty() {
		return root == null;
	}

	// 将左式堆设置为空堆
	public void makeEmpty() {
		this.root = null;
	}

	/**
	 * 1、若第一个根节点为空,则返回第二个根节点; 2、若第一个不为空第二个为空,则返回第一个根节点;
	 * 3、一、二节点都不为空时,判断那个是根较小的节点,将根较小的节点作为第一个参数传递给merge1方法
	 * 
	 * @param h1
	 * @param h2
	 * @return
	 */
	private Node<T> merge(Node<T> h1, Node<T> h2) {
		if (h1 == null)
			return h2;
		if (h2 == null)
			return h1;
		if (h1.element.compareTo(h2.element) < 0) {
			return merge1(h1, h2);
		} else {
			return merge1(h2, h1);
		}
	}

	/**
	 * 将根节点较大的树合并到根节点较小的树上去: 1、若根节点较小的树无左子树,则将根节点较大的树作为其左子树
	 * 2、若根节点较小的树有左子树,则将根节点较大的树和根节点较小的树的右子树合并,作为根节点较小的树的右子树
	 * 3、若左子树的零路径长小于右子树的零路径长,则交换左右子树 4、根节点较小的树的零路径长修正为其右子树的零路径长度+1
	 * 
	 * @param h1
	 * @param h2
	 * @return
	 */
	private Node<T> merge1(Node<T> h1, Node<T> h2) {
		if (h1.left == null)
			h1.left = h2;
		else {
			h1.right = merge(h1.right, h2);
			if (h1.left.npl < h1.right.npl)
				swapChildren(h1);
			h1.npl = h1.right.npl + 1;
		}
		return h1;
	}

	// 交换两个子树
	private void swapChildren(Node<T> t) {
		Node<T> tmp = t.left;
		t.left = t.right;
		t.right = tmp;
	}
}

 

参考资料:《数据结构与算法分析--java语言描述》Mark Allen Weiss著

相关标签: 算法 数据结构