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
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 2As 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