堆排序详解【java版附流程图】

堆排序详解——java版

近期一直再看别人的源码，无意中发现了他里面使用了堆排序算法，由于以前对于堆的排序问题都只是听过，而没有真正的理解过它和实践过它。于是也借本次机会了解了一下堆排序的算法。其实堆的排序是通过二叉树的形式对元素进行排序，它的规律是：k_i>=k_2i并且k_i>=k_2i+1或者是k_i<=k_2i并且k_i<=k_2i+1，意思就是它的父节点一定大于（小于）它的两个孩子们他们节点，也可以叫大堆排序（小堆排序）下面给出它们的存储结构图：

上面的图是我从百度百科里面截过来的。堆排序是通过数组的形式存储二叉树的信息，那么它就需要计算一个节点的父节点位置，和一个节点的左孩子和右孩子节点的位置，其公式分别为：父=(（i+1）/2)-1 左=(2*（i+1）)-1 右=2*（i+1）。可以通过以上几个公式计算节点的父节点和孩子节点存储在数组是的位置。所以当向堆中添加元素的时候，将堆的大小添加1，用于存储新添加进来的元素，添加元素的初始存储位置是堆尾（注意此时还未将元素添加到堆中，只是表示在当前堆大小加一的位置将要存放新添加进来的元素）。先找到插入元素存放的位置，也就是将插入的元素和当前堆中最后元素的父节点进行比较，如果比该父节点好，则将父节点移动到移动到插入元素初始存储的位置，而新添加元素此时的存储位置是刚才父节点的存储位置，将继续和父节点的父节点进行比较，重复上面的操作，就是调换新添加的存储位置和当前比较的父节点的位置，直到遇到一个父节点比它好或者是到了堆的顶部则停止寻找。这样会导致一个为题，就是假设新添加的元素不是插在堆的尾部，那么将会导致在插入新元素之后的元素就失去了堆排序的特性，就是父节点比孩子节点大（小），所以此时将还要使用一个heapify（i），方法来进行对插入新元素位置以后的元素进行重新进行堆排序。详细的思路可见代码。以下粘贴处我用java实现的堆排序代码：

public class HeapSort {

	private IntArray vertexts;//该数组是存储元素信息
	private FloatArray weight;//存储元素的权重，注意元素的位置和其对应的权重位置要一一对应
	private IntIntHashMap vertMap;//这个记录元素存储的位置
	private boolean Comparemode;//标记比较方式
	private float maxWeight;//最大的值

	/*public static void main(String[] args) {
		HeapSort sort = new HeapSort(true, Float.MAX_VALUE);
		for (int i = 0; i < 100; i++) {
			sort.addElement(i, (float) Math.random());
		}
		for (int i = 0; i < 100; i++) {
			System.out.print("cost :" + sort.getBestCost() + "-->");
			System.out.println(" Node: " + sort.removeBestElemment());
		}
	}*/
/**
 * 
 * @param Comparemode 该参数设定该推排序是取大的还是小的，当为true时，这取大，否则取小
 * @param maxWeight 设定该堆最差的权重，一般设定为无穷大
 */
	public HeapSort(boolean Comparemode, float maxWeight) {
		this.vertexts = new IntArray();
		this.weight = new FloatArray();
		this.vertMap = new IntIntHashMap();
		this.Comparemode = Comparemode;
		this.maxWeight = maxWeight;
	}

	public boolean compared(float w1, float w2) {
		if (this.Comparemode) {
			if (w1 > w2) {
				return true;
			} else {
				return false;
			}
		} else {
			if (w1 < w2) {
				return true;
			} else {
				return false;
			}

		}
	}

	/**
	 * 方法是想堆中添加元素，并将该元素存储在相应的位置
	 * 
	 * @param v
	 *            元素编号
	 * @param w
	 *            元素值
	 */
	public void addElement(int v, float w) {
		int i = this.vertMap.size();
		int k;
		this.vertexts.add(-1);
		this.weight.add(this.maxWeight);
		while (i > 0 && this.compared(w, this.weight.get(this.parent(i)))) {
			k = this.vertexts.get(this.parent(i));
			this.vertexts.set(i, k);
			this.weight.set(i, this.weight.get(this.parent(i)));
			this.vertMap.add(k, i);
			i = this.parent(i);
		}
		this.vertexts.set(i, v);
		this.weight.set(i, w);
		this.vertMap.add(v, i);

	}

	public float getBestCost() {
		return this.weight.get(0);
	}

	public int getBestVertex() {
		return this.vertexts.get(0);
	}
//移出最好的元素并将该最好的发回给用户
	public int removeBestElemment() {
		if (this.vertexts.size() <= 0) {
			return -1;
		}
		int v = this.vertexts.get(0);
		this.vertMap.remove(v);
		this.vertexts.set(0, this.vertexts.get(this.vertexts.size() - 1));
		this.weight.set(0, this.weight.get(this.weight.size() - 1));
		// 此是因为this.vertexts.get(0)的位置还不确定，所以先付-1表示位置不确定
		this.vertMap.add(this.vertexts.get(0), -1);
		this.vertexts.remove(this.vertexts.size() - 1);
		this.weight.remove(this.weight.size() - 1);
		heapify(0);
		return v;
	}
//移除指定的元素
	public boolean removeElement(int v) {
		if (this.vertexts.size() != 0) {
			int i = this.vertMap.get(v);
			if (i == -1)
				return false;
			this.vertexts.set(i, this.vertexts.get(this.vertexts.size() - 1));
			this.weight.set(i, this.weight.get(this.weight.size() - 1));
			this.vertMap.add(this.vertexts.get(i), i);
			this.vertexts.remove(this.vertexts.size() - 1);
			this.weight.remove(this.weight.size() - 1);
			this.vertMap.remove(v);
			if (i <= this.vertexts.size() - 1) {
				heapify(i);
				Propogate(i);
			}
			return true;
		}
		return false;

	}
//更新你指定的元素信息，当你更新的元素不存在时，则执行添加操作
	public int updateElement(int v, int w) {
		int i = this.vertMap.get(v);
		int k;
		if (i < 0) {
			this.addElement(v, w);
		} else {
			float w1 = this.weight.get(v);
			if (this.compared(w1, w)) {
				return 0;
			}
			while (i > 0 && this.compared(w1, this.weight.get(this.parent(i)))) {
				k = this.vertexts.get(this.parent(i));
				this.vertexts.set(i, k);
				this.weight.set(i, this.weight.get(k));
				this.vertMap.add(k, i);
				i = this.parent(i);
			}
			this.vertexts.set(i, v);
			this.weight.set(i, w);
			this.vertMap.add(v, i);
		}
		return 1;
	}
//调整某位置以后的元素，例如上面删除了指定元素好，将要对元素在堆中的位置进行重新的调整，此时就要调用该函数
	private void heapify(int i) {
		int best = 0;
		int count = this.weight.size() - 1;
		int left = left(i);
		int right = right(i);
		if (left <= count
				&& this.compared(this.weight.get(left), this.weight.get(i))) {
			best = left;
		} else {
			best = i;
		}
		if (right <= count
				&& this.compared(this.weight.get(right), this.weight.get(best))) {
			best = right;
		}
		if (best != i) {
			swap(i, best);
			heapify(best);
		}

	}
//上面调整了后面的元素后，那么该位置上面的父节点也要做相应的调整，此时需调用该函数
	private boolean Propogate(int v) {
		int v_parent = parent(v);
		while (v_parent > 0
				&& this.compared(this.weight.get(v_parent), this.weight.get(v))) {
			swap(v, v_parent);
			v = v_parent;
			v_parent = parent(v_parent);
		}
		return false;
	}
//调换操作，将某一位置的元素和某一位置的元素互换
	private void swap(int i, int j) {
		float wi = this.weight.get(i);
		int vi = this.vertexts.get(i);
		this.weight.set(i, this.weight.get(j));
		this.vertexts.set(i, this.vertexts.get(j));

		this.weight.set(j, wi);
		this.vertexts.set(j, vi);
		this.vertMap.add(this.vertexts.get(i), i);
		this.vertMap.add(this.vertexts.get(j), j);

	}
//得到某个位置节点的父节点位置
	private int parent(int i) {
		return ((i + 1) / 2) - 1;
	}
//得到某个节点左孩子位置
	private int left(int i) {
		return (2 * (i + 1)) - 1;
	}
//获得右孩子位置
	private int right(int i) {
		return 2 * (i + 1);
	}
}

该算法实现上我使用了一个包，该包的功能和我们常使用的utils包的功能一样，至不过，他们里面的Map对象没有put和set方法，它们均只有add,在add的时候会判断集合中是否存在相同的key，如果存在这相当于set方法，如果不存在则相当与put方法，相应的jar包我会上传到我在我的资源里面，有兴趣的可以下载下来，不需积分。在实现上额外的添加了一些方法如

public boolean removeElement(int v) 
public boolean compared(float w1, float w2) 
public int updateElement(int v, int w) 

是为了使得程序能够更好的适应各个场合。

下面粘贴处算法的流程图（只有添加元素的流程图，具体的思想参照我上面的代码）：

到此本文结束！谢谢浏览！欢迎评论，指出不足！