堆排序实例堆排序实例(Java数组实现数组实现)
下面小编就为大家分享一篇使用Java数组实现堆排序的实例,具有很好的参考价值,希望对大家有所帮助。一
起跟随小编过来看看吧
堆排序:利用大根堆堆排序:利用大根堆
数组全部入堆,再出堆从后向前插入回数组中,数组就从小到大有序了。
public class MaxHeap<T extends Comparable<? super T>> {
private T[] data;
private int size;
private int capacity;
public MaxHeap(int capacity) {
this.data = (T[]) new Comparable[capacity + 1];
size = 0;
this.capacity = capacity;
}
public int size() {
return this.size;
}
public boolean isEmpty() {
return size == 0;
}
public int getCapacity() {
return this.capacity;
}
/**
* @return 查看最大根(只看不删, 与popMax对比)
*/
public T seekMax() {
return data[1];
}
public void swap(int i, int j) {
if (i != j) {
T temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
public void insert(T item) {
size++;
data[size] = item;
shiftUp(size);
}
/**
* @return 弹出最大根(弹出意味着删除, 与seekMax对比)
*/
public T popMax() {
swap(1, size--);
shiftDown(1);
return data[size + 1];
}
/**
* @param child 孩子节点下角标是child,父节点下角表是child/2
*/
public void shiftUp(int child) {
while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {
swap(child, child / 2);
child = child / 2;
}
}
/**
* @param a data数组中某个元素的下角标
* @param b data数组中某个元素的下角标
* @return 哪个元素大就返回哪个的下角标
*/
private int max(int a, int b) {