Re: heap.el -- new release

[Stefan Monnier]

Your code has some problem w.r.t efficiency.  The heap data-structure is
interesting for its complexity properties (e.g. heap-delete-root should be
O(log N)), but your code doesn't enjoy those properties:

> (defun heap-add (heap data)
>   "Add DATA to the heap."
>   ;; Add data to bottom of heap and sift-up from bottom.
>   (heap--set-vect heap (vconcat (heap--vect heap) (vector data)))
>   (heap--sift-up heap (1- (length (heap--vect heap))))
> )

This is O(N) (because vconcat is O(N)).

> (defun heap-delete-root (heap)
>   "Return the root of the heap and delete it from the heap."
>   (let ((vect (heap--vect heap))
>       (root nil) (len nil))
    
>     ;; Deal with special cases of empty heap and heap with just one element.
>     (if (heap-empty heap) nil
>       (setq len (length vect))
>       (setq root (aref vect 0))
>       (if (= 1 len) (heap--set-vect heap [])
>       ;; Delete root, swap last element to top, and sift-down from top.
>       (heap--set-vect heap (vconcat (vector (aref vect (1- len)))
>                                  (heap--subvect vect 1 (1- len))))
>       (heap--sift-down heap 0))
>       root)
>   )
> )

This is O(N) as well.
I.e. you shouldn't resize your array all the time.  You should allow it to
be larger than the number of elements it holds, and only resize it every
once in a while (by reducing/increasing its size by a constant factor).


        Stefan