堆排序

用java实现的堆排序。

 

堆：堆是一种特殊的二叉树，

1）每一个节点的值均大于等于每个子女的值。

2）树是完全平衡的，并且最后一层都在最左边。

 

在程序中传入一个带排序的数组，同时也可指定排序的方式（降序 或 升序）

 

package com.woxiaoe.collection.heap;

import java.util.Arrays;
import java.util.Comparator;


public class Heap<T> {
	private T[] arr;
	private int heapSize;
	public static int DESC = 0,ASC = 1;
	public Comparator<T> comp;
	public Heap(T[] arr,int sort) {
		this.arr = arr;
		heapSize = arr.length;
		if(sort == DESC){
			comp = less;
		}else{
			comp = grater;
		}
		makeHeap();
	}
	public Heap(T[] arr) {
		this.arr = arr;
		heapSize = arr.length;
		comp = less;
		makeHeap();
	}
	public T popHeap(int i ){
		T t = arr[0];
		arr[0] = arr[i];
		arr[i] = t;
		adjustHeap(0,i);
		return t;
	}
	//调整堆
	public void adjustHeap(int first,int last){
		int curr ,child;
		T target;
		curr = first;
		child = curr * 2 + 1;
		target = arr[first];
		while(child < last){
			//选出子节点较大者
			if((child + 1) < last && (comp.compare(arr[child + 1],arr[child])>0)){
				child ++;
			}
			if(comp.compare(arr[child],target)> 0){//如果子节点大于父节点，交换
				arr[curr] = arr[child];
				curr = child;
				child = child*2 + 1;
			}else{
				break;
			}
		}
		arr[curr] = target;
	}
	/**
	 * 构造堆
	 */
	public void makeHeap(){
		int last,curr;
		last = heapSize;
		curr = (heapSize - 2)/2;//最后一个节点
		while(curr >= 0){
			adjustHeap(curr, last);
			curr --;
		}
	}
	/**
	 * 堆排序
	 */
	public void heapSort(){
		int len = heapSize;
		for(int i = len - 1 ; i >= 0; i-- ){
			popHeap(i);
		}
	}
	@Override
	public String toString() {
		return Arrays.toString(arr);
	}
	private Comparator<T> grater = new Comparator<T>() {
		@Override
		public int compare(T o1, T o2) {
			return ((Comparable<T>)o1).compareTo(o2);
		}
	};
	private Comparator<T> less = new Comparator<T>() {
		@Override
		public int compare(T o1, T o2) {
			return ((Comparable<T>)o2).compareTo(o1);
		}
	};
}

 

测试代码

package com.woxiaoe.collection.heap;

import junit.framework.TestCase;

public class HeapTest extends TestCase {
	Heap<Integer> heap;
	@Override
	protected void setUp() throws Exception {
	}
	public void testAddHeap(){
		Integer[] arr = new Integer[100];
		for(int i = 0; i < 100; i++){
			arr[i] = i;
		}
		heap = new Heap<Integer>(arr,Heap.ASC);
		System.out.println(heap);
		heap.heapSort();
		System.out.println(heap);
		
	}
	
}

 Output

[99, 94, 98, 78, 93, 97, 62, 70, 77, 86, 92, 96, 54, 58, 61, 66, 69, 74, 76, 82, 85, 90, 91, 95, 50, 52, 53, 56, 57, 60, 30, 64, 65, 68, 34, 72, 73, 75, 38, 80, 81, 84, 42, 88, 89, 45, 46, 47, 48, 49, 11, 51, 25, 12, 26, 55, 27, 13, 28, 59, 29, 14, 6, 63, 31, 15, 32, 67, 33, 16, 7, 71, 35, 17, 36, 3, 37, 18, 8, 79, 39, 19, 40, 83, 41, 20, 9, 87, 43, 21, 44, 4, 1, 22, 10, 2, 0, 23, 5, 24] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]