堆排序实例(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) {
  if (data[a].compareto(data[b]) < 0) {//如果data[b]大
   return b;//返回b
  } else {//如果data[a]大
   return a;//返回a
  }
 }
 
 /**
  * @param a data数组中某个元素的下角标
  * @param b data数组中某个元素的下角标
  * @param c data数组中某个元素的下角标
  * @return 哪个元素大就返回哪个的下角标
  */
 private int max(int a, int b, int c) {
  int biggest = max(a, b);
  biggest = max(biggest, c);
  return biggest;
 }
 
 
 /**
  * @param father 父节点下角标是father,左右两个孩子节点的下角表分别是：father*2 和 father*2+1
  */
 public void shiftdown(int father) {
  while (true) {
   int lchild = father * 2;//左孩子
   int rchild = father * 2 + 1;//右孩子
   int newfather = father;//newfather即将更新，父、左、右三个结点谁大，newfather就是谁的下角标
 
   if (lchild > size) {//如果该father结点既没有左孩子，也没有右孩子
    return;
   } else if (rchild > size) {//如果该father结点只有左孩子，没有右孩子
    newfather = max(father, lchild);
   } else {//如果该father结点既有左孩子，又有右孩子
    newfather = max(father, lchild, rchild);
   }
 
   if (newfather == father) {//说明father比两个子结点都要大，表名已经是大根堆，不用继续调整了
    return;
   } else {//否则，还需要继续调整堆，直到满足大根堆条件为止
    swap(father, newfather);//值进行交换
    father = newfather;//更新father的值，相当于继续调整shiftdown(newfather)
   }
  }
 }
 
 public static <t extends comparable<? super t>> void sort(t[] arr) {
  int len = arr.length;
  //入堆
  maxheap<t> maxheap = new maxheap<t>(len);
  for (int i = 0; i < len; i++) {
   maxheap.insert(arr[i]);
  }
  //出堆
  for (int i = len - 1; i >= 0; i--) {
   arr[i] = maxheap.popmax();
  }
 }
 
 public static void printarr(object[] arr) {
  for (object o : arr) {
   system.out.print(o);
   system.out.print("\t");
  }
  system.out.println();
 }
 
 public static void main(string args[]) {
  integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  printarr(arr);//3 5 1 7 2 9 8 0 4 6
  sort(arr);
  printarr(arr);//0 1 2 3 4 5 6 7 8 9
 }
}

public class maxheap<t extends comparable<? super t>> {
 private t[] data;
 private int size;
 private int capacity;
 
 public maxheap(int capacity) {
  this.capacity = capacity;
  this.size = 0;
  this.data = (t[]) new comparable[capacity + 1];
 }
 
 public maxheap(t[] arr) {//heapify,数组建堆
  capacity = arr.length;
  data = (t[]) new comparable[capacity + 1];
  system.arraycopy(arr, 0, data, 1, arr.length);
  size = arr.length;
  for (int i = size / 2; i >= 1; i--) {
   shiftdown(i);
  }
 }
 
 public int size() {
  return this.size;
 }
 
 public int getcapacity() {
  return this.capacity;
 }
 
 public boolean isempty() {
  return size == 0;
 }
 
 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);
 }
 
 public t popmax() {
  swap(1, size--);
  shiftdown(1);
  return data[size + 1];
 }
 
 public void shiftup(int child) {
  while (child > 1 && data[child].compareto(data[child / 2]) > 0) {
   swap(child, child / 2);
   child /= 2;
  }
 }
 
 /**
  * @param a data数组中某个元素的下角标
  * @param b data数组中某个元素的下角标
  * @return 哪个元素大就返回哪个的下角标
  */
 private int max(int a, int b) {
  if (data[a].compareto(data[b]) < 0) {//如果data[b]大
   return b;//返回b
  } else {//如果data[a]大
   return a;//返回a
  }
 }
 
 /**
  * @param a data数组中某个元素的下角标
  * @param b data数组中某个元素的下角标
  * @param c data数组中某个元素的下角标
  * @return 哪个元素大就返回哪个的下角标
  */
 private int max(int a, int b, int c) {
  int biggest = max(a, b);
  biggest = max(biggest, c);
  return biggest;
 }
 
 public void shiftdown(int father) {
  while (true) {
   int lchild = father * 2;
   int rchild = father * 2 + 1;
   int newfather = father;//这里赋不赋值无所谓，如果把下面这个return改成break,那就必须赋值了
 
   if (lchild > size) {//如果没有左、右孩子
    return;
   } else if (rchild > size) {//如果没有右孩子
    newfather = max(father, lchild);
   } else {//如果有左、右孩子
    newfather = max(father, lchild, rchild);
   }
 
   if (newfather == father) {//如果原父结点就是三者最大，则不用继续整理堆了
    return;
   } else {//父节点不是最大，则把大的孩子交换上来，然后继续往下堆调整，直到满足大根堆为止
    swap(newfather, father);
    father = newfather;//相当于继续shiftdown(newfather)。假如newfather原来是father的左孩子，那就相当于shiftdown(2*father)
   }
  }
 }
 
 public static <t extends comparable<? super t>> void sort(t[] arr) {
  int len = arr.length;
  maxheap<t> maxheap = new maxheap<>(arr);
  for (int i = len - 1; i >= 0; i--) {
   arr[i] = maxheap.popmax();
  }
 }
 
 public static void printarr(object[] arr) {
  for (object o : arr) {
   system.out.print(o);
   system.out.print("\t");
  }
  system.out.println();
 }
 
 public static void main(string args[]) {
  integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  printarr(arr);//3 5 1 7 2 9 8 0 4 6
  sort(arr);
  printarr(arr);//0 1 2 3 4 5 6 7 8 9
 }
}