grafalgo::HeapSet Class Reference

This class implements a collection of heaps. More...

#include <HeapSet.h>

Inheritance diagram for grafalgo::HeapSet:

Collaboration diagram for grafalgo::HeapSet:

List of all members.

Public Member Functions
	HeapSet (int, int)
void	clear ()
void	resize (int)
void	expand (int)
void	copyFrom (const List &)
index	findMin (int) const
uint64_t	getKey (index) const
int	heapSize (int) const
bool	empty (int)
bool	insert (index, uint64_t, int)
index	deleteMin (int)
void	changeKeyMin (uint64_t, int)
string &	toString (int, string &) const
Private Member Functions
index	nodeMinPos (int) const
	position of smallest item in node
void	siftup (index, int)
	move item up to restore heap order
void	siftdown (index, int)
	move down to restore heap order
Private Attributes
int	maxHeap
	max number of heaps
index *	heaps
	holds all items
uint64_t *	key
	key[i] is key of item i
int *	root
	root[h] is position of heap h root
int *	bot
	bot[h] is position of "bottom" node
int *	hSize
	hSize[h] is # of items in heap h
int *	child
	child[p] points to first child of p
int *	parent
	parent[p/D] points to parent of p
int *	pred
	pred[p/D] is predecessor of p
int	free
	start of free node list
Static Private Attributes
static const int	d = 8
	base of heap

---

Detailed Description

This class implements a collection of heaps.

Items to be stored in the heap are identified by integers in 1..N, where N is a parameter specified in the constructor. Heaps are identified by integers in 1..M where M is another parameter to the constructor. Each item may be stored in at most one heap. Keys are 64 bit unsigned ints.

Heaps are implemented using a variant of the d-heap.

Definition at line 27 of file HeapSet.h.

---

Member Function Documentation

void grafalgo::DiffHeap::siftup	(	index	,
		int
	)		[private]

move item up to restore heap order

Perform siftup operation to restore heap order.

This is a private helper function.

Parameters:

i	is the index of an item to be positioned in the heap
ki	is the key of i
x	is a tentative position for i in the heap
kpx	is the key of the parent of the item at position x

tricky to get this right - maybe try letting dkey(x) become negative, then adjusting heap until all are non-negative

Definition at line 130 of file DiffHeap.cpp.

---

The documentation for this class was generated from the following files:

• /Users/jst/src/grafalgo/cpp/include/HeapSet.h
• /Users/jst/src/grafalgo/cpp/dataStructures/heaps/DiffHeap.cpp