/**=========================================================
* 版权：联信永益 版权所有 (c) 2002 - 2003
* 文件： heapsort.HeapSort.java
* 所含类: HeapSort.java
* 修改记录：
* 日期 作者 内容
* =========================================================
* 2010-5-16 李星星 创建文件，实现基本功能
*/
package heapsort;
/** 就地堆排序 */
public class HeapSort {
public int size;// 记录规模
// 构造方法
public HeapSort() {
size = 0;
}
// 建堆方法，只需线性时间建好
public void buildHeap(int[] num) {
size = num.length;// 获取堆的规模
for (int i = num.length / 2 - 1; i >= 0; i--) {// 对前一半的节点，
percolateDown(num, i);// 进行下滤操作
}
}
// 给定数组交换两个数的位置
public void swap(int[] num, int v, int u) {
int temp = num[v];
num[v] = num[u];
num[u] = temp;
}
// 对该数进行上滤操作，直到该数比父节点大就停止上滤
public void percolateUp(int[] num, int index) {
while (index != 0) {// 只要下标不为0
int parent = (index - 1) / 2;// 获取该数的父节点
if (num[index] < num[parent]) {// 和父节点进行比较
swap(num, index, parent);// 如果比父节点小，就交换两个的位置
index = parent;// 更新index的指向
}
}
}
/******************************* 排序用的方法 ************************************/
public int getSize() {
return size;
}
// 判断该数是否有左节点
public boolean hasLChildTwo(int index) {
return index * 2 + 1 < size ? true : false;
}
// 判断该数是否有右节点
public boolean hasRChildTwo(int index) {
return index * 2 + 2 < size ? true : false;
}
// 对该数进行下滤操作，直到该数比左右节点都小就停止下滤
public void percolateDown(int[] num, int index) {
int min;// 设置最小指向下标
while (hasLChildTwo(index)) {// 如果该数有左节点，则假设左节点最小
min = index * 2 + 1;// 获取左节点的下标
if (hasRChildTwo(index)) {// 如果该数还有右节点
if (num[min] > num[index * 2 + 2]) {// 就和左节点分出最小者
min = index * 2 + 2;// 此时右节点更小，则更新min的指向下标
}
}
// 此时进行该数和最小者进行比较，
if (num[index] < num[min]) {// 如果index最小，
break;// 停止下滤操作
} else {
swap(num, index, min);// 交换两个数，让大数往下沉
index = min;// 更新index的指向
}
}// while
}
/*********************************************************************/
public static void main(String[] args) {
int[] num = { 6, 4, 1, 2, 8, 4, 7, 3, 0, 9 };
HeapSort heap = new HeapSort();
heap.buildHeap(num);// 建立小顶堆
for (int i = 0; i < num.length; i++) {
System.out.print(num[i] + " ");
}
System.out.println();
for (int i = num.length - 1; i >= 1; i--) {
heap.swap(num, 0, i);// 交换
heap.size--;// 每交换一次让规模减少一次
heap.percolateDown(num, 0);// 将新的首元素下滤操作
}
for (int i = 0; i < num.length; i++) {
System.out.print(num[i] + " ");
}
}
}