为何make_heap()无法生成最小堆？代码调试求助

核心错误 #

使用std::pop_heap时，你误解了它的行为：

• std::pop_heap会将堆顶元素（最小堆的最小元素）移动到容器的末尾，然后将剩余元素重新调整为堆结构。
• 你当前在pop_heap后取nums.front()，得到的是调整后的新堆顶，而非刚被弹出的最小元素。这就是为什么第一次获取到的是2而不是1。

修正后的代码 #

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> targetIndices(std::vector<int>& nums, int target) {
    int i = 0;
    std::vector<int> result;
    std::make_heap(nums.begin(), nums.end(), std::greater<int>());
    
    while (!nums.empty()) {
        std::pop_heap(nums.begin(), nums.end(), std::greater<int>());
        // 弹出的元素在容器末尾
        int data = nums.back();
        nums.pop_back();
        
        if (data > target) return result;
        if (data == target) result.push_back(i);
        i++;
    }
    return result;
}

int main() {
    std::vector<int> nums = {2,5,2,3,1};
    std::vector<int> result = targetIndices(nums, 2);
    for(int i : result)
        std::cout << i << std::endl;
}

关键修改点 #

• 将int data = nums.front();改为int data = nums.back();，因为pop_heap把弹出的元素放到了容器末尾。
• 移除了未使用的变量j，简化代码。

运行修正后的代码，result会得到预期的{1,2}，输出结果为：

1
2

内容的提问来源于stack exchange，提问作者sourabh roy