Problem with heap sort

[hunter123]

I have code which counts the number of comparison of binary ternary and quad trees what i think the code for ternary and quad trees
fixDown3 and fixDown4 are off. If you test them on some data (say run a heapSort based on them, you'll see that your positional expressions are all off).

For example, take a look at fixDown4.

template <class Item>
void fixDown4(Item a[], int k, int N)
{ int j;
while (3*k <= N)
{ c1++;
j = 4*k;
if (j < N)
{ if (a[4*k-2]>a[j]) j-=2;
if (a[4*k-1]>a[j]) j=4*k-1;
if (a[4*k+1]>a[j]) j++;
}
if (!(a[k]< a[j])) break;
exch(a[k], a[j]); k = j;
}
}

The expression 3*k <= N for testing internal nodes is wrong. Check it out on some quad-tree with the heap4 numbering.

The expression j = 4*k; won't give you the left-most brother and hence the expression j<N would cut out some nodes. The comparison in

if (a[4*k-2]>a[j]) j-=2;
if (a[4*k-1]>a[j]) j=4*k-1;
if (a[4*k+1]>a[j]) j++;

are completely off when you have only one or two brothers.
heres the code
#include <iostream>

using namespace std;

int c2=0, c3=0, c4=0;
template <class Item>
void exch(Item &A, Item &B)
{ Item t = A; A = B; B = t; }


template <class Item>
void fixDown(Item a[], int k, int N)
{ int j;
while (2*k <= N)
{ c2++;
j = 2*k;
if (j < N && a[j]< a[j+1]) j++;
if (a[k]>= a[j]) break;
exch(a[k], a[j]); k = j;
}
}

template <class Item>
void heapsort(Item a[], int l, int r)
{ int k, N = r-l+1;
for (k = N/2; k >= 1; k--)
fixDown(&a[0], k, N);
while (N > 1)
{
exch(a[1], a[N]);
fixDown(&a[0], 1, --N);
}
}

template <class Item>
void fixDown3(Item a[], int k, int N)
{ int j;
while (3*k <= N)
{ c3++;
j = 3*k;
if (j < N)
{ if (a[3*k-1]>a[j]) j--;
if (a[3*k+1]>a[j]) j++;
}
if (!(a[k]< a[j])) break;
exch(a[k], a[j]); k = j;
}
}

template <class Item>
void heapsort3(Item a[], int l, int r)
{ int k, N = r-l+1;
for (k = (N+1)/3; k >=1; k--)
fixDown3(&a[0], k, N);
while (N > 1)
{
exch(a[1], a[N]);
fixDown(&a[0], 1, --N);
}
}

template <class Item>
void fixDown4(Item a[], int k, int N)
{ int j;
while (3*k <= N)
{ c4++;
j = 4*k;
if (j < N)
{ if (a[4*k-2]>a[j]) j-=2;
if (a[4*k-1]>a[j]) j=4*k-1;
if (a[4*k+1]>a[j]) j++;
}
if (!(a[k]< a[j])) break;
exch(a[k], a[j]); k = j;
}
}

template <class Item>
void heapsort4(Item a[], int l, int r)
{ int k, N = r-l+1;
for (k = (N+1)/4; k >=1; k--)
fixDown4(&a[0], k, N);
while (N > 1)
{
exch(a[1], a[N]);
fixDown(&a[0], 1, --N);
}
}


template <class Item>
void replace_max(Item a[], Item x, int n)
{
a[1] = x;
fixDown(a, 1, n);
}

int main()
{
int m, n, i, a[100000], b[100000], c[100000];

cout << "Enter the size of the Heap: " ;
cin >> m;

for(i=1; i<=m; i++)
{ a[i] = rand();
b[i]= a[i];
c[i]= a[i];
}

heapsort(a, 1, m);
heapsort3(b, 1, m);
heapsort4(c, 1, m);

cout << "Number of comparision: "<<c2 <<" " <<c3<<" "<<c4<<"\n";

system("pause");
}

[Banfa]

You appear to have posted a thread from another forum, (it certainly reads as an initial post plus at least one reply). This is not acceptable behaviour on this forum.

You have also failed to describe your problem, the expected behaviour and the actual behaviour of the code, the input to the program and the outputs from it.

This is also not acceptable.

If you are going to ask a question on this forum then you need to have

• Compiled and run your own code and made an attempt to debug it yourself.
• Be able to describe what it is meant to do
• Be able to describe what it does that is incorrect or undesired
• Actually ask a question, not just post a bunch of code and expect us to run and debug it for you.
• Put code tags round the code you post

Please read our posting guidelines particularly How to ask a question.

Further breaking of the posting guidelines may result initially in a temporary ban on your account.

Banfa
Administrator

[nazguy]

Yes, I see a couple issues with both your fixDown3 and fixDown4 routines. They are basically the same issues so I will just focus on fixDown3 and you can apply the same fixes to fixDown4.

#1 - You are right about your while condition, it is off. You can't just copy the apparent formula down from fixDown2. The node 3*k could be > N and yet you could have the node 3*k-1 = N and it would never get checked with your current code. To get the leftmost child node you would need to calculate 3*k-1 instead.

#2 - You need to rethink your logic of comparing the child nodes and exchanging. Your code is setting j to the middle node and then comparing the left node to it, decrementing j if the left node is larger. Now you have j set to the leftmost child node in this case. Then you compare the rightmost node with the node j is set to (leftmost in this case), and if the rightmost node is larger, then you increment j right back to where it started, the middle node. What you wanted was j set to the rightmost node now since it is the largest in this case. So you are exchanging the middle node instead of the rightmost node in this case.

#3 - Your condition if(j<N) will have to be rethought as well once you fix the above issues.

The implementation needs to be very precise. You can't just make assumptions when extending from binary to ternary to quad. Work out the scheme of your algorithm on paper if that helps and make sure you understand how it works precisely then implement it in code.

Hope this helps.