DHeap< T > Class Template Reference

#include <dheap.h>

Inheritance diagram for DHeap< T >:

List of all members.

Public Member Functions
bool	isHeap ()
	check the double heap conditions are met, mainly for debugging purpouses
T &	max ()
T &	min ()
T	popMax ()
T	popMin ()
void	push (const T &elt)
void	rebuild ()
Protected Member Functions
T &	at (int n)
void	bubbleUp (int i)
void	bubbleUpMax (int i)
void	bubbleUpMin (int i)
int	greatestChild (int i)
int	isMax (int e) const
int	leftChildMax (int i) const
int	leftChildMin (int i) const
int	parentMax (int i) const
int	parentMin (int i) const
int	smallestChild (int i)
void	swap (int a, int b)
void	trickleDownMax (int i)
void	trickleDownMin (int i)

---

Detailed Description

template<class T>
class DHeap< T >

Double ended heap inspired by Min-Max Heaps and Generalized Priority Queues M. D. ATKINSON,J.-R. SACK, N. SANTORO,and T. STROTHOTTE

This structure allows for quick extraction of biggest and smaller item out of a set with linear reconstruction of the ordering.

DHeap exposes the public interface of vector. (push_back(), resize() etc.).

Compared to a stl heap, rebuild is 15% longer, extraction is 2x longer, but you get both min and max extraction in log(n) time.

Definition at line 46 of file dheap.h.

---

Member Function Documentation

template<class T>

T& DHeap< T >::at

(

int

n

)

[inline, protected]

Definition at line 90 of file dheap.h.

template<class T>

void DHeap< T >::bubbleUp

(

int

i

)

[inline, protected]

Definition at line 194 of file dheap.h.

template<class T>

void DHeap< T >::bubbleUpMax

(

int

i

)

[inline, protected]

Definition at line 182 of file dheap.h.

template<class T>

void DHeap< T >::bubbleUpMin

(

int

i

)

[inline, protected]

Definition at line 170 of file dheap.h.

template<class T>

int DHeap< T >::greatestChild

(

int

i

)

[inline, protected]

Definition at line 111 of file dheap.h.

template<class T>

bool DHeap< T >::isHeap

(

)

[inline]

check the double heap conditions are met, mainly for debugging purpouses

Definition at line 215 of file dheap.h.

template<class T>

int DHeap< T >::isMax

(

int

e

)

const [inline, protected]

Definition at line 92 of file dheap.h.

template<class T>

int DHeap< T >::leftChildMax

(

int

i

)

const [inline, protected]

Definition at line 96 of file dheap.h.

template<class T>

int DHeap< T >::leftChildMin

(

int

i

)

const [inline, protected]

Definition at line 95 of file dheap.h.

template<class T>

T& DHeap< T >::max

(

)

[inline]

Definition at line 67 of file dheap.h.

template<class T>

T& DHeap< T >::min

(

)

[inline]

Definition at line 54 of file dheap.h.

template<class T>

int DHeap< T >::parentMax

(

int

i

)

const [inline, protected]

Definition at line 94 of file dheap.h.

template<class T>

int DHeap< T >::parentMin

(

int

i

)

const [inline, protected]

Definition at line 93 of file dheap.h.

template<class T>

T DHeap< T >::popMax

(

)

[inline]

Definition at line 72 of file dheap.h.

template<class T>

T DHeap< T >::popMin

(

)

[inline]

Definition at line 56 of file dheap.h.

template<class T>

void DHeap< T >::push

(

const T &

elt

)

[inline]

Definition at line 49 of file dheap.h.

template<class T>

void DHeap< T >::rebuild

(

)

[inline]

Definition at line 84 of file dheap.h.

template<class T>

int DHeap< T >::smallestChild

(

int

i

)

[inline, protected]

Definition at line 101 of file dheap.h.

template<class T>

void DHeap< T >::swap	(	int	a,
		int	b
	)		[inline, protected]

Definition at line 98 of file dheap.h.

template<class T>

void DHeap< T >::trickleDownMax

(

int

i

)

[inline, protected]

Definition at line 146 of file dheap.h.

template<class T>

void DHeap< T >::trickleDownMin

(

int

i

)

[inline, protected]

Definition at line 123 of file dheap.h.

---

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

• dheap.h