Converting a list to a heap... (probably easy!)

This is a discussion on Converting a list to a heap... (probably easy!) within the C Programming forums, part of the General Programming Boards category; I've been presented with the question... "Convert the following list into a heap: 12 19 33 26 29 35 22" ...

  1. #1
    Registered User mlupo's Avatar
    Join Date
    Oct 2001
    Posts
    72

    Converting a list to a heap... (probably easy!)

    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!

  2. #2
    Green Member Cshot's Avatar
    Join Date
    Jun 2002
    Posts
    892
    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

  3. #3
    Registered User mlupo's Avatar
    Join Date
    Oct 2001
    Posts
    72
    So would that be
    Code:
     int array = malloc(sizeof(int)*7);
    right?

    Thanks,
    Mike
    NEVER PET YOUR DOG WHILE IT'S ON FIRE!

  4. #4
    Green Member Cshot's Avatar
    Join Date
    Jun 2002
    Posts
    892
    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

  5. #5
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 10:01 PM
  2. Replies: 6
    Last Post: 03-02-2005, 01:45 AM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 08:27 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21