1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
<HTML><HEAD>
<!!---------------------------------------------------------------------->
<!! Copyright (C) 1999 Dietmar Kuehl, Claas Solutions GmbH >
<!!>
<!! Permission to use, copy, modify, distribute and sell this >
<!! software for any purpose is hereby granted without fee, provided >
<!! that the above copyright notice appears in all copies and that >
<!! both that copyright notice and this permission notice appear in >
<!! supporting documentation. Dietmar Kuehl and Claas Solutions make no >
<!! representations about the suitability of this software for any >
<!! purpose. It is provided "as is" without express or implied warranty. >
<!!---------------------------------------------------------------------->
<TITLE>mfd/f_heap.3</TITLE>
</HEAD>
<BODY BGCOLOR=white LINK="0000FF" VLINK="800080">
<IMG SRC=../../c++boost.gif ALIGN=TOP WIDTH=277 HEIGHT=86><BR>
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0 COLS=2>
<TR><TD WIDTH=109 VALIGN=TOP><IMG SRC=sidebar.jpg WIDTH=109 HEIGHT=494>
</TD><TD>
<SPACER TYPE=VERTICAL SIZE=40>
<H1>Template Class <nobr><tt>f_heap<T, Comp></tt></nobr></H1>
<A NAME="Synopsis"><H1>Synopsis</H1></A>
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0 COLS=2>
<TR><TD WIDTH=30 VALIGN=TOP></TD><TD>
<PRE>
#include "boost/f_heap.hpp"
template <class T>
class boost::fibonacci_heap_base
{
public:
class iterator
{
public:
iterator();
bool operator== (iterator const& it) const;
bool operator!= (iterator const& it) const;
T const& operator* () const;
T const* operator-> () const;
iterator &operator++ ();
iterator operator++ (int);
};
public:
bool <A HREF="heap-common.html#empty">empty</A>() const;
size_type <A HREF="heap-common.html#size">size</A>() const;
iterator <A HREF="heap-common.html#begin">begin</A>() const;
iterator <A HREF="heap-common.html#end">end</A>() const;
private:
fibonacci_heap_base(fibonacci_heap_base const&); // deliberately not implemented
void operator=(fibonacci_heap_base const&); // deliberately not implemented
};
template <class T, class Comp = std::less<T> >
class boost::fibonacci_heap: public boost::fibonacci_heap_base<T>
{
public:
typedef <I>unsigned integral type</I> <A HREF="heap-common.html#size_type">size_type</A>;
typedef <I>pointer type</I> <A HREF="heap-common.html#pointer">pointer</A>;
typedef T <A HREF="heap-common.html#value_type">value_type</A>;
typedef T const& <A HREF="heap-common.html#const_reference">const_reference</A>;
typedef typename fibonacci_heap_base<T>::iterator <A HREF="heap-common.html#const_iterator">const_iterator</A>;
typedef Comp <A HREF="heap-common.html#compare_type">compare_type</A>;
explicit <A HREF="heap-common.html#default-ctor">fibonacci_heap</A>(Comp const& comp = Comp());
pointer <A HREF="heap-common.html#push">push</A>(T const& val);
void <A HREF="heap-common.html#pop">pop</A>();
T const& <A HREF="heap-common.html#top">top</A>() const;
void <A HREF="heap-common.html#remove">remove</A>(pointer ptr);
template <typename K> void <A HREF="heap-common.html#change_top">change_top</A>(K const& val);
template <typename K> void <A HREF="heap-common.html#change">change</A>(pointer ptr, K const& val);
template <typename K> void <A HREF="heap-common.html#decrease">decrease</A>(pointer ptr, K const& val);
template <typename K> void <A HREF="heap-common.html#increase">increase</A>(pointer ptr, K const& val);
};
</PRE></TD></TABLE>
<A NAME="Description"><H1>Description</H1></A>
Fibonacci heaps are asymptotically the best priority queues known: They
perform all heap operations in O(log n) time, some even in amortized constant time.
However, in practise they are "known" (by the theoreticians) to be inferior
eg. to <A HREF="d_heap.html">d-heaps</A> because their internal maintenance is
relatively involved. Performance tests (with random data) indicated that
they are indeed a bit slower but not too much (at least for many elements).
<P>
Fibonacci heaps are organized as a collection of trees which are somewhat
similar to Binomial trees. Here is what is basically done: If a node becomes
a root (this happens eg. if new node is pushed on the heap or during certain
heap operations) it is checked if there is already a root with the same
degree. If this is the case, the two nodes are linked to combine a new
tree by making the smaller node a child of the larger node. Thereby a
tree with a larger degree is formed which is potentially linked again
with a corresponding tree. Thus, the degrees of the roots of all trees
differs. If a node has to be removed from its parent, eg. because it
became larger due to a <A HREF="heap-common.html#increase"><nobr><tt>increase</tt></nobr>()</A>
operation or because the parent node is removed from the priority queue,
it becomes a new root which is, of course, potentially linked. This
approach could yield to degenerated trees and thus there is an additional
rule: if a node lost more than one child, it is cut and made a new root.
This process may lead to cascading cuts.
<P>
The similarity to Binomial trees is due to their construction: In a
Binomial tree, each tree of degree <I>n</I> has <I>n</I> children
with degrees <I>0</I> to <I>n-1</I>. This also applies to the trees in
Fibonacci heaps since they are basically constructed the same way as
Binomial trees are constructed, namely by using two trees of degree
<I>n</I> to form a tree of degree <I>n+1</I>. However, due to the
cuts applies in Fibonacci heaps the trees in a Fibonacci heap are
normally not Binomial heaps.
<P>
For more information on Fibonacci heaps see eg. <I>Introduction
to Algorithms</I>, Corman, Leiserson, Rivest, MIT Press, or <I>Network Flow</I>, Ahuja, Magnanti, Orlin, Prentice Hall. I used the
latter to create this implementation (I like their descriptions
in general because they often map quite directly to an
implementation). However, the implementation looks quite different
from this description to get the implementation fast...
<P>
For a description of the methods of <nobr><tt>fibonacci_heap<T, Comp></tt></nobr> see the
description of <A HREF="heap-common.html">common methods</A>.
<A NAME="See Also"><H1>See Also</H1></A>
<A HREF="heap.html">heap(3)</A>,
<A HREF="heap-common.html">heap-common(3)</A>
<HR>
Copyright © 1999 <A HREF=http://www.claas-solutions.de/kuehl>Dietmar Kühl</A> (<A HREF="mailto:dietmar.kuehl@claas-solutions.de">dietmar.kuehl@claas-solutions.de</A>)<BR>
<a href="http://www.claas-solutions.de/">Claas Solutions GmbH</a>
</TD></TR></TABLE>
</BODY></HTML>
|
