Сортировка кучи дает неправильный вывод (Cpp) - PullRequest
Новая
       42

Сортировка кучи дает неправильный вывод (Cpp)

0 голосов
/ 23 мая 2018

Я написал следующий код для сортировки кучи с использованием логики Max-Heap. 

#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. Я выталкиваю элемент с конца, но не могу понять, почему такое поведение.

Ответы [ 2 ]

0 голосов
/ 23 мая 2018

В вашем 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, ...]

Поскольку вы не проверяете, если right >= size, '3' получит ре-вставлен в вашу кучу.

0 голосов
/ 23 мая 2018

короче: вы не обрабатываете случай, когда left находится внутри вектора, а right нет.

более подробное объяснение: в heap_sort после a.pop_back () a.size () равно 6, вызываяmax_heapify (a, 0) может, в свою очередь, вызывать max_heapify (a, 2), и когда вы вызываете max_heapify (a, 2), и a.size () равен 6, право будет 2 * 2 + 2 == 6, так что вы попытаетесь получить доступ вне диапазона для вектора a (и, кажется, есть значение 32, которое вы извлекли из вектора).

...