堆排序java实现

对堆数据结构有疑问的伙伴，可以看一下我的另一篇文章，对堆结构有介绍
数据结构堆介绍以及java代码实现

import java.util.Arrays;


public class HeapSort {

    
    public void exchangeHeapEle(int[] heapData,int index1,int index2){
        int temp = heapData[index1];
        heapData[index1] = heapData[index2];
        heapData[index2] = temp;
    }

    
    private void bulidHeap(int[] data,int heapSize){
        for (int i = heapSize>>1;i>0;i--){
            compareHeapElement(data,i,heapSize);
        }
    }

    
    private void compareHeapElement(int[] data,int begin,int end){
        int leftIndex = begin << 1;
        int rightIndex = leftIndex + 1;
        while (rightIndex < end || leftIndex < end){
            int maxIndex = begin;
            if (data[maxIndex] < data[leftIndex]){
                maxIndex = leftIndex;
            }
            if (rightIndex < end && data[maxIndex] < data[rightIndex]){
                maxIndex = rightIndex;
            }
            if (maxIndex != begin){
                // 交换
                exchangeHeapEle(data,begin,maxIndex);
            }
            begin ++;
            leftIndex = begin << 1;
            rightIndex = leftIndex +1;
        }
    }

    
    private void heapSort(int[] heapArray){
        int end = heapArray.length;
        bulidHeap(heapArray,end);
        while (end>1){
            exchangeHeapEle(heapArray,1,end-1);
            end--;
            bulidHeap(heapArray,end);
        }
    }

    public static void main(String[] args) {
        //完全二叉树，第一个元素位置不用，所以跳过
        int[] array = new int[12];
        array[1] = 14;
        array[2] = 17;
        array[3] = 6;
        array[4] = 4;
        array[5] = 2;
        array[6] = 42;
        array[7] = 56;
        array[8] = 89;
        array[9] = 8;
        array[10] = 5;
        array[11] = 1;
        new HeapSort().heapSort(array);
        System.out.printf(Arrays.toString(array));
    }

}