堆排序专题

vector<int> arr;

void buildMinHeap(int firstIndex, int endIndex) {
    for (int i = endIndex/2; i >= firstIndex; i--) {
        adjustDown(i, endIndex);
    }
}

void adjustDown(int parentIndex, int endIndex) {
    int left = 2 * parentIndex + 1;
    int right = 2 * parentIndex + 2;
    //最小值的下标
    int minIndex = parentIndex;
    if (left < endIndex && arr[left] < arr[minIndex]) {
        minIndex = left;
    }
    if (right < endIndex && arr[right] < arr[minIndex]) {
        minIndex = right;
    }
    if (minIndex == parentIndex) {
        return;
    }
    //交换元素
    swap(parentIndex, minIndex);
    //递归调整
    adjustDown(minIndex, endIndex);
}

void heapSort() {
    int n = arr.size();
    //1. 将数组构建成小根堆
    buildMinHeap(0, n);
    //2. 将堆顶元素（最小值）与堆底元素交换，并将堆的大小减1
    for (int i = n - 1; i > 0; i--) {
        swap(0, i);
        //3. 对剩下的元素重新进行堆化
        adjustDown(0, i);
    }
}