堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：子节点的值总是小于（或大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

算法步骤

1. 使用未排序数列构建一个堆H[0……n-1]；
2. 将堆首和堆尾互换；
3. 把堆的尺寸缩小1，并重新调整堆数据，使其满足堆的性质；
4. 重复步骤2-3-2-3….，直到堆的尺寸为1；

动图演示

代码实现

template <typename T>
void swap(T *a, T *b) {
    T temp = *a;
    *a = *b;
    *b = temp;
}
template <typename T>
void adjustHeap(T arr[], int index, size_t len) {

    for (int k = 2*index+1; k<len; k=2*k+1) {
        // 获取左右节点中，较大的那个节点
        if (k+1 < len && arr[k] < arr[k+1]) {
            k = k + 1;
        }
        
        if (arr[k] > arr[index]) {
            // 如果叶子节点大于根节点，则将大的那个节点和根节点交换
            swap(&arr[k], &arr[index]);
            index = k; // 交换后，需要
        } else {
            // 当前节点无需调整
            break;
        }
    }
}


template <typename T>
void heapSort(T arr[], size_t len) {
    
    // 1、构造初始堆
    for (int i = (int)len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
    
    for (int j = (int)len - 1; j > 0; j--) {
        // 2、交换顶元素与最后一个元素
        swap(&arr[j], &arr[0]);
        // 3、交换后，打乱了堆，需要重新调整
        adjustHeap(arr, 0, j);
    }
}

int main(int argc, const char * argv[]) {
    int arr2[] = {99, 4, 6, 8, 5, 9, -1, -2, 100};
    heapSort(arr2, sizeof(arr2) / sizeof(int));
    return 0;
}