A C implementation of Binary Heap

[arnuld]

Insert is surely Log N for an ordered array? Mind you, I am not sure
what is being measured here, so who knows. Maybe data moves are being
measured and some technique is used to reduce moves on delete. I don't
know.

If by Ordered array he means that, all elements are inserted with
ascending or descending order of priority, then of course it will take N,
because you have to do N comparisons to find the proper place to insert.

It does. I don't see a problem. I'd use an array-based heap with a
clean interface so I could change it later if the large block
allocations became a problem (I am told they can be in embedded
systems). In fact, I'd probably use a sorted linked list or an ordered
array to prototype the code and plug in a heap later if inserts were
getting too slow. I am very fond of rapid prototyping.

I am writing a queue implementation of doubly linked list where elements
are added in descending order of priority. That way delete max will
always be 1 but insertion will be N in worst case.

or you think I should use a general queue, adding anywhere and then
insert will be 1 but delete max will be N ?

 

[arnuld]

It does. I don't see a problem. I'd use an array-based heap with a
clean interface so I could change it later if the large block
allocations became a problem (I am told they can be in embedded
systems).

I don't think my seniors is going to agree with using an array with
1000 of heap data structures as elements, no not even 200.

 

[Ben Bacarisse]

If by Ordered array he means that, all elements are inserted with
ascending or descending order of priority, then of course it will take N,
because you have to do N comparisons to find the proper place to
insert.

Binary search takes log N comparisons to find the insertion point.
The table may be summarising a particular, less the optimal,
implementation, of course.

I am writing a queue implementation of doubly linked list where elements
are added in descending order of priority. That way delete max will
always be 1 but insertion will be N in worst case.

Why waste the space with a double link? Do you have space to spare?

or you think I should use a general queue, adding anywhere and then
insert will be 1 but delete max will be N ?

It depends on the application. In many real-world cases, insert and
delete-max operations occur with roughly equal frequency so the
overall cost that matters is that of insert+delete-max.

If you can tolerate O(n) for this combined cost then an ordered list
will be fine. This n in is the length of the queue, of course. Do
you know the expected value of n over time?

 

[arnuld]

Why waste the space with a double link? Do you have space to spare?

no.

It depends on the application. In many real-world cases, insert and
delete-max operations occur with roughly equal frequency so the overall
cost that matters is that of insert+delete-max.

If you can tolerate O(n) for this combined cost then an ordered list
will be fine. This n in is the length of the queue, of course. Do you
know the expected value of n over time?

Not much, except that if I got a million elements and 1 million more were
added after 30 minutes then half of total will be deleted at the same
time. Except that no idea.

 

[Giorgos Keramidas]

If by Ordered array he means that, all elements are inserted with
ascending or descending order of priority, then of course it will take
N, because you have to do N comparisons to find the proper place to
insert.

Unless one uses smarter ways of searching an array that is known to be
sorted by virtue of its construction method, i.e. binary search for the
appropriate location. Then finding the "right" spot for the insert
operation is indeed log2(k), where 'k' is the current array size.

 

[Ben Pfaff]

These are the main points I am focusing on:

1) Millions of elements to process, with no idea of how many to begin
with.
2) Insertion with priority
3) delete with max priority
4) find the element with max priority
5) only 1 priority queue. No joining of different queues. (that is where
I rejected the possibility of using a Binomial Queue)

There are papers that compare the performance of priority queue
implementations. Have you read them?

 

[Keith Thompson]

Insert is surely Log N for an ordered array? Mind you, I am not sure
what is being measured here, so who knows. Maybe data moves are being
measured and some technique is used to reduce moves on delete. I
don't know.

[...]

Finding out where to do the insertion can be done by a binary search,
and is O(log N). Actually doing the insertion requires, on average,
shifting half the existing elements, which is O(N).

But I do question the 1 for "Delete". Deleting an arbitrary element
is O(N). The table, as arnuld posted it, has the same values for
"Del Max" and "Delete" for all 5 methods. arnuld, are you sure
you transcribed it correctly?

 

[user923005]

Insert is surely Log N for an ordered array?  Mind you, I am not sure
what is being measured here, so who knows.  Maybe data moves are being
measured and some technique is used to reduce moves on delete.  I
don't know.

[...]

Finding out where to do the insertion can be done by a binary search,
and is O(log N).  Actually doing the insertion requires, on average,
shifting half the existing elements, which is O(N).

But I do question the 1 for "Delete".  Deleting an arbitrary element
is O(N).  The table, as arnuld posted it, has the same values for
"Del Max" and "Delete" for all 5 methods.  arnuld, are you sure
you transcribed it correctly?

He did not, I have it here in front of me (3rd edition, page 367).

Ordered Array: Insert=N, DeleteMax=1, Delete=N, FindMax=1,
ChangePriority=N, Join=N

For Binomial queue, all operations are log(N)

Optimal: Insert=1, DeleteMax=log(N), Delete=log(N), FindMax=1,
ChangePriority=1, Join=1

 

[Phil Carmody]

An array of structures ?

Or an array of pointers.

Will it be as efficient as a double linked list ?

As efficient at doing _what_? You really need to learn to ask
meaningful questions, or you'll never learn anything.

2nd I don't know the number of elements in advance,

But you do after you've build a binary search tree. Which is
what you're claiming you want to do before you create the heap.

so using array is
out of question. I can use 1000 elements array in the beginning but
then I have to realloc (if I need) 100 more elements. I don't think
its will be as efficient as building a dynamic binary search tree.

Put the elements into the tree in order - what shape does your
tree have? How many comparisons were performed? Compare that to a
heap.

Phil

 

[Phil Carmody]

I doubt that Sedgewick says this but I don't have the book to check.
Wikipedia does not say this unless I've missed it.

You have confused "binary tree" with "binary search tree". Adding to
a BST is O(log n)

No it's not. That's why one self-balances, as if you don't you can
end up with a linked list and Theta(n).

Phil

 

[Phil Carmody]

These are the main points I am focusing on:

1) Millions of elements to process, with no idea of how many to begin
with.
2) Insertion with priority
3) delete with max priority
4) find the element with max priority
5) only 1 priority queue. No joining of different queues. (that is where
I rejected the possibility of using a Binomial Queue)


2nd it has to run on some embedded platform where 64 MB of RAM will be
available definitely, more can be available too. I will use arrays of
pointers to structures if you tell me they will be good for me. I am not
as experienced as you are.

Sedgewick used the arrays to demonstrate binary heap in his book and at
the same time in section 9.1 he has this table:

Insert Del Max Find Max Delete
Ordered array: N 1 1 1

Well, that's wrong. Delete is O(N).

Unordered array: 1 N N N
Ordered list: N 1 1 1

That's wrong too, delete again is O(N), as it requires finding the element.

Unordered list: 1 N N N

And if the finding of the element isn't part of the delete, then that's
wrong for the opposite reason.

heap: LogN LogN 1 LogN

So I thought with the requirements I mentioned Heap fits good.

Given your 5 points above, heap is perfect. Due to the perference
for contiguous memory in implementing heaps, a heap of pointers probably
makes most sense, which can be realloc()ed as needed.

Phil

 

[Ben Bacarisse]

No it's not. That's why one self-balances, as if you don't you can
end up with a linked list and Theta(n).

Quite right. I should have said O(log n) "at beast" (when the insert
is a re-balancing insert). However, the reason this distinction does
not matter is that even the best implementation of a BST is not good
enough for his argument. He has seen the argument that, when
inserting a bunch of item into a heap, it is more efficient to insert
them all and the "heapify" the tree; but this is true only when insert
is O(1). The advantage of the usual array implementation is that
insert if O(1) and it maintains the shape part of the heap property
for free.

 

[arnuld]

There are papers that compare the performance of priority queue
implementations. Have you read them?

If I Google for "priority queue I get 62,800 hits. Same way, if you
search for C programming notes you get 2,380,000 hits, first one being C-
FAQ home page of Steve Summit. Now how can I trust all those notes:
Answer is I do *not*.

My colleagues and friends learn both C from these Google searches and
they hate CLC, I learn from CLC, CLC is the only place I trust, if I get
a link or recommendations from my friends I search the archives of CLC
and see what are the reviews. Everyone knows here that what kind of
teaching is done in those online materials.

I am not a master of either C or Algorithms, so I can not select which
articles to read and which ones not to. Some regular poster do post some
links and I do read them most of the time.

 

[arnuld]

Quite right. I should have said O(log n) "at beast" (when the insert is
a re-balancing insert). However, the reason this distinction does not
matter is that even the best implementation of a BST is not good enough
for his argument. He has seen the argument that, when inserting a bunch
of item into a heap, it is more efficient to insert them all and the
"heapify" the tree; but this is true only when insert is O(1). The
advantage of the usual array implementation is that insert if O(1) and
it maintains the shape part of the heap property for free.

Okay, since you have emphasized an array implementation, I will give it a
try. Actually, I had felt a lot of difficulty understanding a heap built
into an array, where first element is the root and 2nd and 3rd elements
of the array are its children and then 4th and 5th elements are the
children of left child of the root (Sedgewick section 9.2, page 369). For
me, an array is just a collection of elements. I will try to understand
how to build a Binary Heap into a array.

 

[Ben Pfaff]

If I Google for "priority queue I get 62,800 hits. Same way, if you
search for C programming notes you get 2,380,000 hits, first one being C-
FAQ home page of Steve Summit. Now how can I trust all those notes:
Answer is I do *not*.

Here's one paper that looks worthwhile:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8515

I've seen others, too.

 

[arnuld]

If you trust CLC, and CLC trusts Steve Summit's FAQ, it is not
unreasonable for you to trust Steve Summit's FAQ.

Oh.. holy cow.... that is not what I meant, I should have been more
clear. Here is the complete sentence:


Same way, if you search for C programming notes you get 2,380,000 hits,
first one being C- FAQ home page of Steve Summit, which is the only place
I think has "right things about C". Now how can I trust all that other
material: Answer is I do *not*.


C FAQs are the primary place I refer to my friends whenever they have a
question and its already answered in FAQs e.g. Arrays and Pointers are
same, why not cast malloc() etc. Its a different case they don't read it
and if they do, 50% of the times they are not satisfied. Like last month
when I referred my friend to not to cast to malloc() and read FAQ and
firts reaction after reading was "I will never forget including stdlib.h,
who forgets including stdlib.h"