CODEWITHSUNDEEP
c++heapheapsort
kancha
kancha

Reputation: 31

Heap Sort giving wrong output ( Cpp )

I have written the following code for Heap Sort using Max-Heap logic.

#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;
}

Output : 32 9 32 7 32 32

Expected Output: Print elements in descending order.

I don't know why there is a repetition of 32. I am popping the element from the end but can't figure out why such behavior.

Upvotes: 0

Views: 129

Answers (2)

Jim Mischel
Jim Mischel

Reputation: 133950

You have a bug in your 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);
    }    
}

You always check a[max] < a[right], even if right >= size. So you can have this situation:

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

And the array contains: [0,1,3, ...]

Because you don't check to see if right >= size, the '3' will get re-inserted into your heap.

Upvotes: 1

Andrew Kashpur
Andrew Kashpur

Reputation: 746

in short: you do not handle case when left is inside vector, but right is not.

more in depth explanation: in heap_sort after a.pop_back() a.size() is 6, calling max_heapify(a, 0), may, in turn call max_heapify(a, 2) , and when you call max_heapify(a, 2), and a.size() is 6, right will be 2*2+2 == 6, so you will attempt to access out of range for vector a (and there seems to be value 32 you popped from vector).

Upvotes: 1

Related Questions