Did you know? Your proprietary application can use SWI-PrologSearch Documentation:

Heaps are data structures that return the entries inserted into them in an ordered fashion, based on a priority. This makes them the data structure of choice for implementing priority queues, a central element of algorithms such as best-first/A* search and Kruskal's minimum-spanning-tree algorithm.

This module implements min-heaps, meaning that items are retrieved in ascending order of key/priority. It was designed to be compatible with the SICStus Prolog library module of the same name. merge_heaps/3 and singleton_heap/3 are SWI-specific extension. The portray_heap/1 predicate is not implemented.

Although the data items can be arbitrary Prolog data, keys/priorities must be ordered by @=</2. Be careful when using variables as keys, since binding them in between heap operations may change the ordering.

The current version implements pairing heaps. All operations can be performed in at most O(lg n) amortized time, except for delete_from_heap/4, heap_to_list/2, is_heap/1 and list_to_heap/2.

(The actual time complexity of pairing heaps is complicated and not yet determined conclusively; see, e.g. S. Pettie (2005), Towards a final analysis of pairing heaps, Proc. FOCS'05.)

**add_to_heap**`(+Heap0, +Priority, ?Key, -Heap)`is**semidet**- Adds
`Key`with priority`Priority`to`Heap0`, constructing a new heap in`Heap`. **delete_from_heap**`(+Heap0, -Priority, +Key, -Heap)`is**semidet**- Deletes
`Key`from`Heap0`, leaving its priority in`Priority`and the resulting data structure in`Heap`. Fails if`Key`is not found in`Heap0`. **empty_heap**`(?Heap)`is**semidet**- True if
`Heap`is an empty heap. **singleton_heap**`(?Heap, ?Priority, ?Key)`is**semidet**- True if
`Heap`is a heap with the single element`Priority`-`Key`. **get_from_heap**`(?Heap0, ?Priority, ?Key, -Heap)`is**semidet**- Retrieves the minimum-priority pair
`Priority`-`Key`from`Heap0`.`Heap`is`Heap0`with that pair removed. **heap_size**`(+Heap, -Size:int)`is**det**- Determines the number of elements in
`Heap`. **heap_to_list**`(+Heap, -List:list)`is**det**- Constructs a list
`List`of Priority-Element terms, ordered by (ascending) priority. **is_heap**`(+X)`is**semidet**- Returns true if
`X`is a heap. Validates the consistency of the entire heap. **list_to_heap**`(+List:list, -Heap)`is**det**- If
`List`is a list of Priority-Element terms, constructs a heap out of`List`. **min_of_heap**`(+Heap, ?Priority, ?Key)`is**semidet**- Unifies
`Key`with the minimum-priority element of`Heap`and`Priority`with its priority value. **min_of_heap**`(+Heap, ?Priority1, ?Key1, ?Priority2, ?Key2)`is**semidet**- Gets the two minimum-priority elements from
`Heap`. **merge_heaps**`(+Heap0, +Heap1, -Heap)`is**det**- Merge the two heaps
`Heap0`and`Heap1`in`Heap`.