堆排序

对于一个完全二叉树来说，如果所有的结点（叶子结点除外）的值都大于其左右孩子结点的值，那么这个完全二叉树就被成为一个大根堆。

时间复杂度为O(nlogn)
空间复杂度O（n）

代码：

/**
调整堆结点
**/
//arr:数组首地址；n:结点在数组中的位置；len:数组的长度
void heap_down(int *arr, int n, int len)
{
    int l, r, max, tmp;
    l = 2 * n + 1; //左右孩子的索引，注意数组下标从0开始。
    r = 2 * n + 2;
    max = n;

    if (l<len&&arr[l]>arr[n])
        max = l;
    if (r<len&&arr[r]>arr[max])
        max = r;

    if (max != n)
    {
        tmp = arr[n];
        arr[n] = arr[max];
        arr[max] = tmp;
        heap_down(arr, max, len); //保证最大堆
    }
}

/**
堆排序
**/
//堆排序（升序）
void heap_sort(int *arr, int len)
{
    for (int i = len / 2-1; i >= 0; i--) // 从最后一个非叶子节点开始往前遍历
        heap_down(arr, i, len);
    int tmp;

    for (int i = len - 1; i >= 0; i--)
    {
        tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;
        heap_down(arr, 0, i);
    }
}

/**
插入元素
**/
  // 从已经排好序的队列里，添加元素到尾部
    public void insert(int item ) {
        //先将添加的元素加到最后一个元素后面
        //有索引还得考虑索引越界问题，最好的解决方案是动态扩展堆
        //这样可以不受堆容量限制，容量不足开辟新空间
        if(count++<=getCapacity()) {
        //count指向所添加的元素
        data[count]=item;
        //再将item向上移动，与父节点比较，如果比父节点大，则交换
        shiftUp(count);
        }       
    }

 //向上移动，将item与父节点比较，如果比父节点大，则交换
    private void shiftUp(int i) {
        while(i>1&&data[i]>data[i/2]) {
            swap(i,i/2);
            i/=2;
        }
    }

/**
删除元素
**
  // 从一个已经排好序的队列里，删除第一个元素
    public int extractMax() {
        if(count<=0)
            return 0;
        //先取出最大的（优先级高的）
        int max=data[1];
        //将堆中最后一个元素存入第一元素的位置
        swap(1, count);
        count--;
        //将第一个元素向下移，找到合适位置，维护堆
        shiftDown(1);
        return max;
    }

// 交换元素
private void swap(int i, int j) {
        if(i!=j) {
            int temp=data[i];
            data[i]=data[j];
            data[j]=temp;
        }
    }