构造小根堆，并从大到小排序c++

构造一个小根堆并实现从大到小排序的过程在C++中通常涉及以下几个步骤：

1. **定义结构体或类**：首先创建一个存储数据的结构体或类，比如`Pair`，包含一个元素值和一个用于比较的引用。

struct Pair {
    int value;
    // 使用引用保证在heap中修改原数组元素
    int& index;
};

2. **初始化堆**：创建一个大小为n的数组（假设我们有n个元素），并将所有元素设置为它们的值作为初始键。然后将数组转换成一个最小堆，保证每个父节点的值都小于等于其子节点。

std::vector<Pair> heap(n);
// 初始化堆，假设arr是一个整数数组
for (size_t i = 0; i < n; ++i) {
    heap[i] = {arr[i], i};
    siftDown(i, n - 1); // 将当前元素下沉到正确位置
}

3. **siftDown** 函数用于维护堆的性质：对于索引i的节点，如果它大于其子节点中的较大者，则交换位置，并递归地调整子树。

void siftDown(size_t i, size_t heapSize) {
    while (i * 2 + 1 < heapSize) {
        size_t leftChild = i * 2 + 1;
        size_t rightChild = i * 2 + 2;

        if (rightChild < heapSize && heap[leftChild].value < heap[rightChild].value) {
            leftChild = rightChild;
        }

        if (heap[leftChild].value >= heap[i].value)
            break;

        std::swap(heap[i], heap[leftChild]);
        i = leftChild;
    }
}

4. **提取最大元素**：将堆顶元素（即最大的元素，由于是小根堆，所以实际上是“最小”的）与最后一个元素交换，然后将堆的大小减一，继续调整堆顶元素的位置，使其满足小根堆的性质。

5. **重复提取最大元素**：直到堆的大小为1，重复上述过程，每次提取后都会有一个新的最大元素出现在数组的末尾，这个过程实现了从大到小排序。

6. **排序后的结果**：最后，数组`arr`中的元素就是按照降序排列的结果。

// 排序后的元素存放在arr中
while (heap.size() > 1) {
    std::swap(arr[0], arr[heap.back().index]);
    heap.pop_back();
    siftDown(0, heap.size() - 1);
}