The heap Module

Overview

A heap is an implementation of the abstract data type “sorted list”. A heap is a sorted sequence of items. Most likely the user will end up writing something like

define class <heap-item> (<object>)
  slot priority;
  slot data;
end;

with appropriate methods defined for < and =. The user could, however, have simply a sorted list of integers, or have some item where the priority is an integral part of the item itself.

make on heaps supports the less-than: keyword, which supply the heap’s comparison and defaults to <.

Heaps support all the usual sequence operations. The most useful ones:

heap-push(heap, item) => updated-heap
heap-pop(heap)        => smallest-element
first(heap)           => smallest-element
second(heap)          => second-smallest-element
add!(heap, item)      => updated-heap
sort, sort!           => sorted-sequence

These are all “efficient” operations (defined below). As with push on <deque>, heap-push is another name for add!, and does exactly the same thing except that heap-push doesn’t accept any keywords. sort and sort! return a sequence that’s not a heap. Not necessarily efficient but useful anyhow:

add-new!(heap, item, #key test:, efficient:) => updated-heap
remove!(heap, item, #key test:, efficient:) => updated-heap
member?(item, heap, #key test:, efficient:) => <boolean>

The efficient: keyword defaults to #f. If #t, it uses the random-iteration-protocol (which is considerably more efficient, but isn’t really standard behavior, so it had to be optional). Conceivably most sequence methods could support such a keyword, but they don’t yet.

The user can use element-setter or the iteration protocol to change an item in the heap, but changing the priority of an item is an error and Bad Things(tm) will happen. No error will be signaled. Both of these operations are very inefficient.

Heaps are not instances of <stretchy-collection>, although add! and heap-pop can magically change the size of the heap.

Efficiency: Approximate running times of different operations are given below: (N is the size of the heap)

first, first-setter                             O(1)
second (but not second-setter)                  O(1)
size                                            O(1)
add!                                            O(lg N)
heap-push                                       O(lg N)
heap-pop(heap)                                  O(lg N)
sort, sort!                                     O(N * lg N)
forward-iteration-protocol
                        setup:                  O(N)
                        next-state:             O(lg N)
                        current-element:        O(1)
                        current-element-setter: O(N)
backward-iteration-protocol
                        setup:                  O(N * lg N)
                        next-state:             O(1)
                        current-element:        O(1)
                        current-element-setter: O(N)
random-iteration-protocol
                        setup:                  O(1)
                        next-state:             O(1)
                        current-element:        O(1)
                        current-element-setter: O(1)
element(heap, M)                                O(M*lg N + N)
element-setter(value, heap, M)                  O(N + M*lg N + M)

element, element-setter on arbitrary keys use the forward-iteration-protocol (via the inherited methods), and have accordingly bad performance.

Reference

The HEAP module

<heap> Class
Superclasses:

<mutable-sequence>

Init-Keywords:
heap-pop Generic function
Signature:

heap-pop (h) => (smallest-item)

Parameters:

  • h – An instance of <heap>.

Values:

  • smallest-item – An instance of <object>.

heap-push Generic function
Signature:

heap-push (h new-elt) => (changed-heap)

Parameters:
Values:

  • changed-heap – An instance of <heap>.

random-iteration-protocol Generic function
Signature:

random-iteration-protocol (collection) => (initial-state limit next-state finished-state? current-key current-element current-element-setter copy-state)

Parameters:

  • collection – An instance of <heap>.

Values: