Lely core libraries 2.3.4
|
This header file is part of the utilities library; it contains the pairing heap declarations. More...
Go to the source code of this file.
Data Structures | |
struct | pnode |
A node in a pairing heap. More... | |
struct | pheap |
A pairing heap. More... | |
Macros | |
#define | PNODE_INIT |
The static initializer for pnode. | |
#define | PHEAP_INIT |
The static initializer for pheap. | |
#define | pnode_foreach(first, node) pnode_foreach_(__LINE__, first, node) |
Iterates over each node in a pairing heap in unspecified order. More... | |
#define | pheap_foreach(heap, node) pnode_foreach (pheap_first(heap), node) |
Iterates over each node in a pairing heap in unspecified order. More... | |
Typedefs | |
typedef int | pheap_cmp_t(const void *p1, const void *p2) |
The type of a comparison function suitable for use in a paring heap. More... | |
Functions | |
void | pnode_init (struct pnode *node, const void *key) |
Initializes a node in a paring heap. More... | |
struct pnode * | pnode_next (const struct pnode *node) |
Returns a pointer to the next node (in unspecified order) in a pairing heap. | |
void | pheap_init (struct pheap *heap, pheap_cmp_t *cmp) |
Initializes a pairing heap. More... | |
int | pheap_empty (const struct pheap *heap) |
Returns 1 if the pairing heap is empty, and 0 if not. | |
size_t | pheap_size (const struct pheap *heap) |
Returns the size (in number of nodes) of a pairing heap. More... | |
void | pheap_insert (struct pheap *heap, struct pnode *node) |
Inserts a node into a pairing heap. More... | |
void | pheap_remove (struct pheap *heap, struct pnode *node) |
Removes a node from a pairing heap. More... | |
struct pnode * | pheap_find (const struct pheap *heap, const void *key) |
Finds a node in a pairing heap. More... | |
int | pheap_contains (const struct pheap *heap, const struct pnode *node) |
Checks if a node is part of a pairing heap. More... | |
struct pnode * | pheap_first (const struct pheap *heap) |
Returns a pointer to the first (minimum) node in a pairing heap. More... | |
This header file is part of the utilities library; it contains the pairing heap declarations.
A pairing heap is a half-sorted tree structure suitable for a priority queue. Compared to a self-balancing binary tree, insertion and retrieval of the first (minimum) element is faster (O(1) vs. O(log(n))), while finding an arbitrary element is slower (O(n) vs. O(log(n))).
The pairing heap implemented here is generic and can be used for any kind of key-value pair; only (void) pointers to keys are stored. Upon initialization of the heap, the user is responsible for providing a suitable comparison function (pheap_cmp_t).
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
Definition in file pheap.h.
#define pnode_foreach | ( | first, | |
node | |||
) | pnode_foreach_(__LINE__, first, node) |
Iterates over each node in a pairing heap in unspecified order.
It is safe to remove the current node during the iteration. However, since pheap_remove() may change the order of the nodes, it is not guaranteed that all nodes will be visited.
first | a pointer to the first node. |
node | the name of the pointer to the nodes. This variable is declared in the scope of the loop. |
#define pheap_foreach | ( | heap, | |
node | |||
) | pnode_foreach (pheap_first(heap), node) |
Iterates over each node in a pairing heap in unspecified order.
typedef int pheap_cmp_t(const void *p1, const void *p2) |
The type of a comparison function suitable for use in a paring heap.
p1 and p2 MUST be NULL or point to objects of the same type.
|
inline |
|
inline |
|
inline |
Inserts a node into a pairing heap.
This is an O(1) operation. This function does not check whether a node with the same key already exists, or whether the node is already part of another heap. It is the responsibility of the user to ensure that the node is not part of the heap before calling this function.
Removes a node from a pairing heap.
This is an (amortized) O(log(n)) operation. It is the responsibility of the user to ensure that the node is part of the heap before calling this function.
Finds a node in a pairing heap.
This is an O(n) operation.