jbmilgrom jbmilgrom - 11 months ago 58
C Question

Why does efficient heap construction require random access?

Since you can efficiently construct a heap by sequentially iterating through an array:

make_heap(priority_queue *q, item_type s[], int n)
int i; /* counter */

for (i=0; i<n; i++)
priority_q_insert(q, s[i]);

Part of the priority_q implementation (in case helpful):

priority_q_insert(priority_queue *q, item_type x)
if (q->n >= PQ_SIZE)
else {
q->n = (q->n) + 1;
q->q[ q->n ] = x;
bubble_up(q, q->);

Why can't you efficiently construct a heap by sequentially iterating through a linked-list (which it appears you can do)?

pts pts
Answer Source

Values of a heap are stored in a read-write indexable array. For example, bubble_up needs to be able to read and write values in nonsequential order. See Muhammad Ahmad's answer for a more specific example how the heap does nonsequential access.

Thus it's not possible to store and maintain values of a heap in a linked list (or doubly-linked list), because that supports only sequential access. (More specifically: nonsequential access in a linked list is possible, but it's usually too slow. Thus the building and using a heap based on a linked list would be too slow.)

It's possible to convert a linked list to a heap, by starting from an empty heap, iterating over the linked list, and inserting each element in the linked list to the heap. In the end there will be two copies of the values: one in the linked list and one in the heap. The linked list can be deleted then. It's also possible to remove each value during the iteration.

It's not possible to convert a linked list to a heap in place (without copying values or without making it too slow), because the heap needs nonsequential access, and the linked list provides only sequential access efficiently.