Heap - lexorder

Hi,

I need to construct a heap using a list.

Have found this in Maple help.

> h := (heap[new])(lexorder, greg, tony, bruno, michael); (heap[insert])(stefan, h);
stefan
> (heap[size])(h);
5
> (heap[max])(h);
tony
> while `not`((heap[empty])(h)) do (heap[extract])(h) end do;
tony
stefan
michael
greg
bruno

What would be a command similar to 'lexorder' that will enable to arrange numbers in a heap?

Also, how would I deconstruct a heap into a list? Is there a command in Maple that would allow to see the worst case scenario (a maximum number of comparison between the elements of the heap) and the best case scenario (a minimum number of comparisons).

Thanks in advance! Antonio

acer's picture

size

You could arrange numbers in a heap according to size.

> h := heap[new](`<`, 4, 7, 19, 111, 2):

> heap[insert](17, h):

> while not heap[empty](h) do heap[extract](h); end do;
                                      111

                                      19

                                      17

                                       7

                                       4

                                       2

As for extracting them to a list, I presume that you want the list sorted (by the same boolean-valued function used by the heap). Note that, for a heap h stored in a table according to the scheme above, the element h[0] is the number of stored values while the element h[`<`] is the boolean valued function which compares/sorts them.

> h := heap[new](`>`, 4, 7, 19, 111, 2):
> sort([seq(h[i],i=1..h[0])],h[`<`]);
                              [111, 19, 7, 4, 2]

> h := (heap[new])(lexorder, greg, tony, bruno, michael):
> sort([seq(h[i],i=1..h[0])],h[`<`]);
                         [bruno, greg, michael, tony]

See here for some nice notes on efficient sorting of lists.

note: This stuff above involves heaps implemented as Maple tables. You also wrote that you wanted to implement a heap as a list. Do you really want to do that, as well, even though Maple lists are not efficient mutable data structures?

acer

Thanks a lot! The upper

Thanks a lot!

The upper bound (maximum number of comparisons) is in O(n*ln(n)) and the lower bound (minimum number of comparisons) is in omega(n*ln(n)). Just wondered if there is a step-by-step procedure for different levels of algorithm efficiency for n number of elements in a heap.

In other words, if, say, we have 12 elements in a heap: how it would be possible to re-arrange the heap into a list showing the max and min number of comparisons. I could do it manually, but for large n, it is perhaps best to use Maple (if such procedure exists).

Many thanks in advance. Antonio

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
}