Array based Binary Heap in C

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

On Oct 30, 12:24*am, arnuld <sunr...@invalid.address> 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

> 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

> 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

On Nov 1, 10:37*pm, arnuld <sunr...@invalid.address> 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

> 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

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) kst- <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

> 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

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[i] and you refer to the address of this value as &p[i].

--
Remove del for email

Barry Schwarz

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[i];
arr[i] = 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