max heap and print implementation question

[mordac]

Hello, I was wondering if I could get some opinions on how best to
handle printing in a max heap data structure. Right now my heap
struct looks as thus:
typedef struct heapStruct {
int* heapArray;
int heapSize;
int arraySize;
int maxSize;
} heapStruct;
arraySize holds the current number of elements in the array.
maxSize is the total size of the array (so we know when to realloc).
And heapSize is the current size of the heap in the array.
heapsize <= arraySize <= maxSize.

I have a printHeap function that prints the elements in the heapArray
from 1 to heapSize. This works great if the elements in the array are
currently a heap. But I also have a heapSort function that sorts the
elements from smallest to greatest.

When this happens my array is no longer a max heap, and running
printHeap prints out just the first element in the array, since it is
the only element remaining in a heap from the heapSort process. It
seems to me that printHeap should be able to handle the scenario when
heapSort has been run, and the elements are sorted instead of in a
heap. However, the function's name printHeap seems to intuitively
state that you should only be calling this function when the client
has created a data structure that is indeed a heap. (ie after calling
insertHeap, which will insert while maintaining the heap properties).

Therefore if the client wants to print out the sorted array after
running heapSort, the ADT should have a separate printArray function
that prints heapArray's elements from 1 to arraySize. This is in fact
what I have right now, but having two print functions (printHeap and
printArray) seems non-portable style, and potentially confusing to the
client.

Maybe I could have a flag in the heap structure to keep track of when
the array is still a heap, and when I run heapSort that flag gets
turned off. Then printHeap could check for this flag, and if it is
off, print the entire array. However, this would mean that printHeap
is printing something that's not actually a heap, so I dont really
like it.

Is this just an issue of implementation? With proper documentation of
printHeap and printArray, would having the two aforedescribed print
functions be valid?

Thanks for your input,

mordac

[Alexander Bartolich]

begin followup to mordac:

Maybe I could have a flag in the heap structure to keep track of when
the array is still a heap, and when I run heapSort that flag gets
turned off. Then printHeap could check for this flag, and if it is
off, print the entire array. However, this would mean that printHeap
is printing something that's not actually a heap, so I dont really
like it.

I take it that you are aiming for beauty, not strict performance.
In that case I recommend a function pointer.

typedef void (*pfnPrintHeap) (const heapStruct*);

Add one member to this heapStruct, lets say

pfnPrintHeap print;

Using the print facility then looks like this:

heapStruct heap;
/*
* do whatever to initialize and sort
*/
heap->print(heap);

The actual function name can then be hidden completely.

--
Für Google, Tux und GPL!

[bluness]

#include <stdio.h>

main()
{
for(;;)
{
printf ("Hello Max Heap Data Structure!\n");
}
}

mo****@crackhea d.org (mordac) wrote in message news:<ca******* *************** ****@posting.go ogle.com>...

Hello, I was wondering if I could get some opinions on how best to
handle printing in a max heap data structure. Right now my heap
struct looks as thus:
typedef struct heapStruct {
int* heapArray;
int heapSize;
int arraySize;
int maxSize;
} heapStruct;
arraySize holds the current number of elements in the array.
maxSize is the total size of the array (so we know when to realloc).
And heapSize is the current size of the heap in the array.
heapsize <= arraySize <= maxSize.

I have a printHeap function that prints the elements in the heapArray
from 1 to heapSize. This works great if the elements in the array are
currently a heap. But I also have a heapSort function that sorts the
elements from smallest to greatest.

When this happens my array is no longer a max heap, and running
printHeap prints out just the first element in the array, since it is
the only element remaining in a heap from the heapSort process. It
seems to me that printHeap should be able to handle the scenario when
heapSort has been run, and the elements are sorted instead of in a
heap. However, the function's name printHeap seems to intuitively
state that you should only be calling this function when the client
has created a data structure that is indeed a heap. (ie after calling
insertHeap, which will insert while maintaining the heap properties).

Therefore if the client wants to print out the sorted array after
running heapSort, the ADT should have a separate printArray function
that prints heapArray's elements from 1 to arraySize. This is in fact
what I have right now, but having two print functions (printHeap and
printArray) seems non-portable style, and potentially confusing to the
client.

Maybe I could have a flag in the heap structure to keep track of when
the array is still a heap, and when I run heapSort that flag gets
turned off. Then printHeap could check for this flag, and if it is
off, print the entire array. However, this would mean that printHeap
is printing something that's not actually a heap, so I dont really
like it.

Is this just an issue of implementation? With proper documentation of
printHeap and printArray, would having the two aforedescribed print
functions be valid?

Thanks for your input,

mordac