Lely core libraries  2.2.5
pheap.c File Reference

This file is part of the utilities library; it contains the implementation of the pairing heap. More...

#include "util.h"
#include <lely/util/pheap.h>
#include <assert.h>
Include dependency graph for pheap.c:

Go to the source code of this file.

Functions

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 pnodepheap_find (const struct pheap *heap, const void *key)
 Finds a node in a pairing heap. More...
 

Detailed Description

This file is part of the utilities library; it contains the implementation of the pairing heap.

See also
lely/util/pheap.h
Author
J. S. Seldenthuis jseld.nosp@m.enth.nosp@m.uis@l.nosp@m.ely..nosp@m.com

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.c.

Function Documentation

◆ pheap_insert()

void pheap_insert ( struct pheap heap,
struct pnode node 
)

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.

See also
pheap_remove(), pheap_find()

Definition at line 37 of file pheap.c.

◆ pheap_remove()

void pheap_remove ( struct pheap heap,
struct pnode node 
)

Removes a node from a pairing heap.

This is an (amortized) O(log(n)) operation.

See also
pheap_insert()

Definition at line 65 of file pheap.c.

◆ pheap_find()

struct pnode* pheap_find ( const struct pheap heap,
const void *  key 
)

Finds a node in a pairing heap.

This is an O(n) operation.

Returns
a pointer to the node if found, or NULL if not.
See also
pheap_insert()

Definition at line 91 of file pheap.c.