Array based Binary Heap in C

Discussion in 'C Programming' started by arnuld, Oct 28, 2009.

  1. arnuld

    arnuld Guest

    After discussing in my other thread titled "A C implementation of Binary
    Heap", I have done this attempt of coding and came with this code makes a
    proper Binary Heap inside the array without any problems so far.

    I am posting the code for verification of my assumptions and of course as
    usual for any advice on improvements. Does anyone see a hidden bug inside
    the program before I go on extending it to completion. Any advice will be
    appreciated :)

    If array has five elements then this should be the Binary-Heap, correct
    me if I am wrong:

    P5
    / \
    P4 P3
    / \
    P2 P1

    (section 9.2, Algorithms in C - Robert Sedgewick)


    NOTE: one strange thing though, I am using -ansi flgg rather than -
    std=c99 with gcc but then why it does not report any warning/error if I
    am using __func__ , a C99 facility, not present in C90


    /* A simple implementation of Priority Queue using a heap-based array. We
    will be using it for 3 operations:
    *
    * (1) Insert an element with some priority in the PQ. No duplicate
    elements.
    * (2) Delete the element with highest priority.
    * (3) find the element with highest priority.
    *
    *
    * VERSION 0.0
    *
    */




    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>


    /* we are going to use an array of pointers, a pointer takes 4 bytes, so
    using an array of 100,000 elements = 400 KB, which is an amount
    of memory too small to be concerned about when we 64 MB of RAM at our
    disposal. 10,000 is the minimum number of elements we will
    be needing. In an average case we will need to use 100,000 elements,
    hence the number of element in the array */
    enum { SIZE_ARR = 100000 };


    enum { SIZE_PRIO = 20,
    SIZE_GRADE = 20
    };


    enum BOOL { NO = 0,
    YES = 1,
    VAL_FAIL = NO,
    VAL_SUCC = YES};


    struct pq_element
    {
    char priority[SIZE_PRIO];
    char grade[SIZE_GRADE];
    };


    struct pq_element* PQ_arr[SIZE_ARR] = {0};
    static long int N = -1;


    struct pq_element* PQ_create_element(char [], char []);
    void PQ_insert(struct pq_element* );


    void PQ_remove(struct pq_element* [], long, long);
    void PQ_heapify_up(long int );

    enum BOOL PQ_element_exists(struct pq_element* );
    enum BOOL PQ_comp_less(struct pq_element*, struct pq_element*);
    void PQ_swap_elements(struct pq_element**, struct pq_element** );

    void PQ_print(struct pq_element** );
    void PQ_print_single_element(struct pq_element* );

    int main(void)
    {
    struct pq_element* a1 = PQ_create_element("P1", "G-Average");
    struct pq_element* a2 = PQ_create_element("P2", "G-First");
    struct pq_element* a3 = PQ_create_element("P3", "G-First");
    struct pq_element* a4 = PQ_create_element("P4", "G-First");
    struct pq_element* a5 = PQ_create_element("P5", "G-First");


    if(NULL == a1)
    {
    fprintf(stderr, "IN: %s : Memory Exhausted!\n", __func__);
    }


    PQ_insert(a1);
    PQ_insert(a2);
    PQ_insert(a3);
    PQ_insert(a4);
    PQ_insert(a5);
    PQ_insert(a1);

    PQ_print(PQ_arr);

    return 0;
    }



    struct pq_element* PQ_create_element(char prio[], char grd[])
    {
    struct pq_element* p = malloc(1 * sizeof*p);

    if(p)
    {
    strcpy(p->priority, prio);
    strcpy(p->grade, grd);
    }

    return p;
    }


    void PQ_insert(struct pq_element* p)
    {
    if(NULL == p)
    {
    printf("IN: %s, Can not add NULL element to PQ\n", __func__);
    return;
    }

    if(PQ_element_exists(p))
    {
    /* printf("IN: %s:, An element with same priority is already
    present in the queue\n", __func__); */
    return;
    }


    PQ_arr[++N] = p;
    PQ_heapify_up(N);
    }




    enum BOOL PQ_element_exists(struct pq_element* p)
    {
    int i;
    struct pq_element* c;

    for(i = 0; i <= N; ++i)
    {
    c = PQ_arr;

    if(0 == strcmp(c->priority, p->priority))
    {
    return YES;
    }
    }

    return NO;
    }




    void PQ_heapify_up(long int n)
    {
    for( ; (n >= 0) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )
    {
    PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
    }
    }


    /* chekc if first argument has lesser priority than second */
    enum BOOL PQ_comp_less(struct pq_element* b1, struct pq_element* b2)
    {
    int comp;

    /*
    printf("going to compare, N = %ld\n", N);
    printf("b1->priority: %s\nb1->grade: %s\n", b1->priority, b1->grade);
    printf("b2->priority: %s\nb2->grade: %s\n", b2->priority, b2->grade);
    */

    if( (comp = strcmp( b1->priority, b2->priority)) < 0 )
    {
    /* printf("comp YES\n\n"); */
    return YES;
    }

    /* printf("comp NO\n\n"); */
    return NO;
    }


    void PQ_swap_elements(struct pq_element** p, struct pq_element** q)
    {
    struct pq_element* temp = *p;
    *p = *q;
    *q = temp;
    }




    void PQ_print(struct pq_element** p)
    {
    for( ; p && *p; ++p)
    {
    PQ_print_single_element(*p);
    }
    }




    void PQ_print_single_element(struct pq_element* p)
    {
    if(p)
    {
    printf("priority: %s\n", p->priority);
    printf("grade: %s\n\n", p->grade);
    }
    }


    ======================== OUTPUT ===========================
    [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra PQ-array.c
    [arnuld@dune programs]$ ./a.out
    priority: P5
    grade: G-First

    priority: P4
    grade: G-First

    priority: P3
    grade: G-First

    priority: P2
    grade: G-First

    priority: P1
    grade: G-Average

    [arnuld@dune programs]$







    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Oct 28, 2009
    #1
    1. Advertising

  2. arnuld

    Phil Carmody Guest

    arnuld <> writes:
    > After discussing in my other thread titled "A C implementation of Binary
    > Heap", I have done this attempt of coding and came with this code makes a
    > proper Binary Heap inside the array without any problems so far.
    >
    > I am posting the code for verification of my assumptions and of course as
    > usual for any advice on improvements. Does anyone see a hidden bug inside
    > the program before I go on extending it to completion. Any advice will be
    > appreciated :)
    >
    > If array has five elements then this should be the Binary-Heap, correct
    > me if I am wrong:
    >
    > P5
    > / \
    > P4 P3
    > / \
    > P2 P1


    Assuming the digits imply order, that indeed is a binary heap.

    > (section 9.2, Algorithms in C - Robert Sedgewick)
    >
    >
    > NOTE: one strange thing though, I am using -ansi flgg rather than -
    > std=c99 with gcc but then why it does not report any warning/error if I
    > am using __func__ , a C99 facility, not present in C90
    >
    >
    > /* A simple implementation of Priority Queue using a heap-based array. We
    > will be using it for 3 operations:
    > *
    > * (1) Insert an element with some priority in the PQ. No duplicate
    > elements.
    > * (2) Delete the element with highest priority.
    > * (3) find the element with highest priority.
    > *
    > *
    > * VERSION 0.0
    > *
    > */
    >
    >
    >
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    > #include <string.h>
    >
    >
    > /* we are going to use an array of pointers, a pointer takes 4 bytes, so
    > using an array of 100,000 elements = 400 KB, which is an amount
    > of memory too small to be concerned about when we 64 MB of RAM at our
    > disposal. 10,000 is the minimum number of elements we will
    > be needing. In an average case we will need to use 100,000 elements,
    > hence the number of element in the array */
    > enum { SIZE_ARR = 100000 };
    >
    >
    > enum { SIZE_PRIO = 20,
    > SIZE_GRADE = 20
    > };
    >
    >
    > enum BOOL { NO = 0,
    > YES = 1,
    > VAL_FAIL = NO,
    > VAL_SUCC = YES};
    >
    >
    > struct pq_element
    > {
    > char priority[SIZE_PRIO];
    > char grade[SIZE_GRADE];
    > };
    >
    > struct pq_element* PQ_arr[SIZE_ARR] = {0};
    > static long int N = -1;


    Beware!!!!!
    Heaps indexed from [1] upwards are far easier to deal with, IMHO.
    I bet that there are indexing issues later....

    > struct pq_element* PQ_create_element(char [], char []);
    > void PQ_insert(struct pq_element* );
    >
    >
    > void PQ_remove(struct pq_element* [], long, long);
    > void PQ_heapify_up(long int );
    >
    > enum BOOL PQ_element_exists(struct pq_element* );
    > enum BOOL PQ_comp_less(struct pq_element*, struct pq_element*);
    > void PQ_swap_elements(struct pq_element**, struct pq_element** );
    >
    > void PQ_print(struct pq_element** );
    > void PQ_print_single_element(struct pq_element* );
    >
    > int main(void)
    > {
    > struct pq_element* a1 = PQ_create_element("P1", "G-Average");
    > struct pq_element* a2 = PQ_create_element("P2", "G-First");
    > struct pq_element* a3 = PQ_create_element("P3", "G-First");
    > struct pq_element* a4 = PQ_create_element("P4", "G-First");
    > struct pq_element* a5 = PQ_create_element("P5", "G-First");
    >
    >
    > if(NULL == a1)


    In theory they could all succeed or fail intependently of each other.

    > {
    > fprintf(stderr, "IN: %s : Memory Exhausted!\n", __func__);
    > }
    >
    >
    > PQ_insert(a1);
    > PQ_insert(a2);
    > PQ_insert(a3);
    > PQ_insert(a4);
    > PQ_insert(a5);


    OK, you've got all 5 elements in your structure, if those functions are
    correct.

    > PQ_insert(a1);


    From reading below, I see that this is to check error conditions.

    To check error conditions, you want to test a whole load of examples,
    not just one. Randomise the values.

    > PQ_print(PQ_arr);
    >
    > return 0;
    > }
    >
    >
    >
    > struct pq_element* PQ_create_element(char prio[], char grd[])
    > {
    > struct pq_element* p = malloc(1 * sizeof*p);
    >
    > if(p)
    > {
    > strcpy(p->priority, prio);
    > strcpy(p->grade, grd);


    Beware untrusted callers - they may give you long strings that you
    hang yourself with. Find or write a 'strlcpy' for such purposes.

    > }
    >
    > return p;
    > }
    >
    >
    > void PQ_insert(struct pq_element* p)


    I notice you're assuming only one heap exists, rather than
    passing a pointer to it and its size as a parameter. The latter
    would be more re-usable.

    > {
    > if(NULL == p)
    > {
    > printf("IN: %s, Can not add NULL element to PQ\n", __func__);
    > return;
    > }


    If you trust your callers to obey a no-NULL interface, then you
    could convert that to an assert. But if you don't trust your callers,
    that can stay.

    > if(PQ_element_exists(p))
    > {
    > /* printf("IN: %s:, An element with same priority is already
    > present in the queue\n", __func__); */
    > return;
    > }
    >
    > PQ_arr[++N] = p;
    > PQ_heapify_up(N);
    > }


    Looks OK from here.

    > enum BOOL PQ_element_exists(struct pq_element* p)
    > {
    > int i;
    > struct pq_element* c;
    >
    > for(i = 0; i <= N; ++i)
    > {
    > c = PQ_arr;
    > if(0 == strcmp(c->priority, p->priority))
    > {
    > return YES;


    So priority is your unique key? That's OK.

    > }
    > }
    >
    > return NO;
    > }


    A rather expensive operation, but while developing and debugging
    it can be useful to have expensive sanity checks.

    A good sanity check is one that verifies the heap condition. Implement
    one, and verify that every time you add an element it still satisfies
    the heap condition.

    > void PQ_heapify_up(long int n)
    > {
    > for( ; (n >= 0) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )


    You don't want to be comparing PQ_arr[0] with PQ_arr[0].
    You want to be comparing [1] with [0], and later, you want
    to be comparing [2] with [0]. However, you'll be comparing
    [2] with [1].

    That's the indexing issue I mentioned above.

    > {
    > PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
    > }
    > }
    >
    >
    > /* chekc if first argument has lesser priority than second */
    > enum BOOL PQ_comp_less(struct pq_element* b1, struct pq_element* b2)
    > {
    > int comp;
    >
    > /*
    > printf("going to compare, N = %ld\n", N);
    > printf("b1->priority: %s\nb1->grade: %s\n", b1->priority, b1->grade);
    > printf("b2->priority: %s\nb2->grade: %s\n", b2->priority, b2->grade);
    > */
    >
    > if( (comp = strcmp( b1->priority, b2->priority)) < 0 )
    > {
    > /* printf("comp YES\n\n"); */
    > return YES;
    > }
    >
    > /* printf("comp NO\n\n"); */
    > return NO;
    > }


    Seems OK.

    > void PQ_swap_elements(struct pq_element** p, struct pq_element** q)
    > {
    > struct pq_element* temp = *p;
    > *p = *q;
    > *q = temp;
    > }


    Yup.

    > void PQ_print(struct pq_element** p)
    > {
    > for( ; p && *p; ++p)


    You could run off the end of the array and not know it. You have
    N for a reason - use it.

    > {
    > PQ_print_single_element(*p);
    > }
    > }
    >
    > void PQ_print_single_element(struct pq_element* p)
    > {
    > if(p)
    > {
    > printf("priority: %s\n", p->priority);
    > printf("grade: %s\n\n", p->grade);
    > }
    > }
    >
    >
    > ======================== OUTPUT ===========================
    > [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra PQ-array.c
    > [arnuld@dune programs]$ ./a.out
    > priority: P5
    > grade: G-First
    >
    > priority: P4
    > grade: G-First
    >
    > priority: P3
    > grade: G-First
    >
    > priority: P2
    > grade: G-First
    >
    > priority: P1
    > grade: G-Average
    >
    > [arnuld@dune programs]$


    Given the indexing issues, I'd say that's luck. However, you're
    close, so should be able to hone in on a correct implementation
    pretty soon.

    Phil
    --
    Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
     
    Phil Carmody, Oct 28, 2009
    #2
    1. Advertising

  3. arnuld

    arnuld Guest

    > On Wed, 28 Oct 2009 22:49:52 +0200, Phil Carmody wrote:

    >> arnuld <> writes:
    >> struct pq_element* PQ_arr[SIZE_ARR] = {0}; static long int N = -1;


    > Beware!!!!!
    > Heaps indexed from [1] upwards are far easier to deal with, IMHO. I bet
    > that there are indexing issues later....


    If I start from [1] then n/2 and n in PQ_heapify_up() no longer apply.
    IMHO, I felt lot of difficulty in finding a proper way n/2, n/3, n-1, n-2
    etc but none works.


    BTW, if n/2 and n no longer apply then it will not be binary heap (as per
    definition)




    >> void PQ_insert(struct pq_element* p)

    >
    > I notice you're assuming only one heap exists, rather than passing a
    > pointer to it and its size as a parameter. The latter would be more
    > re-usable.



    Its actually because of the part of the software I am working on where
    the PQ is available at a global level.




    > So priority is your unique key? That's OK.


    yes, and that makes insertions N + N, N for lookup and another N for
    insert, so Sedewick's worst case does not fit in here (Algorithms n C -
    section 9.1)


    > A good sanity check is one that verifies the heap condition. Implement
    > one, and verify that every time you add an element it still satisfies
    > the heap condition.


    What do you mean a /verifying the heap condition/ . PQ_heapify_up()
    already does this for insertion. Later, PQ_heapify_down() will do this
    for deletion. What else if left ?




    >> void PQ_heapify_up(long int n)
    >> {
    >> for( ; (n >= 0) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )

    >
    > You don't want to be comparing PQ_arr[0] with PQ_arr[0]. You want to be
    > comparing [1] with [0], and later, you want to be comparing [2] with
    > [0]. However, you'll be comparing [2] with [1].


    > That's the indexing issue I mentioned above.



    for n = 0 the comparison is between 0,0
    for n = 1 the comparison is between 0,1
    for n = 2 the comparison is between 1,2
    for n = 3 the comparison is between 1,3
    for n = 4 the comparison is between 2,4
    for n = 5 the comparison is between 2,5

    You are right that for n=2, it should compare with 0, not 1 but then I
    have to change that n/2 and n and it will break the requirement for
    Binary Heap. See:


    http://mathworld.wolfram.com/Heap.html

    Also, Section 9.2, Algorithms in C , Sedgewick









    > Given the indexing issues, I'd say that's luck.


    You mean the program is buggy and will not make binary heap every time ?





    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Oct 29, 2009
    #3
  4. arnuld

    arnuld Guest

    > On Wed, 28 Oct 2009 22:49:52 +0200, Phil Carmody wrote:


    > Beware!!!!!
    > Heaps indexed from [1] upwards are far easier to deal with, IMHO. I bet
    > that there are indexing issues later....



    How about this implementation:


    /* A simple implementation of Priority Queue using a heap-based array. We
    will be using it for 3 operations:
    *
    * (1) Insert an element with some priority in the PQ. No duplicate
    elements.
    * (2) Delete the element with highest priority.
    * (3) find the element with highest priority.
    *
    *
    * VERSION 0.1
    *
    */




    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>


    /* we are going to use an array of pointers, a pointer takes 4 bytes, so
    using an array of 100,000 elements = 400 KB, which is an amount
    of memory too small to be concerned about when we 64 MB of RAM at our
    disposal. 10,000 is the minimum number of elements we will
    be needing. In an average case we will need to use 100,000 elements,
    hence the number of element in the array */
    enum { SIZE_ARR = 100000 };


    enum { SIZE_GRADE = 20 };


    enum BOOL { NO = 0,
    YES = 1,
    VAL_FAIL = NO,
    VAL_SUCC = YES};


    struct pq_element
    {
    long int priority;
    char grade[SIZE_GRADE];
    };


    struct pq_element* PQ_arr[SIZE_ARR] = {0};
    static long int N = 1;


    struct pq_element* PQ_create_element(long int, char []);
    void PQ_insert(struct pq_element* );


    void PQ_remove(struct pq_element* [], long, long);
    void PQ_heapify_up(long int );

    enum BOOL PQ_element_exists(struct pq_element* );
    enum BOOL PQ_comp_less(struct pq_element*, struct pq_element*);
    void PQ_swap_elements(struct pq_element**, struct pq_element** );

    void PQ_print(struct pq_element**, long int );
    void PQ_print_single_element(struct pq_element* );

    int main(void)
    {
    struct pq_element* a1 = PQ_create_element(1, "G-Average");
    struct pq_element* a2 = PQ_create_element(2, "G-First");
    struct pq_element* a3 = PQ_create_element(3, "G-First");
    struct pq_element* a4 = PQ_create_element(4, "G-First");
    struct pq_element* a5 = PQ_create_element(5, "G-First");
    struct pq_element* a6 = PQ_create_element(6, "G-First");
    struct pq_element* a21 = PQ_create_element(21, "G-First");
    struct pq_element* a20 = PQ_create_element(20, "G-First");

    if(NULL == a1)
    {
    fprintf(stderr, "IN: %s : Memory Exhausted!\n", __func__);
    }


    PQ_insert(a2);
    PQ_insert(a20);
    PQ_insert(a1);
    PQ_insert(a4);
    PQ_insert(a3);
    PQ_insert(a21);
    PQ_insert(a6);
    PQ_insert(a5);
    PQ_insert(a21);
    PQ_insert(a21);

    PQ_print(PQ_arr, N);

    return 0;
    }



    struct pq_element* PQ_create_element(long int d, char grd[])
    {
    struct pq_element* p = malloc(1 * sizeof*p);

    if(p)
    {
    p->priority = d;
    strcpy(p->grade, grd);
    }

    return p;
    }


    /* Total instertion time will be N + N = 2N, N for instertion, N for
    duplicacy check */
    void PQ_insert(struct pq_element* p)
    {
    if(NULL == p)
    {
    printf("IN: %s, Can not add NULL element to PQ\n", __func__);
    return;
    }

    if(PQ_element_exists(p))
    {
    /* printf("IN: %s:, An element with same priority is already
    present in the queue\n", __func__); */
    return;
    }


    PQ_arr[N] = p;
    PQ_heapify_up(N++);
    }




    /* This is log(N) */
    enum BOOL PQ_element_exists(struct pq_element* p)
    {
    int i;
    struct pq_element* c;

    for(i = 1; i <= N; ++i)
    {
    c = PQ_arr;

    if( c && (c->priority == p->priority))
    {
    printf("element_EXISTS YES\n");
    return YES;
    }
    }


    printf("element_EXISTS NO\n");
    return NO;
    }




    void PQ_heapify_up(long int n)
    {
    for( ; (n > 1) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )
    {
    PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
    }
    }


    /* chekc if first argument has lesser priority than second */
    enum BOOL PQ_comp_less(struct pq_element* b1, struct pq_element* b2)
    {
    /*
    printf("going to compare, N = %ld\n", N);
    printf("b1->priority: %s\nb1->grade: %s\n", b1->priority, b1->grade);
    printf("b2->priority: %s\nb2->grade: %s\n", b2->priority, b2->grade);
    */

    if((b1->priority < b2->priority))
    {
    /* printf("comp YES\n\n"); */
    return YES;
    }

    /* printf("comp NO\n\n"); */
    return NO;
    }


    void PQ_swap_elements(struct pq_element** p, struct pq_element** q)
    {
    struct pq_element* temp = *p;
    *p = *q;
    *q = temp;
    }




    /* ---------------------------- General Printing Functions
    -------------------------------- */
    void PQ_print(struct pq_element** p, long int n)
    {
    for(int i=0; i <= n; ++i)
    {
    PQ_print_single_element(p);
    }
    }


    void PQ_print_single_element(struct pq_element* p)
    {
    if(p) printf("%ld --> %s \n", p->priority, p->grade);
    }


    ====================== OUTPUT =================================
    [arnuld@dune programs]$ gcc -std=c99 -pedantic -Wall -Wextra PQ-array.c
    [arnuld@dune programs]$ ./a.out
    element_EXISTS NO
    element_EXISTS NO
    element_EXISTS NO
    element_EXISTS NO
    element_EXISTS NO
    element_EXISTS NO
    element_EXISTS NO
    element_EXISTS NO
    element_EXISTS YES
    element_EXISTS YES
    21 --> G-First
    5 --> G-First
    20 --> G-First
    4 --> G-First
    3 --> G-First
    1 --> G-Average
    6 --> G-First
    2 --> G-First
    [arnuld@dune programs]$




    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Oct 29, 2009
    #4
  5. arnuld

    arnuld Guest

    Full fledged version of Array based Binary Heap. Any suggestions ?




    /* A simple implementation of Priority Queue using a heap-based array. We
    will be using it for 3 operations:
    *
    * (1) Insert an element with some priority in the PQ. No duplicate
    elements.
    * (2) Delete the element with highest priority.
    * (3) find the element with highest priority.
    *
    *
    * VERSION 0.2
    *
    */




    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>


    /* we are going to use an array of pointers, a pointer takes 4 bytes, so
    using an array of 100,000 elements = 400 KB, which is an amount
    of memory too small to be concerned about when we 64 MB of RAM at our
    disposal. 10,000 is the minimum number of elements we will
    be needing. In an average case we will need to use 100,000 elements,
    hence the number of element in the array */
    enum { SIZE_ARR = 100000,
    SIZE_GRADE = 20 };

    enum { POSITION_MAX = 1 };

    enum BOOL { NO = 0,
    YES = 1,
    VAL_FAIL = NO,
    VAL_SUCC = YES};


    struct pq_element
    {
    long int priority;
    char grade[SIZE_GRADE];
    };


    struct pq_element* PQ_arr[SIZE_ARR] = {0};
    static long int N = 0;


    struct pq_element* PQ_create_element(long int, char []);
    void PQ_insert(struct pq_element* );



    void PQ_heapify_up(long int );
    struct pq_element* PQ_find_max(struct pq_element** );
    void PQ_heapify_down(long int nd);
    void PQ_remove_max(void);
    void PQ_remove(long int);


    enum BOOL PQ_element_exists(struct pq_element* );
    enum BOOL PQ_comp_less(struct pq_element*, struct pq_element*);
    void PQ_swap_elements(struct pq_element**, struct pq_element** );
    void PQ_free_single_element(struct pq_element** );

    void PQ_print(struct pq_element**, long int );
    void PQ_print_single_element(struct pq_element* );


    int main(void)
    {
    struct pq_element* a1 = PQ_create_element(1, "G-Average");
    struct pq_element* a2 = PQ_create_element(2, "G-First");
    struct pq_element* a3 = PQ_create_element(3, "G-First");
    struct pq_element* a4 = PQ_create_element(4, "G-First");
    struct pq_element* a5 = PQ_create_element(5, "G-First");
    struct pq_element* a6 = PQ_create_element(6, "G-First");
    struct pq_element* a21 = PQ_create_element(21, "G-First");
    struct pq_element* a20 = PQ_create_element(20, "G-First");


    PQ_insert(a2);
    PQ_insert(a20);
    PQ_insert(a1);
    PQ_insert(a4);

    PQ_insert(a3);
    PQ_insert(a21);

    PQ_insert(a6);
    PQ_insert(a5);
    PQ_insert(a21);
    PQ_insert(a21);


    PQ_print(PQ_arr, N);
    PQ_remove_max();
    printf("\n\n --------------- Array after MAX removed ------------------
    \n\n");
    PQ_print(PQ_arr, N);


    return 0;
    }



    struct pq_element* PQ_create_element(long int d, char grd[])
    {
    struct pq_element* p = malloc(1 * sizeof*p);

    if(p)
    {
    p->priority = d;
    strcpy(p->grade, grd);
    }

    return p;
    }


    /* Total instertion time will be N + N = 2N, N for instertion, N for
    duplicacy check */
    void PQ_insert(struct pq_element* p)
    {
    if(NULL == p)
    {
    return;
    }

    if(PQ_element_exists(p))
    {
    return;
    }


    PQ_arr[++N] = p;
    PQ_heapify_up(N);
    }



    /* (1) Swap the last element of the right subtree with the element with
    max priority (root)
    (2) delete the root
    (3) heapify-down the new root till we get a heap ordered tree.

    Requires 2N comparisons in worst case.
    */
    void PQ_remove_max(void)
    {
    PQ_remove(POSITION_MAX);
    }

    void PQ_remove(long int pos)
    {
    if(N > 0 )
    {
    PQ_swap_elements(&PQ_arr[pos], &PQ_arr[N]);

    PQ_free_single_element(&PQ_arr[N]);
    PQ_arr[N--] = NULL;

    PQ_heapify_down(pos);
    }
    }


    void PQ_heapify_up(long int n)
    {
    for( ; (n > 1) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )
    {
    PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
    }
    }



    void PQ_heapify_down(long int nd)
    {
    long node_left, node_right, node_comp;

    node_left = 2 * nd;
    node_right = (2 * nd) + 1;

    while(node_left <= N)
    {
    node_left = 2 * nd;
    node_right = (2 * nd) + 1;


    if( node_left < N && PQ_comp_less(PQ_arr[node_left], PQ_arr
    [node_right]))
    {
    node_comp = node_right;
    }
    else
    {
    node_comp = node_left;
    }


    if( YES == PQ_comp_less(PQ_arr[node_comp], PQ_arr[nd]) )
    {
    break;
    }

    PQ_swap_elements(&PQ_arr[node_comp], &PQ_arr[nd]);
    nd = node_comp;
    }
    }





    struct pq_element* PQ_find_max(struct pq_element** arr)
    {
    if(arr)
    {
    return arr[POSITION_MAX];
    }

    return NULL;
    }


    /* ------------------ Small Helper Functions ------------------------ */

    /* This is log(N) */
    enum BOOL PQ_element_exists(struct pq_element* p)
    {
    int i;
    struct pq_element* c;

    for(i = 1; i <= N; ++i)
    {
    c = PQ_arr;

    if( c && (c->priority == p->priority))
    {
    return YES;
    }
    }

    return NO;
    }



    /* chekc if first argument has lesser priority than second */
    enum BOOL PQ_comp_less(struct pq_element* b1, struct pq_element* b2)
    {
    if((NULL == b1) || (NULL == b2))
    {
    return YES;
    }


    if((b1->priority < b2->priority))
    {
    return YES;
    }

    return NO;
    }


    void PQ_swap_elements(struct pq_element** p, struct pq_element** q)
    {
    struct pq_element* temp = *p;
    *p = *q;
    *q = temp;
    }


    void PQ_free_single_element(struct pq_element** p)
    {
    free(*p);
    *p = NULL;
    }


    /* ---------------------------- General Printing Functions
    -------------------------------- */
    void PQ_print(struct pq_element** p, long int n)
    {
    int i;

    printf("N = %ld\n", n);
    for(i = 0; i <= n; ++i)
    {
    PQ_print_single_element(p);
    }

    printf("+++++++\n\n");
    }


    void PQ_print_single_element(struct pq_element* p)
    {
    if(p) printf("%ld --> %s \n", p->priority, p->grade);
    }


    ===================== OUTPUT ============================
    [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra PQ.c
    [arnuld@dune programs]$ ./a.out
    N = 8
    21 --> G-First
    5 --> G-First
    20 --> G-First
    4 --> G-First
    3 --> G-First
    1 --> G-Average
    6 --> G-First
    2 --> G-First
    +++++++



    --------------- Array after MAX removed ------------------

    N = 7
    20 --> G-First
    5 --> G-First
    6 --> G-First
    4 --> G-First
    3 --> G-First
    1 --> G-Average
    2 --> G-First
    +++++++

    [arnuld@dune programs]$



    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Oct 29, 2009
    #5
  6. arnuld

    Phil Carmody Guest

    arnuld <> writes:
    >> On Wed, 28 Oct 2009 22:49:52 +0200, Phil Carmody wrote:

    >
    >>> arnuld <> writes:
    >>> struct pq_element* PQ_arr[SIZE_ARR] = {0}; static long int N = -1;

    >
    >> Beware!!!!!
    >> Heaps indexed from [1] upwards are far easier to deal with, IMHO. I bet
    >> that there are indexing issues later....

    >
    > If I start from [1] then n/2 and n in PQ_heapify_up() no longer apply.


    Wrong. Try again. Aim for correctness this time.

    > IMHO, I felt lot of difficulty in finding a proper way n/2, n/3, n-1, n-2
    > etc but none works.


    Did you try my previous suggestion?

    > BTW, if n/2 and n no longer apply then it will not be binary heap (as per
    > definition)


    Wrong. You are confusing the indexes in an array and the indexes within
    the heap. The fact that you are confused is because you have ignored
    the advice which I gave which reduces the amount of confusion. If you
    prefer confusing yourself, just say so, and I'll not waste time trying
    to help you any more, it's no skin off my nose.

    >> A good sanity check is one that verifies the heap condition. Implement
    >> one, and verify that every time you add an element it still satisfies
    >> the heap condition.

    >
    > What do you mean a /verifying the heap condition/ .


    Checking that the heap condition holds for all nodes in the heap.

    > PQ_heapify_up()
    > already does this for insertion. Later, PQ_heapify_down() will do this
    > for deletion. What else if left ?


    They don't check the whole heap. They only modify (and break currently)
    a subset of the tree.

    >>> void PQ_heapify_up(long int n)
    >>> {
    >>> for( ; (n >= 0) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )

    >>
    >> You don't want to be comparing PQ_arr[0] with PQ_arr[0]. You want to be
    >> comparing [1] with [0], and later, you want to be comparing [2] with
    >> [0]. However, you'll be comparing [2] with [1].

    >
    >> That's the indexing issue I mentioned above.

    >
    >
    > for n = 0 the comparison is between 0,0


    which is pointless

    > for n = 1 the comparison is between 0,1


    which is correct

    > for n = 2 the comparison is between 1,2


    which is wrong

    > for n = 3 the comparison is between 1,3


    which is correct

    > for n = 4 the comparison is between 2,4


    which is wrong

    > for n = 5 the comparison is between 2,5


    which is correct

    > You are right that for n=2, it should compare with 0, not 1 but then I
    > have to change that n/2 and n and it will break the requirement for
    > Binary Heap.


    Wrong. Not if you do it correctly. That's the bit *you* are failing
    to do currently, not me.

    > See:


    I don't need references, I can already do this with my eyes closed.

    >> Given the indexing issues, I'd say that's luck.

    >
    > You mean the program is buggy and will not make binary heap every time ?


    Yes.

    Phil
    --
    Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
     
    Phil Carmody, Oct 29, 2009
    #6
  7. arnuld

    Phil Carmody Guest

    arnuld <> writes:
    >> On Wed, 28 Oct 2009 22:49:52 +0200, Phil Carmody wrote:

    >
    >
    >> Beware!!!!!
    >> Heaps indexed from [1] upwards are far easier to deal with, IMHO. I bet
    >> that there are indexing issues later....

    >
    >
    > How about this implementation:


    > static long int N = 1;


    > /* Total instertion time will be N + N = 2N, N for instertion, N for
    > duplicacy check */


    It's not necessary to have uniquely keyed elements in a heap,
    so you don't need the uniqueness test in order to be a heap.
    And insertion's not N operations, it's O(lg(N)) operations.

    > void PQ_insert(struct pq_element* p)
    > {
    > if(NULL == p)
    > {
    > printf("IN: %s, Can not add NULL element to PQ\n", __func__);
    > return;
    > }
    >
    > if(PQ_element_exists(p))
    > {
    > /* printf("IN: %s:, An element with same priority is already
    > present in the queue\n", __func__); */
    > return;
    > }
    >
    >
    > PQ_arr[N] = p;


    So the first insertion goes into slot [1], good.

    > PQ_heapify_up(N++);


    I prefer to keep the side-effects on global variables out of the
    function calls, for readability. (The function called might depend
    on that global variable, and the "post-"increment is actually done
    before the function call, not after it.

    However, subsequent items will be temprorarily placed in [2], [3], ...
    good.

    > }
    >
    > void PQ_heapify_up(long int n)


    Here n = N-1, and represents the actual number of elements in the
    heap.

    > {
    > for( ; (n > 1) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )


    Looks good.

    > {
    > PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
    > }
    > }


    > ====================== OUTPUT =================================
    > [arnuld@dune programs]$ gcc -std=c99 -pedantic -Wall -Wextra PQ-array.c
    > [arnuld@dune programs]$ ./a.out
    > element_EXISTS NO
    > element_EXISTS NO
    > element_EXISTS NO
    > element_EXISTS NO
    > element_EXISTS NO
    > element_EXISTS NO
    > element_EXISTS NO
    > element_EXISTS NO
    > element_EXISTS YES
    > element_EXISTS YES
    > 21 --> G-First
    > 5 --> G-First
    > 20 --> G-First
    > 4 --> G-First
    > 3 --> G-First
    > 1 --> G-Average
    > 6 --> G-First
    > 2 --> G-First
    > [arnuld@dune programs]$


    Which looks like a heap. Congratulations.

    Phil
    --
    Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
     
    Phil Carmody, Oct 30, 2009
    #7
  8. arnuld

    Phil Carmody Guest

    arnuld <> writes:
    > Full fledged version of Array based Binary Heap. Any suggestions ?


    > static long int N = 0;


    > PQ_arr[++N] = p;
    > PQ_heapify_up(N);


    Not read the rest, but that's much better maintainability-wise.

    Phil
    --
    Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
     
    Phil Carmody, Oct 30, 2009
    #8
  9. arnuld

    Chad Guest

    On Oct 28, 1:49 pm, Phil Carmody <>
    wrote:
    > arnuld <> writes:
    > > After discussing in my other thread titled "A C implementation of Binary
    > > Heap", I have done this attempt of coding and came with this code makes a
    > > proper Binary Heap inside the array without any problems so far.

    >
    > > I am posting the code for verification of my assumptions and of course as
    > > usual for any advice on improvements. Does anyone see a hidden bug inside
    > > the program before I go on extending it to completion. Any advice will be
    > > appreciated  :)

    >
    > > If array has five elements then this should be the Binary-Heap, correct
    > > me if I am wrong:

    >
    > >              P5
    > >            /    \
    > >           P4     P3
    > >         /   \
    > >         P2   P1

    >
    > Assuming the digits imply order, that indeed is a binary heap.
    >
    >
    >
    > > (section 9.2, Algorithms in C - Robert Sedgewick)

    >
    > > NOTE:  one strange thing though, I am using -ansi flgg rather than -
    > > std=c99 with gcc but then why it does not report any warning/error if I
    > > am using __func__ , a C99 facility, not present in C90

    >
    > > /* A simple implementation of Priority Queue using a heap-based array. We
    > > will be using it for 3 operations:
    > >  *
    > >  * (1) Insert an element with some priority in the PQ. No duplicate
    > > elements.
    > >  * (2) Delete the element with highest priority.
    > >  * (3) find the element with highest priority.
    > >  *
    > >  *
    > >  * VERSION 0.0
    > >  *
    > >  */

    >
    > > #include <stdio.h>
    > > #include <stdlib.h>
    > > #include <string.h>

    >
    > > /* we are going to use an array of pointers, a pointer takes 4 bytes, so
    > > using an array of 100,000 elements = 400 KB, which is an amount
    > >    of memory too small to be concerned about when we 64 MB of RAM at our
    > > disposal. 10,000 is the minimum number of elements we will
    > >    be needing. In an average case we will need to use 100,000 elements,
    > > hence the number of element in the array */
    > > enum { SIZE_ARR = 100000 };

    >
    > > enum { SIZE_PRIO  = 20,
    > >        SIZE_GRADE = 20
    > > };

    >
    > > enum BOOL { NO = 0,
    > >        YES = 1,
    > >        VAL_FAIL = NO,
    > >        VAL_SUCC = YES};

    >
    > > struct pq_element
    > > {
    > >   char priority[SIZE_PRIO];
    > >   char grade[SIZE_GRADE];
    > > };

    >
    > > struct pq_element* PQ_arr[SIZE_ARR] = {0};
    > > static long int N = -1;

    >
    > Beware!!!!!
    > Heaps indexed from [1] upwards are far easier to deal with, IMHO.
    > I bet that there are indexing issues later....
    >
    >
    >
    > > struct pq_element* PQ_create_element(char [], char []);
    > > void PQ_insert(struct pq_element* );

    >
    > > void PQ_remove(struct pq_element* [], long, long);
    > > void PQ_heapify_up(long int );

    >
    > > enum BOOL PQ_element_exists(struct pq_element* );
    > > enum BOOL PQ_comp_less(struct pq_element*, struct pq_element*);
    > > void PQ_swap_elements(struct pq_element**, struct pq_element** );

    >
    > > void PQ_print(struct pq_element** );
    > > void PQ_print_single_element(struct pq_element* );

    >
    > > int main(void)
    > > {
    > >   struct pq_element* a1 = PQ_create_element("P1", "G-Average");
    > >   struct pq_element* a2 = PQ_create_element("P2", "G-First");
    > >   struct pq_element* a3 = PQ_create_element("P3", "G-First");
    > >   struct pq_element* a4 = PQ_create_element("P4", "G-First");
    > >   struct pq_element* a5 = PQ_create_element("P5", "G-First");

    >
    > >   if(NULL == a1)

    >
    > In theory they could all succeed or fail intependently of each other.
    >
    > >     {
    > >       fprintf(stderr, "IN: %s : Memory Exhausted!\n", __func__);
    > >     }

    >
    > >   PQ_insert(a1);
    > >   PQ_insert(a2);
    > >   PQ_insert(a3);
    > >   PQ_insert(a4);
    > >   PQ_insert(a5);

    >
    > OK, you've got all 5 elements in your structure, if those functions are
    > correct.
    >
    > >   PQ_insert(a1);

    >
    > From reading below, I see that this is to check error conditions.
    >
    > To check error conditions, you want to test a whole load of examples,
    > not just one. Randomise the values.
    >
    > >   PQ_print(PQ_arr);

    >
    > >   return 0;
    > > }

    >
    > > struct pq_element* PQ_create_element(char prio[], char grd[])
    > > {
    > >   struct pq_element* p = malloc(1 * sizeof*p);

    >
    > >   if(p)
    > >     {
    > >       strcpy(p->priority, prio);
    > >       strcpy(p->grade, grd);

    >
    > Beware untrusted callers - they may give you long strings that you
    > hang yourself with. Find or write a 'strlcpy' for such purposes.
    >


    Couldn't he/she/it (by 'it', I mean a man posing as a woman, or a
    woman posing as a man) do something like...

    (void) strcpy(p->priority, prio);
    (void) strcpy(p->grade, grd);

    In this case? Just curious, because in some production level code I've
    seen programmers do the following..

    (void)strncpy(...);

    Please note that this is strncpy() and not strcpy().
     
    Chad, Oct 30, 2009
    #9
  10. arnuld

    arnuld Guest

    > On Fri, 30 Oct 2009 02:05:11 +0200, Phil Carmody wrote:

    > It's not necessary to have uniquely keyed elements in a heap, so you
    > don't need the uniqueness test in order to be a heap. And insertion's
    > not N operations, it's O(lg(N)) operations.



    And my Binary-Heap *does* need to have unique keys, If I don't then my
    boss will find someone else to do the job.



    > They don't check the whole heap. They only modify (and break currently)
    > a subset of the tree.


    Did you mean Heapsort ?




    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Oct 30, 2009
    #10
  11. arnuld

    Phil Carmody Guest

    arnuld <> writes:
    >> On Fri, 30 Oct 2009 02:05:11 +0200, Phil Carmody wrote:

    >
    >> It's not necessary to have uniquely keyed elements in a heap, so you
    >> don't need the uniqueness test in order to be a heap. And insertion's
    >> not N operations, it's O(lg(N)) operations.

    >
    > And my Binary-Heap *does* need to have unique keys, If I don't then my
    > boss will find someone else to do the job.


    In that case, you've probably chosen the wrong data structure.
    Perhaps your boss should find someone else to do the job?

    >> They don't check the whole heap. They only modify (and break currently)
    >> a subset of the tree.

    >
    > Did you mean Heapsort ?


    I meant what I wrote, nothing more, and nothing less.

    Phil
    --
    Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
     
    Phil Carmody, Oct 30, 2009
    #11
  12. arnuld

    user923005 Guest

    On Oct 30, 12:24 am, arnuld <> wrote:
    > > On Fri, 30 Oct 2009 02:05:11 +0200, Phil Carmody wrote:
    > > It's not necessary to have uniquely keyed elements in a heap, so you
    > > don't need the uniqueness test in order to be a heap. And insertion's
    > > not N operations, it's O(lg(N)) operations.

    >
    > And my Binary-Heap *does* need to have unique keys, If I don't then my
    > boss will find someone else to do the job.


    Why write a heap from scratch? There are zillions of them laying
    around, all over the planet. Two minutes with a web search beats 2
    days in edit/compile/test any day.

    And if you need a priority queue why not just pick up one of the
    dozens and dozens of freely available, thoroughly tested priority
    queues that are laying around all over the sidewalk?

    > > They don't check the whole heap. They only modify (and break currently)
    > > a subset of the tree.

    >
    > Did you mean Heapsort ?


    Turning a heap into heapsort is trivial. And if you write your own
    heapsort, I'm going to be sick, unless it's just for fun or learning
    in which case it is fine.

    P.S.
    Have a look at Lamont's heap.
     
    user923005, Oct 30, 2009
    #12
  13. arnuld

    arnuld Guest

    > On Fri, 30 Oct 2009 19:45:07 +0200, Phil Carmody wrote:

    >> arnuld <> writes:
    >> And my Binary-Heap *does* need to have unique keys, If I don't then my
    >> boss will find someone else to do the job.


    > In that case, you've probably chosen the wrong data structure. Perhaps
    > your boss should find someone else to do the job?



    I was told create a Binary-Heap with unique keys, inserting element with
    priority, finding/deleting the element with max priority and I did it
    (with CLC's help of course)



    >> Did you mean Heapsort ?


    > I meant what I wrote, nothing more, and nothing less.


    That is I did not get, I did not understand what you asked of me to do.






    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Nov 2, 2009
    #13
  14. arnuld

    arnuld Guest

    > On Wed, 28 Oct 2009 10:33:44 +0000, arnuld wrote:

    > struct pq_element* PQ_arr[SIZE_ARR] = {0}; static long int N = -1;
    >
    > ...SNIP....




    > void PQ_insert(struct pq_element* p)
    > {
    > if(NULL == p)
    > {
    > printf("IN: %s, Can not add NULL element to PQ\n", __func__);
    > return;
    > }
    >
    > if(PQ_element_exists(p))
    > {
    > /* printf("IN: %s:, An element with same priority is already
    > present in the queue\n", __func__); */
    > return;
    > }
    >
    >
    > PQ_arr[++N] = p;
    > PQ_heapify_up(N);
    > }


    What about reallocating the memory when array is full ? (it will be
    full).

    I can not reassign the array to some another realloc()ed pointer. Does
    that mean I must not use array but a pointer ?




    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Nov 2, 2009
    #14
  15. arnuld

    user923005 Guest

    On Nov 1, 10:37 pm, arnuld <> wrote:
    > > On Wed, 28 Oct 2009 10:33:44 +0000, arnuld wrote:
    > > struct pq_element* PQ_arr[SIZE_ARR] = {0}; static long int N = -1;

    >
    > > ...SNIP....
    > > void PQ_insert(struct pq_element* p)
    > > {
    > >   if(NULL == p)
    > >     {
    > >       printf("IN: %s, Can not add NULL element to PQ\n", __func__);
    > >       return;
    > >     }

    >
    > >   if(PQ_element_exists(p))
    > >     {
    > >       /*      printf("IN: %s:, An element with same priority is already
    > > present in the queue\n", __func__);  */
    > >       return;
    > >     }

    >
    > >   PQ_arr[++N] = p;
    > >   PQ_heapify_up(N);
    > > }

    >
    > What about reallocating the memory when array is full ?  (it will be
    > full).
    >
    > I can not reassign the array to some another realloc()ed pointer. Does
    > that mean I must not use array but a pointer ?


    If you do not know the maximum size at startup, then a fixed length
    array is not a good choice.
     
    user923005, Nov 2, 2009
    #15
  16. arnuld

    arnuld Guest

    > On Wed, 28 Oct 2009 22:49:52 +0200, Phil Carmody wrote:

    > ..SNIP...


    > Beware!!!!!
    > Heaps indexed from [1] upwards are far easier to deal with, IMHO. I bet
    > that there are indexing issues later....


    > .....SNIP.....


    Since I can not realloc() an array, I am changing the whole program to
    use a pointer rather than array, hence starting from scratch again.






    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Nov 6, 2009
    #16
  17. arnuld <> writes:
    >> On Wed, 28 Oct 2009 22:49:52 +0200, Phil Carmody wrote:

    >
    >> ..SNIP...

    >
    >> Beware!!!!!
    >> Heaps indexed from [1] upwards are far easier to deal with, IMHO. I bet
    >> that there are indexing issues later....

    >
    >> .....SNIP.....

    >
    > Since I can not realloc() an array, I am changing the whole program to
    > use a pointer rather than array, hence starting from scratch again.


    A quibble: If you're doing what i think you're doing, you'll still be
    using an array. It will just be an array allocated via malloc and/or
    realloc, not one declared as a named array object.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Nov 6, 2009
    #17
  18. arnuld

    arnuld Guest

    > On Fri, 06 Nov 2009 09:48:21 -0800, Keith Thompson wrote:

    >> arnuld <> writes:
    >> Since I can not realloc() an array, I am changing the whole program to
    >> use a pointer rather than array, hence starting from scratch again.


    > A quibble: If you're doing what i think you're doing, you'll still be
    > using an array. It will just be an array allocated via malloc and/or
    > realloc, not one declared as a named array object.


    But I will have to replace this call:


    struct pq_element* p[];

    with

    struct pq_element**;


    which going to cause trouble to functions like this:


    void PQ_heapify_up(unsigned long int n)
    {
    for( ; (n > 1) && PQ_comp_less(PQ_arr[n/2], s[n]); n = n/2 )
    {
    PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
    }
    }


    Here PQ_arr is an array: struct pq_element* PQ_arr[], I cna take the
    address of its element like &PQ_arr[2]. How am I supposed to do that for
    a double-pointer: use a triple-level pointer indirection ?







    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Nov 7, 2009
    #18
  19. On 07 Nov 2009 07:06:11 GMT, arnuld <> wrote:

    >> On Fri, 06 Nov 2009 09:48:21 -0800, Keith Thompson wrote:

    >
    >>> arnuld <> writes:
    >>> Since I can not realloc() an array, I am changing the whole program to
    >>> use a pointer rather than array, hence starting from scratch again.

    >
    >> A quibble: If you're doing what i think you're doing, you'll still be
    >> using an array. It will just be an array allocated via malloc and/or
    >> realloc, not one declared as a named array object.

    >
    >But I will have to replace this call:
    >
    >
    > struct pq_element* p[];
    >
    >with
    >
    > struct pq_element**;
    >
    >
    >which going to cause trouble to functions like this:
    >
    >
    >void PQ_heapify_up(unsigned long int n)
    >{
    > for( ; (n > 1) && PQ_comp_less(PQ_arr[n/2], s[n]); n = n/2 )
    > {
    > PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
    > }
    >}
    >
    >
    >Here PQ_arr is an array: struct pq_element* PQ_arr[], I cna take the
    >address of its element like &PQ_arr[2]. How am I supposed to do that for
    >a double-pointer: use a triple-level pointer indirection ?


    I can't keep track of the different names you are using and the one
    object that has no name. The bottom line is - do not let the slight
    difference in syntax confuse you. For sake of an example, lets assume
    an object of type struct pq_element* is four bytes with four byte
    alignment.

    When you define the array p, it is located somewhere in
    memory. Let's say 0x12345678. Each element of the array is a pointer
    to struct. Element p[0] is located at that address, p[1] is located
    at 0x1234567c, etc. The expression &p[1] will evaluate to 0x1234567c
    with type pointer to struct pq_element* which is just struct
    pq_element**.

    If instead you define p as a pointer to pointer to struct and
    allocate memory, then p will be assigned the value returned by malloc.
    Let's say 0x12345678. The value at that address (denoted by p[0]) has
    type struct pq_element* and is therefore four bytes wide.
    Consequently, the object denoted by p[1] must be located at 0x1234567c
    and is also of type struct pq_element*. The expression &p[1] will
    evaluate to 0x1234567c with type struct pq_element**. Note this is
    exactly the same as the paragraph above.

    Regardless of whether you define the array to hold values or define a
    pointer and allocate space to hold values, you refer to the i-th value
    as p and you refer to the address of this value as &p.

    --
    Remove del for email
     
    Barry Schwarz, Nov 7, 2009
    #19
  20. arnuld <> writes:

    >> On Fri, 06 Nov 2009 09:48:21 -0800, Keith Thompson wrote:

    >
    >>> arnuld <> writes:
    >>> Since I can not realloc() an array, I am changing the whole program to
    >>> use a pointer rather than array, hence starting from scratch again.

    >
    >> A quibble: If you're doing what i think you're doing, you'll still be
    >> using an array. It will just be an array allocated via malloc and/or
    >> realloc, not one declared as a named array object.

    >
    > But I will have to replace this call:
    >
    > struct pq_element* p[];
    >
    > with
    >
    > struct pq_element**;


    It's not a "call", but yes, you will.

    > which going to cause trouble to functions like this:
    >
    >
    > void PQ_heapify_up(unsigned long int n)
    > {
    > for( ; (n > 1) && PQ_comp_less(PQ_arr[n/2], s[n]); n = n/2 )
    > {
    > PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
    > }
    > }
    >
    > Here PQ_arr is an array: struct pq_element* PQ_arr[], I cna take the
    > address of its element like &PQ_arr[2]. How am I supposed to do that for
    > a double-pointer: use a triple-level pointer indirection ?


    If PQ_arr is of type struct pq_element **, then that code works
    unaltered. Now, I think you have a typo because s is undeclared, but
    I think you meant PQ_arr[n] rather than s[n].

    You are right about the *** simply because a swap function that sawp T
    objects must be passed two T* arguments, but you don't have to do it
    that way of it bothers you:

    void PQ_swap_elements(struct pq_element **arr, size_t i, size_t j)
    {
    struct pq_element *tmp = arr;
    arr = arr[j];
    arr[j] = tmp;
    }

    would also work.

    As I suggested in comp.programming, since you need other information
    to represent a queue, you should pack it all up in a struct
    (preferably using the opaque type trick). This will include the
    current capacity and current size. It might also include the
    comparison function.

    --
    Ben.
     
    Ben Bacarisse, Nov 7, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. CoolPint
    Replies:
    0
    Views:
    292
    CoolPint
    Dec 18, 2003
  2. Michal Slocinski

    Heap dump file size vs heap size

    Michal Slocinski, Mar 25, 2008, in forum: Java
    Replies:
    1
    Views:
    741
    GArlington
    Mar 25, 2008
  3. viki
    Replies:
    6
    Views:
    568
    Erik Wikström
    Jun 28, 2008
  4. arnuld

    A C implementation of Binary Heap

    arnuld, Oct 9, 2009, in forum: C Programming
    Replies:
    55
    Views:
    5,300
    arnuld
    Oct 21, 2009
  5. Raymond Schanks
    Replies:
    0
    Views:
    543
    Raymond Schanks
    Apr 11, 2010
Loading...

Share This Page