CODEWITHSUNDEEP
c++algorithmsorting
user670595
user670595

Reputation:

Implementing Heap Sort

I am attempting to implement Heap sort in my program to learn more about sorting algorithms. However I am running in to an issue.

I call Heap sort in main like this:

Main:

heap_sort(h_vector);

Where h_vector is a randomly sized vector with random ordered elements. My heap sort algorithm looks like.

Heap Sort:

void max_heapify(std::vector<int>& v, int i)
{
    int left = i + 1, right = i + 2;
    int largest;

    if( left <= v.size() && v[left] > v[i])
    {
        largest = left;
    }

    else
    {
        largest = i;
    }

    if( right <= v.size() && v[right] > v[largest])
    {
        largest = right;
    }

    if( largest != i)
    {
        std::swap(v[i], v[largest]);
        max_heapify(v,largest);
    }



}

void build_max_heap(std::vector<int>& v)
{
    for( int i = v.size() - 2; i >= 0; --i)
    {
        max_heapify(v, i);
    }

}

void heap_sort(std::vector<int>& v)
{
    build_max_heap(v);
    int x = 0;
    int i = v.size() - 1;
    while( i > x)
    {
        std::swap(v[i],v[x]);
        ++x;
        --i;
    }

}

Whenever I add this sort to my program I get the following error.

Error:

*** glibc detected *** ./a.out: free(): invalid next size (normal): 0x096c82d0 ***

I am not sure what could be causing this. I thought at first that my alogrithm might be going out of bounds of the vector but I have checked a few times and I do not see where. Any ideas? Thanks for your help in advance.

Upvotes: 0

Views: 3376

Answers (4)

shashankS
shashankS

Reputation: 1073

I have attempted this heap sort solution, refer this. Python implementation of the heap sort algorithm:

def heapify(aiml, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2

if l < n and aiml[l] > aiml[largest]:
    largest = l

if r < n and aiml[r] > aiml[largest]:
    largest = r

if largest != i:
    aiml[i], aiml[largest] = aiml[largest], aiml[i]
    heapify(aiml, n, largest)

def heapSort(aiml): n = len(aiml)

# Build a maxheap.
for i in range(n // 2 - 1, -1, -1):
    heapify(aiml, n, i)

# One by one extract elements
for i in range(n - 1, 0, -1):
    aiml[i], aiml[0] = aiml[0], aiml[i]  # swap
    heapify(aiml, i, 0)

Example usage:

aiml = [12, 11, 13, 5, 6, 7] heapSort(aiml) print("Sorted array is", aiml)

Upvotes: 0

Mushrif Ali
Mushrif Ali

Reputation: 1

#include <stdio.h>
#include <stdlib.h>
int a[90],n;

void swap(int *a,int *b)
 {
   int temp = *a;
        *a = *b;
        *b = temp;
 }
void ct_heap(int n)
{
 int j,data,i;
 for(i=0;i<n;i++)
 {
  data=a[i];
   for(j=i;j>0;j--)
   {
    if(a[(i-1)/2]<data)
     {
       swap(&a[(i-1)/2],&a[i]);
       i=(i-1)/2;
     }
   }
 }
}
void display()
{
  int k;
   for(k=0;k<n;k++)
    {
     printf("%d\t",a[k]);
    }
   printf("\n");
 }
void heap_sort()
{
ct_heap(n);
int end;
end=n-1;

while(end>=0)
  {
    swap(&a[end],&a[0]);

    ct_heap(end);
    end=end-1;
  }
}
int main()
{
    int i;

      printf("Enter Number of Nodes\n");
      scanf("%d",&n);
      printf("Enter Data\n");
      for(i=0;i<n;i++)
      scanf("%d",&a[i]);
      printf("After Heap Creation\n");
      ct_heap(n);
      display();
      heap_sort();
      printf("Array After Heap Sort\n");
      display();
    return 0;
}

Upvotes: -1

phkahler
phkahler

Reputation: 5767

Your "for" loop in build_max_heap() is running backwards. You can't build a heap that way. You start with the first element of the array as a heap and then add subsequent elements to it. This does not work starting from the end, because the rest of the array is not a heap yet.

Also, what amit said.

In particular, a heap will be defined by the array and the size of the heap - not the array because it's not always ALL part of the heap. So you're missing a parameter (the heap size). The only time the whole array is a heap, is after build_max_heap() is done and before you run the second pass to pull it into sorted order. At every other time, the heap size is not the array size.

Upvotes: 0

amit
amit

Reputation: 178411

At the very first invokation of max_heapify(), you invoke it with i = v.size() - 2

Thus, when you set right = i + 2; you actually set: right = v.size()

Now, look at this:

 if( right <= v.size() && v[right] > v[largest])

Note that right <= v.size(), and you are now trying to access v[right], which is out of bound.

Note that the last index of v is v[v.size() -1] - so all your if statements should be right < v.size() [instead <=]

I assume solving these issues will solve your bug eventually.

Upvotes: 4

Related Questions