I've been presented with the question...
"Convert the following list into a heap: 12 19 33 26 29 35 22"
I figure that this can be accomplished a few ways.
1) moved into memory that is dymanically allocated
2) pushed onto a stack (a specific implementation of step I presume)
Am I correct in this assumption?
What would be your approach if you were asked this question.
Thanks in advance,
Mike
NEVER PET YOUR DOG WHILE IT'S ON FIRE!
If the only operations required is to create a heap, I'd just dynamically create an array (size = 7 in your example) and then treat that as if it were a heap by inserting the values in the correct slot.
Try not.
Do or do not.
There is no try.
- Master Yoda
So would that be
right?Code:int array = malloc(sizeof(int)*7);
Thanks,
Mike
NEVER PET YOUR DOG WHILE IT'S ON FIRE!
No. It'd be
int *array = malloc(sizeof(int) * 7);
However, the logic may be easier if you defined a structure with left and right pointers along with the int value. There's many ways to implement a heap. Do a search for "data structures heap". You'll find far better illustrations than what we can provide you here.
Try not.
Do or do not.
There is no try.
- Master Yoda
Usually though it's best to implement it with
int* array = malloc(sizeof(int) * 8); and leave the array[0]
unused. This is so that you can define
PARENT(i) = i / 2, LEFT_CHILD(i) = i * 2, RIGHT_CHILD(i) = i * 2 +1. Copy the list to the array. And then use the standard
algorithm to build a heap from a ordinary array.
