Module jumper.core.bheap
A light implementation of binary heaps.
While running a search, some algorithms have to maintains a list of nodes called open list. Finding in this list the lowest cost node from the node being processed can be quite slow, (as it requires to skim through the collection of nodes stored in this list) especially when dozens of nodes are being processed (large maps).
The current module implements a binary heap data structure, from which the internal open list will be instantiated. As such, looking up for lower-cost node will run faster, and globally makes the search algorithm run faster.
This module should normally not be used explicitely. The algorithm uses it internally.
Info:
- Copyright: 2012-2013
- License: MIT
- Author: Roland Yonaba
Functions
| heap:empty () | Checks if a heap is empty |
| heap:clear () | Clears the heap (removes all items queued in the heap) |
| heap:push (item) | Adds a new item in the heap |
| heap:pop () | Pops from the heap . |
| heap:heapify ([item]) | Restores the heap property. |
Tables
| heap | The heap class |
Functions
- heap:empty ()
-
Checks if a heap is empty
Returns:
-
bool
trueof no item is queued in the heap,falseotherwise - heap:clear ()
- Clears the heap (removes all items queued in the heap)
- heap:push (item)
-
Adds a new item in the heap
Parameters:
- item object a new object to be queued in the heap
- heap:pop ()
-
Pops from the heap .
Removes and returns the lowest cost item (with respect to the comparison function used) from the heap .
Returns:
-
object
an object stored in the heap
- heap:heapify ([item])
-
Restores the heap property.
Reorders the heap with respect to the comparison function being used.
When given arg
item, will sort that very item in the heap . Otherwise, the whole heap will be sorted.Parameters:
- item object the modified object
Tables
- heap
- The heap class