nuget
Heaps
01 Syntax
02 Methods
| Name | Overloads | Summary |
|---|---|---|
| MakeHeap | 1 | Constructor for the heap objects. |
| MakeArrays | 1 | allocate a nPoints-by-size matrix and then fill it with the given fillValue |
| HeapPush | 1 | Push a new element onto the heap. |
| UncheckedHeapPush | 1 | Push a new element onto the heap. |
| HeapPushPair | 1 | Push the symmetric neighbours pair (rowA -> rowB) and (rowB -> rowA) onto the heap in a thread safe manner. |
| BuildCandidates | 1 | Build a heap of candidate neighbors for nearest neighbor descent. |
| DeHeapSort | 1 | Given an array of heaps (of indices and weights), unpack the heap out to give and array of sorted lists of indices and weights by increasing weight. |
| SortHeapRow | 1 | unpack one heap row out to a sorted list of indices by increasing weight (the second half of the heap sort) |
| ToIntMatrix | 1 | convert the indices matrix of the heap from double to integer |
| SiftDown | 1 | Restore the heap property for a heap with an out of place element at position elt. |
| SmallestFlagged | 1 | Search the heap for the smallest element that is still flagged |
03 Members
Int32, Int32)Constructor for the heap objects. The heaps are used for approximate nearest neighbor search, maintaining a list of potential neighbors sorted by their distance.We also flag if potential neighbors are newly added to the list or not.Internally this is stored as a single array; the first axis determines whether we are looking at the array of candidate indices, the array of distances, or the flag array for whether elements are new or not.Each of these arrays are of shape (nPoints, size)
Double, Int32, Int32)allocate a nPoints-by-size matrix and then fill it with the given fillValue
Heap, Int32, Double, Int32, Int32)Push a new element onto the heap. The heap stores potential neighbors for each data point.The row parameter determines which data point we are addressing, the weight determines the distance (for heap sorting), the index is the element to add, and the flag determines whether this is to be considered a new addition.
Heap, Int32, Double, Int32, Int32)Push a new element onto the heap. The heap stores potential neighbors for each data point. The row parameter determines which data point we are addressing, the weight determines the distance (for heap sorting), the index is the element to add, and the flag determines whether this is to be considered a new addition.
Heap, Object(), Int32, Int32, Double, Int32)Push the symmetric neighbours pair (rowA -> rowB) and (rowB -> rowA) onto the heap in a thread safe manner.
the two lock objects are always acquired in the ascending order of the stripe index, so that the dead lock is impossible.
| Name | Type | Description |
|---|---|---|
heap | Heap | - |
locks | Object() | a striped lock array which is created via the Utils.NewStripedLocks() function. |
rowA | Int32 | - |
rowB | Int32 | - |
weight | Double | - |
flag | Int32 | - |
the number of the elements that have been pushed onto the heap: 0, 1 or 2.
Build a heap of candidate neighbors for nearest neighbor descent. For each vertex the candidate neighbors are any current neighbors, and any vertices that have the vertex as one of their nearest neighbors.
| Name | Type | Description |
|---|---|---|
parallelism | Heap | the parallelism configuration, the candidate heap will be built in parallel when the size of the graph is large enough. |
Heap, ParallelConfig)Given an array of heaps (of indices and weights), unpack the heap out to give and array of sorted lists of indices and weights by increasing weight. This is effectively just the second half of heap sort (the first half not being required since we already have the data in a heap).
| Name | Type | Description |
|---|---|---|
parallelism | Heap | the parallelism configuration. Each row of the heap is sorted independently, so this procedure could be done in parallel without any lock. |
Double(), Double())unpack one heap row out to a sorted list of indices by increasing weight (the second half of the heap sort)
this procedure only touches the two given rows, so that it is safe for run it in parallel for each row of the heap.
| Name | Type | Description |
|---|---|---|
indHeap | Double() | the row of the neighbour indices, this row will be modified in place. |
distHeap | Double() | the row of the neighbour distances, this row will be modified in place. |
Double()(), ParallelConfig)convert the indices matrix of the heap from double to integer
Double(), Double(), Int32, Int32)Restore the heap property for a heap with an out of place element at position elt. This works with a heap pair where heap1 carries the weights and heap2 holds the corresponding elements.
Heap, Int32)Search the heap for the smallest element that is still flagged