You should not be heapifying in your loop. Do that only once
, at the beginning of your function. After that, you only need a very inexpensive push-down/sink/apply heap property/whatever on the root node each time through the loop to maintain the heap.
Your post was moved and edited, apparently, so it no longer has your function to get a
 You don't need to find the parent. You need to find children. Apply the heap property (that is, "sink" or "push down" or whatever) to a parent. The following commentary about number of operations still applies: [/edit]
As you had it, you were performing way too many operations to determine the child index. As explained with the Heapsort FAQ
you only need an inexpensive shift and add to get the left child's address:
child = (parent << 1) + 1;
(which is the same as:
child = (parent * 2) + 1;
). Since you are using a binary heap, all you need to access the children is
. You do need to make sure not to access an invalid child, BTW (that is, make sure that
child < unsortedSize
(child + 1) < unsortedSize
before you try to access them.
Hope this helps.