heap sort

I am trying to write a heap sort function using the prototype:

Code:

---

void
heap_sort(void *base, size_t nel, size_t width, int(*compar)(const void *, const void *));

---

where base is a pointer to the first element
nel is the number of elements to be sorted
width is the size of each element
and compar is a standard comparison function

(the same prototype for the library function qsort)
I have successfully written a swap_data function and the necessary comparison functions.

I was wondering if anyone can give me some hints on how to do things like setting child = 2 * parent + 1 using these definitions when parent and child are void* items. I keep getting "assignment makes pointer from integer without a cast" and "invalid use of unary *" errors.

Thanks

I posted a generic quicksort implementation a while back. The quality is debatable (written in a hurry), but it should give you some ideas on how to do your heapsort implementation.

Thanks, that cleared up some things, but I still cannot find the child nodes. The children appear at 2*parent+1 in a heap as far as I know, but when parent is void* (or unsigned char*) rather than being an int in an array, I just don't know how to find the child.

Don't worry, I worked everything out, yay!

For anyone that was interested, instead of doing:

Code:

---

child = 2*parent + width

---

I just did:

Code:

---

child = parent + (parent - base) + width

---

which makes sense if you think about it long enough, and draw diagrams and stuff :)

Out of curiousity, do you go to Melb Uni? :)
Well because we nearly got the same question and at the same time for 1 of our assignments.

Yep, pretty easy to guess I suppose, damn sorting project took me ages. Still, I learned a hell of a lot from it so it's not all bad.

Haha yer the report was a pain to write :p