堆排序

堆排序算法，详细内容参考这里和这里，堆排序除了排序外，还可以用来从一堆数种选取top K（最大/小）个的对象/数字

 

以下是一个最小堆的实现代码，当然，也可以做最大堆用，T实现Comparable接口的时候，compareTo返回值颠倒下就行了。

 

package com.kingdee.gmis;

/**
 * 
 * @author hua_fan
 * 
 */
public class HeapSort<T extends Comparable<? super T>> {

	private int size;
	private Object[] data = new Object[256];

	public HeapSort(T[] data) {
		super();
		this.initHeap(data);

	}

	@SuppressWarnings("unchecked")
	public void initHeap(T[] data) {
		assert data.length >= 1;
		ensureCapacity();
		this.size = data.length;
		System.arraycopy(data, 0, this.data, 0, this.size);
		int startPos = this.getParentIndex(this.size - 1);
		for (int i = startPos; i >= 0; i--) {
			this.shiftdown(i);
		}
	}

	@SuppressWarnings("unchecked")
	public T getHeapTop() {
		return (T) this.data[0];
	}

	/**
	 * 加元素到堆中，但是保持堆 的大小
	 * 
	 * @param value
	 */
	public void addToHeapKeepFixedSize(T value) {
		if (value.compareTo(this.getHeapTop()) > 0) {
			this.data[0] = value;
			this.shiftdown(0);
		}
	}

	/**
	 * 加元素到堆中，同时扩展堆的大小
	 * 
	 * @param value
	 */
	public void addToHeap(T value) {
		this.ensureCapacity();
		this.data[this.size++] = value;
		// this.shiftdown(this.getParentIndex(this.size));
		this.shiftup(this.size - 1);
	}

	private void shiftup(int pos) {
		int parentIdx = this.getParentIndex(pos);
		while (pos != 0
				&& this.getValue(pos).compareTo(this.getValue(parentIdx)) < 0) {
			this.swap(pos, parentIdx);
			pos = parentIdx;
			parentIdx = this.getParentIndex(pos);
		}
	}

	private void ensureCapacity() {
		if (this.data.length <= this.size) {
			Object[] oldData = this.data;
			this.data = new Object[(int) (data.length * 1.5)];
			System.arraycopy(oldData, 0, this.data, 0, oldData.length);
		}
	}

	public T removeTop() {
		T rst = this.getHeapTop();
		this.data[0] = this.data[--this.size];
		this.shiftdown(0);
		return rst;
	}

	public boolean hasNext() {
		return this.size > 0;
	}

	@SuppressWarnings("unchecked")
	public T[] getData() {
		return (T[]) this.data;
	}

	@SuppressWarnings("unchecked")
	public T getValue(int index) {
		return (T) this.data[index];
	}

	private int getParentIndex(int pos) {
		return (pos - 1) / 2;
	}

	private int getLeftChildIdx(int pos) {
		return pos * 2 + 1;
	}

	private int getRightChildIdx(int pos) {
		return pos * 2 + 2;
	}

	private void swap(int idx1, int idx2) {
		T tmp = this.getValue(idx1);
		this.data[idx1] = this.getValue(idx2);
		this.data[idx2] = tmp;
	}

	/**
	 * 节点值向下级交换，构造堆
	 * 
	 * @param pos
	 */
	private void shiftdown(int pos) {
		int leftChildIdx = this.getLeftChildIdx(pos);
		// 没有子节点了
		if (leftChildIdx >= this.size) {
			return;
		}
		int rightChildIdx = getRightChildIdx(pos);
		int toBeSwapIdx = leftChildIdx;
		if (rightChildIdx < this.size
				&& this.getValue(leftChildIdx).compareTo(
						this.getValue(rightChildIdx)) > 0) {
			toBeSwapIdx = rightChildIdx;
		}
		// swap
		if (this.getValue(pos).compareTo(this.getValue(toBeSwapIdx)) > 0) {
			this.swap(pos, toBeSwapIdx);
			this.shiftdown(toBeSwapIdx);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Integer[] data = { 7, 12, 13, 24, 8, 6, 4, 27, 14, 8, 12, 56, 22 };
		HeapSort<Integer> heap = new HeapSort<Integer>(data);
		while (heap.hasNext()) {
			System.out.print(heap.removeTop());
			System.out.print("  ");
		}

		System.out.println("  ");
		heap.initHeap(data);
		for (int i = 0; i < 10; i++) {
			heap.addToHeap(i);
		}
		while (heap.hasNext()) {
			System.out.print(heap.removeTop());
			System.out.print("  ");
		}
		
		System.out.println("  ");
		heap.initHeap(data);
		for (int i = 0; i < 10; i++) {
			heap.addToHeapKeepFixedSize(i);
		}
		while (heap.hasNext()) {
			System.out.print(heap.removeTop());
			System.out.print("  ");
		}
		

	}

}

 测试输出：

 

4  6  7  8  8  12  12  13  14  22  24  27  56    
0  1  2  3  4  4  5  6  6  7  7  8  8  8  9  12  12  13  14  22  24  27  56    
7  8  8  8  9  12  12  13  14  22  24  27  56