473,320 Members | 1,950 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

max heap and print implementation question

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
Nov 14 '05 #1
2 7488
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!
Nov 14 '05 #2
#include <stdio.h>

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

mo****@crackhead.org (mordac) wrote in message news:<ca**************************@posting.google. 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

Nov 14 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

14
by: Kevin Grigorenko | last post by:
Hello, I couldn't find an obvious answer to this in the FAQ. My basic question, is: Is there any difference in allocating on the heap versus the stack? If heap or stack implementation is not...
15
by: John Doe | last post by:
Hi all, I know the standard doesn't care about threads (wrongly :-) But in current compilers implementation, is the "list" which holds count of the occupied and free heap addresses SHARED among...
17
by: Jonas Rundberg | last post by:
Hi I just started with c++ and I'm a little bit confused where stuff go... Assume we have a class: class test { private: int arr; };
9
by: gold | last post by:
Hello all, I want know abt wht kind of datastructures using both C & C++ internally. Some were said heap, others said tree anyone can explain brief?
5
by: Ook | last post by:
I'm not sure this is technically a c++ question, maybe there is a better ng to ask, but I'll start here since I'm coding this in c++. What exactly is a max heap, and more specifically, how do you...
24
by: arcticool | last post by:
I had an interview today and I got destroyed :( The question was why have a stack and a heap? I could answer all the practical stuff like value types live on the stack, enums are on the stack, as...
0
by: rnot | last post by:
My code is working but I am not sure why. Is it because of the copy constructor? Is it becuase I still didn't define the distructor? (I did define an empty one) I am adding a psaudo code: ...
53
by: fdmfdmfdm | last post by:
This is an interview question and I gave out my answer here, could you please check for me? Q. What are the memory allocation for static variable in a function, an automatic variable and global...
1
by: wishbone34 | last post by:
Hi, I have a question regarding the use of a couple functions I have for an assignment.. first here is the header file that im trying to use...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.