c++ - 堆排序给出错误的输出(Cpp)

Question

我已经使用最大堆逻辑为堆排序编写了以下代码。

#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
using namespace std;   

void max_heapify(vector<int> &a,int i)
{

    int left=2*i+1;
    int right=2*i+2;
    if(i >= (int)a.size()/2 )
    {
        return;
    }
    int max=i;
    if(a[i]<a[left])
    {
        max=left;
    }
    if(a[max]<a[right])
    {
        max=right;
    }
    if(max!=i)
    {
        swap(a[i],a[max]);
        max_heapify(a,max);
    }    
}   

void build_maxHeap(vector<int> &a)
{
    int l=a.size();
    for(int i=l/2-1;i>=0;i--)
    {
        max_heapify(a,i);
    }
}


void heap_sort(vector<int> &a)
{
    build_maxHeap(a); // max element at top.
    for(int i=a.size()-1;i>=1;i--)
    {
        swap(a[i],a[0]);
        cout<<a[i]<<" ";
        a.pop_back();
        max_heapify(a,0);
    }
    cout<<a[0]<<endl;       
}  

int main()
{
    vector<int> a={6,7,8,1,2,9,32};
    heap_sort(a);
    return 0;
}

输出:32 9 32 7 32 32

预期输出:按降序打印元素。

我不知道为什么重复 32。我从末尾弹出元素，但无法弄清楚为什么会出现这种行为。

Answer 1

简而言之:当左侧在 vector 内但右侧不在 vector 内时，您不处理大小写。

更深入的解释:在 heap_sort 之后 a.pop_back() a.size() 为 6，调用 max_heapify(a, 0)，可能会依次调用 max_heapify(a, 2) ，当你调用 max_heapify(a, 2) 时，a. size() 为 6，right 将为 2*2+2 == 6，因此您将尝试访问 vector a 的超出范围(并且您从 vector 中弹出的值似乎为 32)。