排序－堆

堆排序的时间效率与快速排序 相同，也为O(n * log n)。空间上没有使用多余的空间。
基于数组堆的相关定义算法见Heap 堆

排序基于以下假设：
    如果一个节点的两个子堆是正确，可以通过下降trickleDown使得堆恢复正常。
    一个无序数组的n/2～n的数字可以看成为没有子堆的正确的堆。
    对从n/2-1  至 0的元素依次调用trickleDown,可以将一个无序数组组中成一个正确的堆
    只有一个节点的堆是个正确的堆
    移除总是移除最大的元素，且每次移除后数组的从后向前多增加自由位置，可以将刚移除的数据放入其中。

    Node为辅助类，key表示排序关键字，value表示数据。为了简便没有采用标准的get,set
    Heap中
        构造函数根据给定的需要排序的数组构造。
        sort方法：首先将数组变成一个正确的堆，然后将堆中的数据依次取出放回数组。
        trickleDown：将数组中的指定位置元素下降至恰当的位置，以保证堆的正确性。
        print,main:提供简单的测试。

class Node {	//表示装数据的节点
	private int key;	//排序的关键字
	private Object value;	//数据
	
	Node(int key, Object value) {
		this.key =  key;
		this.value = value;
	}

	int key() { return key; }
	Object value() { return value; }
}

class Heap {
	private Node[] array;	//序排序的数组
	private int pos;	//当前有效数据的个数
	Heap(Node[] array) {
		this.array = array;	//装入要排序的数组
		pos = array.length;
	}

	private Node remove() {	//删除堆的顶
		Node result = array[0];
		array[0] = array[--pos];	//将最后一个元素提至堆定
		trickleDown(0);		//将堆顶下降为恰当位置
		return result;
	}

	private void trickleDown(int index) {
		Node top = array[index]; //存放要下降的数据
		int left = getLeft(index);	//得到左子的位置
		int right = getRight(index);	//得到右子的位置
		int current;	//当前可能要下降的位置
		if(left < pos && right < pos) //左右子节点有效，当前的位置设置为左右子节点中小的那个
			current = array[left].key() > array[right].key() ? left : right;
		else if (left < pos) current = left; //如果左子节点有效，则当前位置设置为左子节点
		else current = -1;	//没有可以下降的位置
		while(current != -1 && array[current].key() > top.key()) {//当前节点有效且大于要下降的数据
 			array[index] = array[current];	//将当前节点向上提升。
			index = current;	//重复以上过程
			left = getLeft(index);
			right = getRight(index);
			if(left < pos && right < pos) 
				current = array[left].key() > array[right].key() ? left : right;
			else if (left < pos) current = left; 
			else current = -1;
		}
		array[index] = top;	//将暂存的数据放入恰当的位置
	}

	private int getParent(int index) {
		return (index-1)/2;
	}

	private int getLeft(int index) {
		return 2 * index + 1;
	}

	private int getRight(int index) {
		return 2 * index + 2;
	}

	public void sort() {
		for(int i=array.length/2 -1; i>=0; i--) {
			trickleDown(i);
		}
		for(int i=array.length-1; i>=0;i--) array[i] = remove();
	}

	public static void main(String[] args) {
		Node[] nodes = {new Node(50,"hello"), 
			new Node(20,"jason"),
			new Node(60,"peter"), 
			new Node(50,"orange"),
			new Node(30,"temp"), 
			new Node(40,"hello"),
			new Node(90,"nasen"),
			new Node(25,"kaka")};
		Heap heap = new Heap(nodes);
		heap.sort();
		print(nodes);
	}

	private static void print(Node[] nodes) {
		for(Node node: nodes) 
			System.out.println(node.key() + "-----" + node.value());
	}
}

 

 

评论

2 楼 run_xiao 2008-08-06  

堆排序，搞懂了N次，忘记了N次！

1 楼 桔红糕 2008-05-08  

早上八点半？
结果上班还迟到？？
还被淋湿了？？？

怪不得郁闷呢～