Next: , Previous: , Up: Data Structures   [Contents][Index]

7.1.17 Priority Queues

(require 'priority-queue)

This algorithm for priority queues is due to Introduction to Algorithms by T. Cormen, C. Leiserson, R. Rivest. 1989 MIT Press.

Function: make-heap pred<?

Returns a binary heap suitable which can be used for priority queue operations.

Function: heap-length heap

Returns the number of elements in heap.

Procedure: heap-insert! heap item

Inserts item into heap. item can be inserted multiple times. The value returned is unspecified.

Procedure: heap-extract-max! heap

Returns the item which is larger than all others according to the pred<? argument to make-heap. If there are no items in heap, an error is signaled.