First, I assume you mean besides the fact that you don't need it, since we have an entire heap management function set in the C++ standard library, including make_heap, push_heap, pop_heap, and even sort_heap.
That said, I think I know what your problem is. You have unnecessary movement of elements in your heap. It deals with the swapping algorithm on the heap-down: the same problem is notable on both left and right sides, so I'll show the first one:
if (l < n && arr[i] < arr[l])
{
swap(arr[i], arr[l]);
heapDown(l);
if (r < n && arr[i] < arr[r])
{
swap(arr[i], arr[r]);
heapDown(r);
}
}
The logic here is not optimal for minimum motion. The "lesser" state of the element being pushed down must fall into one of two basic categories, and different actions are taken for each:
- The element is not less than either left or right. Do nothing.
- The element is less than either left or right, swap only with the largest, then drive down into only that subtree.
The #2 above in that list is the problem in your code. you swap with the smaller, then the larger, if item < left < right. I hope that is clear. If you want a proposal to fix your logic I can provide one, but I think you may have a handle on it if you understand what I described above.
Spoiler
void Heap::heapDown(int i)
{
int l = left(i);
int r = right(i);
int x = 0;
if (l < n && arr[i] < arr[l])
{
x = l;
if (r < n && arr[l] < arr[r])
x = r;
}
else if (r < n && arr[i] < arr[r])
x = r;
if (x != 0)
{
swap(arr[i], arr[x]);
heapDown(x);
}
}
Note:; In case it wasn't obvious, this is the very definition of tail-recursive, and as such could easily be transformed into a simple iterative loop.