module__pheap.c File Reference

Pairing heap. More...

#include <assert.h>
#include <stdlib.h>
#include <kuroko/vm.h>
#include <kuroko/util.h>

Include dependency graph for module__pheap.c:

Go to the source code of this file.

Data Structures
struct	PHeap
struct	PHeap_Obj

Macros
#define	IS_PHeap(o)   (krk_isInstanceOf(o,PHeapClass))
#define	AS_PHeap(o)   ((struct PHeap_Obj*)AS_OBJECT(o))
#define	CURRENT_CTYPE   struct PHeap_Obj *
#define	CURRENT_NAME   self

Typedefs
typedef struct PHeap	PHeap
	Heap node. More...
typedef int(*	pheap_comparator_func) (PHeap *, PHeap *)
	Heap comparator function. More...

Functions
KrkValue	_PHeap___init__ (int, KrkValue *, int)
KrkValue	_PHeap_insert (int, KrkValue *, int)
KrkValue	_PHeap_peek (int, KrkValue *, int)
KrkValue	_PHeap_pop (int, KrkValue *, int)
KrkValue	_PHeap___bool__ (int, KrkValue *, int)
KrkValue	_PHeap___len__ (int, KrkValue *, int)
KrkValue	_PHeap_visit (int, KrkValue *, int)
KrkValue	_PHeap_comp (int, KrkValue *, int)
	KRK_Module (_pheap)

Detailed Description

Pairing heap.

Author

K. Lange klang.nosp@m.e@to.nosp@m.aruos.nosp@m..org

A very simple pairing heap.

Provides a min-heap with insert, peek, and pop.

While heap entries may be mutable, care should be taken not to modify any values used for comparison, as the heap can not update ordering.

This could likely be improved by the implementation of parent pointers, which can allow for elements of the heap other than the root to be removed or updated (removal + reinsertion), but that requires the ability to quickly reference specific elements - which requires the heap "nodes" to also be accessible or addressible in some way, such as by making them Kuroko objects. Such a change would likely result in performance impacts, so a parent-pointer pairing heap should be a separate class.

The implementation here is based strongly on the pseudocode found in the Wikipedia article "Paring heap".

Definition in file module__pheap.c.

Typedef Documentation

PHeap

typedef struct PHeap PHeap

Heap node.

Represents one element in the heap. Each element potentially has a pointer to more elements (a "right" or "next" pointer) and a pointer to a subheap (a "left" pointer).

Definition at line 30 of file module__pheap.c.

pheap_comparator_func

typedef int(* pheap_comparator_func) (PHeap *, PHeap *)

Heap comparator function.

The heap is ostensibly a min-heap, but the comparison behavior is left entirely to the user. A comparator function should return true if the left (first) argument has priority (is less than) the right (second) argument, and 0 otherwise. This comparison must be consistent or the heap will not work correctly.

Generally, this module only uses one comparison function: a wrapper that calls a Kuroko callable. As Kuroko callables may hold their own state, no facility was necessary to pass user data to the comparator - only the left and right heap nodes to compare are given.

Definition at line 61 of file module__pheap.c.