C RUBY-ON-RAILS MYSQL ASP.NET DEVELOPMENT RUBY .NET LINUX SQL-SERVER REGEX WINDOWS ALGORITHM ECLIPSE VISUAL-STUDIO STRING SVN PERFORMANCE APACHE-FLEX UNIT-TESTING SECURITY LINQ UNIX MATH EMAIL OOP LANGUAGE-AGNOSTIC VB6 MSBUILD

# Heapsort Algorithm by Cormen Implementation in C , not working correctly

By : Waldemar
Date : November 22 2020, 10:38 AM
it helps some times I believe your Left and right functions may have an off by one error. Left(0) should not be 0 (it should be 1), Right(0) should not be 1 (it should be 2). Left of 1 should not be 2 (it should be 3), right of 1 should not be 3 (it should be 4), ect – IdeaHat
code :

Share :

## implementation of Cormen's HeapSort algorithm in C

By : Tejas B.S
Date : March 29 2020, 07:55 AM
Hope this helps 1) Fix swap, you're passing by value. Which means after swap is called nothing was changed!
2) The max_heapify function is wrong. Your left and right child calculation is off by 1. When you swap, you swap an index with an array value, yikes.
code :
`````` for(i= len-1;i>=1;i--)
{
swap(arr[0],arr[i]);
heapsize = heapsize -1;
max_heapify(arr,0);
}
``````

## Heapsort with min-heap not working correctly

By : zhou
Date : March 29 2020, 07:55 AM
will be helpful for those in need Background
As far as I understand you are using your array in two partitions.
code :
``````    if (left < input.Length && input[left] < input[index])
smallest = left;
else
smallest = index;

if (right < input.Length && input[right] < input[smallest])
smallest = right;
``````
``````    if (left <= input[0] && input[left] < input[index])
smallest = left;
else
smallest = index;

if (right <= input[0] && input[right] < input[smallest])
smallest = right;
``````

## Trying heapsort by Cormen, but getting segmentation fault

By : YSR
Date : March 29 2020, 07:55 AM
hop of those help? @mafso is correct. I changed build_heap to return a copy of the heap instead of a pointer and it worked. Maybe not the best way but it works. Here is the code:
heap.h
code :
``````#ifndef HEAP_H_
#define HEAP_H_

typedef struct
{
int size;   //array size
int count;  //heap size
int *a;     //int array
} heap;

#define PARENT(x) ((x + 1) / 2)
#define LEFT(x) (2 * (x) + 1)
#define RIGHT(x) (2 * ( (x) + 1) )

void heapify(heap* h, int i);
heap build_heap(int *a, int size);
void heapsort(int *a, int size);
void print_heap(heap *h);
void print_array(heap *h);
static void swap(int *a, int *b);

#endif /* HEAP_H_ */
``````
``````#include <stdlib.h>
#include <stdio.h>
#include "heap.h"

void heapify(heap *h, int i)
{
int largest, left = LEFT(i), right = RIGHT(i);

if (left < h->count && (*(h->a + left) > *(h->a + i)))
largest = left;
else
largest = i;
if (right < h->count && (*(h->a + right) > *(h->a + largest)))
largest = right;

if (largest != i)
{
swap(h->a + i, h->a + largest);
heapify(h, largest);
}
}

heap build_heap(int *a, int size)
{
heap h;// = (heap) { .size = size, .count = size, .a = a };
h.size = size;
h.count = size;
h.a = a;

heap *ph = &h;
int i = size / 2;

while (i >= 0)
heapify(ph, i--);

return *ph;
}

void heapsort(int *a, int size)
{
heap h = build_heap(a, size);
int i;

for (i = h.size - 1; i >= 1; --i)
{
swap(h.a, h.a + i);
h.count--;
heapify(&h, 0);
}
}

void print_heap(heap *h)
{
int *end = h->a + h->count, *arr = h->a;

while (arr < end)
printf("%d ", *arr++);

printf("\n");
}

void print_array(heap *h)
{
int *end = h->a + h->size, *arr = h->a;

while (arr < end)
printf("%d ", *arr++);

printf("\n");
}

static void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
``````
``````4 1 3 2 16 9 10 14 8 7
1 2 3 4 7 8 9 10 14 16
``````

## Problems with an implementation of Heapsort algorithm in R

By : user3504663
Date : March 29 2020, 07:55 AM
To fix the issue you can do My guess is that you were trying to convert the algorithm posted on GeeksforGeeks where they implement this in many zero based languages. This is one of the sources of your problem (R starts indexing at 1 instead of 0).
Base Zero Indexing Issues:
code :
``````                         ## We also need to swap these indices
array = replace(array, c(i, 0), c(array[0], array[i]))
heapify(array, i, 1)

Should be:

array <- replace(array, c(i, 1), array[c(1, i)])
array <- heapify(array, i, 1)
``````
``````leftChild <- 2 * i + 1
rightChild <- 2 * i + 2

Should be:

leftChild <- 2 * (i - 1) + 1
rightChild <- 2 * (i - 1) + 2
``````
``````heapify <- function(array, n, i)
{
parent <- i
leftChild <- 2 * (i - 1) + 1
rightChild <- 2 * (i - 1) + 2

if ((leftChild < n) & (array[parent] < array[leftChild]))
{
parent <- leftChild
}

if ((rightChild < n) & (array[parent] < array[rightChild]))
{
parent <- rightChild
}

if (parent != i) {
array <- replace(array, c(i, parent), array[c(parent, i)])
array <- heapify(array, n, parent)
}

array
}

heapSort <- function(array)
{
n <- length(array)

for (i in floor(n / 2):1) {
array <- heapify(array, n, i)
}

for (i in n:1) {
array <- replace(array, c(i, 1), array[c(1, i)])
array <- heapify(array, i, 1)
}

array
}
``````
``````array <- c(5, 14, 3, 70, 64)
heapSort(array)
[1]  3  5 14 64 70

set.seed(11)
largerExample <- sample(1e3)

[1] 278   1 510  15  65 951

identical(heapSort(largerExample), 1:1e3)
[1] TRUE
``````

## algorithm: exercise 5.1-2 in Introduction to Algorithm by Cormen, Leiserson, Rivest and Stein

By : Matthew Budram
Date : March 29 2020, 07:55 AM
Does that help It's enough to just do this for a = 0 and b some positive integer (why?). You need log_2 b bits to represent b in binary. Now I've given you a huge hint: think in binary.
In general, if someone hands you a computer science problem and something in the problem can generate from { 0, 1 }, start thinking in binary.