Did you know ... | Search Documentation: |

library(heaps): heaps/priority queues |

- Documentation
- Reference manual
- The SWI-Prolog library
- library(aggregate): Aggregation operators on backtrackable predicates
- library(ansi_term): Print decorated text to ANSI consoles
- library(apply): Apply predicates on a list
- library(assoc): Association lists
- library(broadcast): Broadcast and receive event notifications
- library(charsio): I/O on Lists of Character Codes
- library(check): Consistency checking
- library(clpb): CLP(B): Constraint Logic Programming over Boolean Variables
- library(clpfd): CLP(FD): Constraint Logic Programming over Finite Domains
- library(clpqr): Constraint Logic Programming over Rationals and Reals
- library(csv): Process CSV (Comma-Separated Values) data
- library(dcg/basics): Various general DCG utilities
- library(dcg/high_order): High order grammar operations
- library(debug): Print debug messages and test assertions
- library(dicts): Dict utilities
- library(error): Error generating support
- library(fastrw): Fast reading and writing of terms
- library(gensym): Generate unique symbols
- library(heaps): heaps/priority queues
- library(increval): Incremental dynamic predicate modification
- library(intercept): Intercept and signal interface
- library(iostream): Utilities to deal with streams
- library(listing): List programs and pretty print clauses
- library(lists): List Manipulation
- library(main): Provide entry point for scripts
- library(nb_set): Non-backtrackable set
- library(www_browser): Open a URL in the users browser
- library(occurs): Finding and counting sub-terms
- library(option): Option list processing
- library(optparse): command line parsing
- library(ordsets): Ordered set manipulation
- library(pairs): Operations on key-value lists
- library(persistency): Provide persistent dynamic predicates
- library(pio): Pure I/O
- library(portray_text): Portray text
- library(predicate_options): Declare option-processing of predicates
- library(prolog_debug): User level debugging tools
- library(prolog_jiti): Just In Time Indexing (JITI) utilities
- library(prolog_trace): Print access to predicates
- library(prolog_pack): A package manager for Prolog
- library(prolog_xref): Prolog cross-referencer data collection
- library(quasi_quotations): Define Quasi Quotation syntax
- library(random): Random numbers
- library(rbtrees): Red black trees
- library(readutil): Read utilities
- library(record): Access named fields in a term
- library(registry): Manipulating the Windows registry
- library(settings): Setting management
- library(statistics): Get information about resource usage
- library(strings): String utilities
- library(simplex): Solve linear programming problems
- library(solution_sequences): Modify solution sequences
- library(tables): XSB interface to tables
- library(terms): Term manipulation
- library(thread): High level thread primitives
- library(thread_pool): Resource bounded thread management
- library(ugraphs): Graph manipulation library
- library(url): Analysing and constructing URL
- library(varnumbers): Utilities for numbered terms
- library(yall): Lambda expressions

- The SWI-Prolog library
- Packages

- Reference manual

- author
- Lars Buitinck

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. These support insertion and merging both in constant time, deletion of the minimum in logarithmic amortized time (though delete-min, i.e., get_from_heap/3, takes linear time in the worst case).

- [semidet]
**add_to_heap**(`+Heap0, +Priority, ?Key, -Heap`) - Adds
`Key`with priority`Priority`to`Heap0`, constructing a new heap in`Heap`. - [semidet]
**delete_from_heap**(`+Heap0, -Priority, +Key, -Heap`) - Deletes
`Key`from`Heap0`, leaving its priority in`Priority`and the resulting data structure in`Heap`. Fails if`Key`is not found in`Heap0`.- bug
- This predicate is extremely inefficient and exists only for SICStus compatibility.

- [semidet]
**empty_heap**(`?Heap`) - True if
`Heap`is an empty heap. Complexity: constant. - [semidet]
**singleton_heap**(`?Heap, ?Priority, ?Key`) - True if
`Heap`is a heap with the single element`Priority`-`Key`.Complexity: constant.

- [semidet]
**get_from_heap**(`?Heap0, ?Priority, ?Key, -Heap`) - Retrieves the minimum-priority pair
`Priority`-`Key`from`Heap0`.`Heap`is`Heap0`with that pair removed. Complexity: logarithmic (amortized), linear in the worst case. - [det]
**heap_size**(`+Heap, -Size:int`) - Determines the number of elements in
`Heap`. Complexity: constant. - [det]
**heap_to_list**(`+Heap, -List:list`) - Constructs a list
`List`of Priority-Element terms, ordered by (ascending) priority. Complexity: $O(n`\`

log n)$. - [semidet]
**is_heap**(`+X`) - Returns true if
`X`is a heap. Validates the consistency of the entire heap. Complexity: linear. - [det]
**list_to_heap**(`+List:list, -Heap`) - If
`List`is a list of Priority-Element terms, constructs a heap out of`List`. Complexity: linear. - [semidet]
**min_of_heap**(`+Heap, ?Priority, ?Key`) - Unifies
`Key`with the minimum-priority element of`Heap`and`Priority`with its priority value. Complexity: constant. - [semidet]
**min_of_heap**(`+Heap, ?Priority1, ?Key1, ?Priority2, ?Key2`) - Gets the two minimum-priority elements from
`Heap`. Complexity: logarithmic (amortized).Do not use this predicate; it exists for compatibility with earlier implementations of this library and the SICStus counterpart. It performs a linear amount of work in the worst case that a following get_from_heap has to re-do.

- [det]
**merge_heaps**(`+Heap0, +Heap1, -Heap`) - Merge the two heaps
`Heap0`and`Heap1`in`Heap`. Complexity: constant.

Tags are associated to your profile if you are logged in

Tags: