时间戳

首页 > 解决方案 > 堆排序给出错误的输出（ Cpp ）

c++ - 堆排序给出错误的输出（ Cpp ）

问题描述

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

#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。我从最后弹出元素，但不知道为什么会出现这种行为。

标签： c++heapheapsort

解决方案

你的max_heapify.

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;
    }
 // Bug is here
    if(a[max]<a[right])
    {
        max=right;
    }
    if(max!=i)
    {
        swap(a[i],a[max]);
        max_heapify(a,max);
    }    
}

你总是检查a[max] < a[right]，即使right >= size。所以你可以有这种情况：

size = 2
i = 0
left = 1
right = 2

该数组包含：[0,1,3, ...]

因为您不检查 if right >= size，所以 '3' 将被重新插入到您的堆中。

推荐阅读