The heap Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The heap Reference Manual

This is the heap Reference Manual, version 1.0, generated automatically by Declt version 2.4 patchlevel 1 "Will Decker" on Fri May 24 08:59:48 2019 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

Binary Heap for Common Lisp

Simple implementation of a binary heap for Common Lisp. Very useful for priority queues, etc.

Quickstart

To create a new heap, use the make-heap function.

(make-heap test &key key initial-contents)

All heaps require a test function that is used much in the same way a sort function is used. It compares two elements in the heap to determine which should be closer to the top of the heap.

For example...

CL-USER > (make-heap #'> :initial-contents '(1 2 3))
#<HEAP 3 items>

CL-USER > (heap-pop *)
3

CL-USER > (make-heap #'< :initial-contents '(1 2 3))
#<HEAP 3 items>

CL-USER > (heap-pop *)
1

If you are storing objects in your heap, the key can be used to in the same way find and other Common Lisp functions use the key to extract the pertinent information from each element.

CL-USER > (make-heap #'> :key #'car :initial-contents '((1 a) (2 b)))
#<HEAP 2 items>

CL-USER > (heap-pop *)
(2 B)

The initial-contents can be any sequence.

Once you have a heap, you can add items to it with heap-push and remove items from it with heap-pop.

CL-USER > (setf h (make-heap #'>))
#<HEAP 0 items>

CL-USER > (heap-push 10 h)
#<HEAP 1 items>

CL-USER > (heap-pop h)
10

NOTE: Be sure and only push items into the heap that can abide by the key and test functions used when creating the heap.

Popping items from an empty heap returns NIL.

CL-USER > (heap-pop (make-heap #'<))
NIL

You can look at the top item in the heap (without popping it) with heap-peek.

CL-USER > (heap-peek (make-heap #'> :initial-contents '(1 2 3)))
3

Removing all elements from the heap can be done with with heap-flush.

CL-USER > (heap-flush (make-heap #'< :initial-contents '(1 2 3)))
NIL

Finally, you can get a copy of all the items in the heap with heap-contents. This will return a simple-vector.

CL-USER > (heap-contents (make-heap #'> :initial-contents '(1 2 3)))
#(3 1 2)

Note: The items returned may not be in any discernable order!


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 heap

Author

Jeffrey Massung

License

Apache 2.0

Description

Binary Heap for Common Lisp.

Version

1.0

Source

heap.asd (file)

Component

heap.lisp (file)


Next: , Previous: , Up: Top   [Contents][Index]

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 heap.asd

Location

heap.asd

Systems

heap (system)

Packages

heap-asd


Previous: , Up: Lisp files   [Contents][Index]

3.1.2 heap/heap.lisp

Parent

heap (system)

Location

heap.lisp

Packages

heap

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Next: , Previous: , Up: Packages   [Contents][Index]

4.1 heap-asd

Source

heap.asd

Use List

Previous: , Up: Packages   [Contents][Index]

4.2 heap

Source

heap.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Functions

Function: heap-contents HEAP

Return a copy of the heap items.

Package

heap

Source

heap.lisp (file)

Function: heap-flush HEAP

Remove all elements from the heap.

Package

heap

Source

heap.lisp (file)

Function: heap-peek HEAP

Return the next element to be removed from the heap.

Package

heap

Source

heap.lisp (file)

Function: heap-pop ()

Remove the root element from the heap.

Package

heap

Source

heap.lisp (file)

Function: heap-push ()

Insert a new element onto the heap.

Package

heap

Source

heap.lisp (file)

Function: make-heap TEST &key KEY INITIAL-CONTENTS

Create a heap with data in it.

Package

heap

Source

heap.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Functions

Function: %make-heap TEST &key KEY
Package

heap

Source

heap.lisp (file)

Function: copy-heap INSTANCE
Package

heap

Source

heap.lisp (file)

Function: heap-compare INSTANCE
Function: (setf heap-compare) VALUE INSTANCE
Package

heap

Source

heap.lisp (file)

Function: heap-elts INSTANCE
Function: (setf heap-elts) VALUE INSTANCE
Package

heap

Source

heap.lisp (file)

Function: heap-p OBJECT
Package

heap

Source

heap.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Structures

Structure: heap ()
Package

heap

Source

heap.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: compare
Initform

(if (null heap::key) heap::test (lambda (heap::a heap::b) (funcall heap::test (funcall heap::key heap::a) (funcall heap::key heap::b))))

Readers

heap-compare (function)

Writers

(setf heap-compare) (function)

Slot: elts
Initform

(make-array 0 :adjustable t :fill-pointer t)

Readers

heap-elts (function)

Writers

(setf heap-elts) (function)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   H   L  
Index Entry  Section

F
File, Lisp, heap.asd: The heap<dot>asd file
File, Lisp, heap/heap.lisp: The heap/heap<dot>lisp file

H
heap.asd: The heap<dot>asd file
heap/heap.lisp: The heap/heap<dot>lisp file

L
Lisp File, heap.asd: The heap<dot>asd file
Lisp File, heap/heap.lisp: The heap/heap<dot>lisp file

Jump to:   F   H   L  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   %   (  
C   F   H   M  
Index Entry  Section

%
%make-heap: Internal functions

(
(setf heap-compare): Internal functions
(setf heap-elts): Internal functions

C
copy-heap: Internal functions

F
Function, %make-heap: Internal functions
Function, (setf heap-compare): Internal functions
Function, (setf heap-elts): Internal functions
Function, copy-heap: Internal functions
Function, heap-compare: Internal functions
Function, heap-contents: Exported functions
Function, heap-elts: Internal functions
Function, heap-flush: Exported functions
Function, heap-p: Internal functions
Function, heap-peek: Exported functions
Function, heap-pop: Exported functions
Function, heap-push: Exported functions
Function, make-heap: Exported functions

H
heap-compare: Internal functions
heap-contents: Exported functions
heap-elts: Internal functions
heap-flush: Exported functions
heap-p: Internal functions
heap-peek: Exported functions
heap-pop: Exported functions
heap-push: Exported functions

M
make-heap: Exported functions

Jump to:   %   (  
C   F   H   M  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   C   E   S  
Index Entry  Section

C
compare: Internal structures

E
elts: Internal structures

S
Slot, compare: Internal structures
Slot, elts: Internal structures

Jump to:   C   E   S  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   H   P   S  
Index Entry  Section

H
heap: The heap system
heap: The heap package
heap: Internal structures
heap-asd: The heap-asd package

P
Package, heap: The heap package
Package, heap-asd: The heap-asd package

S
Structure, heap: Internal structures
System, heap: The heap system

Jump to:   H   P   S