- package com.algorithm.sorting;
- public class Heapsort {
- public int size;
- public int queue[];
- public Heapsort(int[] list) {
- queue = new int[list.length];
- for (int i = 0; i < list.length; i++) {
- add(list[i]);
- }
- System.out.println(size);
- int i=0;
- while(size>0){
- list[i++]=remove();
- }
- }
- public void add(int e) {
- int i = size;
- while (i > 0) {
- int parent = (i - 1) / 2;
- int root = queue[parent];
- if (e <= root)
- break;
- queue[i] = root;
- i = parent;
- }
- queue[i] = e;
- size++;
- }
- public int remove() {
- int parent = 0;
- if (size == 0) {
- throw new NullPointerException("queue is null");
- }
- int max = queue[0];// top
- int last = queue[size - 1];// last
- queue[0] = last;// add the last to top
- size--;
- if (size == 2 && last < queue[1]) { // 只剩下最后两个结点,进行比较
- queue[0] = queue[1];
- queue[1] = last;
- }
- if (size > 2) { // 大于三个结点的,向下旋转
- while (parent < size / 2) {
- int left = 2 * parent + 1;// left child
- int right = left + 1;// right child
- int root = queue[parent];// root
- if (root > queue[left] && root > queue[right])
- break;
- if (queue[left] >= queue[right]) {// 左节点大于右节点,左节点和父节点交换
- queue[parent] = queue[left];
- queue[left] = root;
- parent = left;
- } else {
- queue[parent] = queue[right];
- queue[right] = root;
- parent = right;
- }
- if (right * 2 >= size)//没有子节点了,结束循环
- break;
- }
- }
- return max;
- }
- public static void main(String[] args) {
- int[]list=new int[10000];
- for (int i = 0; i <list.length; i++) {
- list[i]=i;
- }
- Heapsort sort = new Heapsort(list);
- for (int i : list) {
- System.out.print(i+" ");
- if(i%10==0)
- System.out.println();
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/130120148505.html
来源: http://www.codesnippet.cn/detail/130120148505.html