• 各个编程语言中优先级队列的原理

// 从位置i, 将父节点不断向下与子节点比较, 使得以i为跟的二叉树, 满足堆的性质
void heapify(vector<int>& nums, int n, int i) {
    int largest = i;         // 当前结点
    int left = 2 * i + 1;    // 左子结点
    int right = 2 * i + 2;   // 右子结点

    if (left < n && nums[left] > nums[largest]) {
        largest = left;
    }
    if (right < n && nums[right] > nums[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, n, largest);  // 递归调整子树
    }
}

void heapSort(vector<int>& nums) {
    int n = nums.size();

    // 1. 建堆（从最后一个非叶子节点向上调整）
    for (int i = n / 2 - 1; i >= 0; --i) {
        heapify(nums, n, i);
    }

    // 2. 排序（每次把最大值放最后）
    for (int i = n - 1; i > 0; --i) {
        swap(nums[0], nums[i]);       // 把堆顶放最后
        heapify(nums, i, 0);          // 只对前 i 个 heapify
    }
}