forked from sarathavasarala/EloquentJavaScript
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathappendix2.html
More file actions
206 lines (197 loc) · 20.8 KB
/
appendix2.html
File metadata and controls
206 lines (197 loc) · 20.8 KB
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
<html><head><link rel="stylesheet" type="text/css" href="css/book.css"/><link rel="stylesheet" type="text/css" href="css/highlight.css"/><link rel="stylesheet" type="text/css" href="css/console.css"/><link rel="stylesheet" type="text/css" href="css/codemirror.css"/><meta http-equiv="Content-Type" content="text/html; charset=utf-8"/><title>Binary Heaps -- Eloquent JavaScript</title></head><body><script type="text/javascript" src="js/before.js"> </script><div class="content"><script type="text/javascript">var chapterTag = 'binaryheap';</script><div class="navigation"><a href="appendix1.html"><< Previous chapter</a> | <a href="contents.html">Contents</a> | <a href="index.html">Cover</a> | Next chapter >></div><h1><span class="number">Appendix 2: </span>Binary Heaps</h1><div class="block"><p><a class="paragraph" href="#p4e2b9c86" name="p4e2b9c86"> ¶ </a>In <a href="chapter7.html">chapter 7</a>, the <a name="key1"></a>binary heap was introduced as a method to store a
collection of objects in such a way that the smallest element can be
quickly found. As promised, this appendix will explain the details
behind this data structure.</p><p><a class="paragraph" href="#pcec8fab" name="pcec8fab"> ¶ </a>Consider again the problem we needed to solve. The A* algorithm
created large amounts of small objects, and had to keep these in an
'open list'. It was also constantly removing the smallest element from
this list. The simplest approach would be to just keep all the objects
in an array, and search for the smallest one when we need it. But,
unless we have a <em>lot</em> of time, this will not do. Finding the smallest
element in an unsorted array requires going over the whole array, and
checking each element.</p><p><a class="paragraph" href="#p58c2209a" name="p58c2209a"> ¶ </a>The next solution would be, of course, to sort our array. JavaScript
arrays have a wonderful <a name="key2"></a><code>sort</code> method, which can be used to do the
heavy work. Unfortunately, re-sorting a whole array every time an
element is removed is more work than searching for a minimum value in
an unsorted array. Some tricks can be used, such as, instead of
re-sorting the whole array, just making sure new values are inserted
in the right place so that the array, which was sorted before, stays
sorted. This is coming closer to the approach a binary heap uses
already, but inserting a value in the middle of an array requires
moving all the elements after it one place up, which is still just too
slow.</p><p><a class="paragraph" href="#p72e59821" name="p72e59821"> ¶ </a>Another approach is to not use an array at all, but to store the
values in a set of interconnected objects. A simple form of this is to
have every object hold one value and two (or less) links to other
objects. There is one root object, holding the smallest value, which
is used to access all the other objects. Links always point to objects
holding greater values, so the whole structure looks something like
this:</p><div class="illustration"><img src="img/tree.png"/></div><p><a class="paragraph" href="#p2bc11a99" name="p2bc11a99"> ¶ </a>Such structures are usually called <a name="key3"></a>trees, because of the way they
branch. Now, when you need the smallest element, you just take off the
top element and rearrange the tree so that one of the top element's
children ― the one with the lowest value ― becomes the new top. When
inserting new elements, you 'descend' the tree until you find an
element less than the new element, and insert it there. This takes a
lot less searching than a sorted array does, but it has the
disadvantage of creating a lot of objects, which also slows things
down.</p></div><hr/><div class="block"><p><a class="paragraph" href="#p47700f21" name="p47700f21"> ¶ </a>A binary heap, then, does make use of a sorted array, but it is only
partially sorted, much like the tree above. Instead of objects, the
positions in the array are used to form a tree, as this picture tries
to show:</p><div class="illustration"><img src="img/heap.png"/></div><p><a class="paragraph" href="#p4b2c7639" name="p4b2c7639"> ¶ </a>Array element <code>1</code> is the root of the tree, array element <code>2</code> and <code>3</code>
are its children, and in general array element <code>X</code> has children <code>X *
2</code> and <code>X * 2 + 1</code>. You can see why this structure is called a 'heap'.
Note that this array starts at <code>1</code>, while JavaScript arrays start at
<code>0</code>. The heap will always keep the smallest element in position <code>1</code>,
and make sure that for every element in the array at position <code>X</code>, the
element at <code>X / 2</code> (round down) is smaller.</p><p><a class="paragraph" href="#p51c64dc6" name="p51c64dc6"> ¶ </a>Finding the smallest element is now a matter of taking the element at
position <code>1</code>. But when this element is removed, the heap must make
sure that there are no holes left in the array. To do this, it takes
the last element in the array and moves it to the start, and then
compares it to its child elements at position <code>2</code> and <code>3</code>. It is
likely to be greater, so it is exchanged with one of them, and the
process of comparing it with its children is repeated for the new
position, and so on, until it comes to a position where its children
are greater, or a position where it has no children.</p><pre class="preformatted">[2, 3, 5, 4, 8, 7, 6]
Take out 2, move 6 to the front.
[6, 3, 5, 4, 8, 7]
6 is greater than its first child 3, so swap them.
[3, 6, 5, 4, 8, 7]
Now 6 has children 4 and 8 (position 4 and 5). It is greater than
4, so we swap again.
[3, 4, 5, 6, 8, 7]
6 is in position 4, and has no more children. The heap is in order
again.</pre><p><a class="paragraph" href="#p3e6493a9" name="p3e6493a9"> ¶ </a>Similarly, when an element has to be added to the heap, it is put at
the end of the array and allowed to 'bubble' up by repeatedly
exchanging it with its parent, until we find a parent that is less
than the new node.</p><pre class="preformatted">[3, 4, 5, 6, 8, 7]
Element 2 gets added again, it starts at the back.
[3, 4, 5, 6, 8, 7, 2]
2 is in position 7, its parent is at 3, which is a 5. 5 is greater
than 2, so we swap.
[3, 4, 2, 6, 8, 7, 5]
The parent of position 3 is position 1. Again, we swap.
[2, 4, 3, 6, 8, 7, 5]
The element can not go further than position 1, so we are done.</pre><p><a class="paragraph" href="#p4e036f0f" name="p4e036f0f"> ¶ </a>Note how adding or inserting an element does not require it to be
compared with every element in the array. In fact, because the jumps
between parents and children get bigger as the array gets bigger, this
advantage is especially large when we have a lot of elements<a class="footref" href="#footnote1">1</a>.</p></div><hr/><div class="block"><p><a class="paragraph" href="#p11be5673" name="p11be5673"> ¶ </a>Here is the full code of a binary heap implementation. Two things to
note are that, instead of directly comparing the elements put into the
heap, a function (<code>scoreFunction</code>) is first applied to them, so that
it becomes possible to store objects that can not be directly
compared.</p><p><a class="paragraph" href="#p4713954c" name="p4713954c"> ¶ </a>Also, because JavaScript arrays start at <code>0</code>, and the parent/child
calculations use a system that starts at <code>1</code>, there are a few strange
calculations to compensate.</p><pre class="code"><span class="keyword">function</span> <span class="variable">BinaryHeap</span>(<span class="variabledef">scoreFunction</span>){
<span class="localvariable">this</span>.<span class="property">content</span> = [];
<span class="localvariable">this</span>.<span class="property">scoreFunction</span> = <span class="localvariable">scoreFunction</span>;
}
<span class="variable">BinaryHeap</span>.<span class="property">prototype</span> = {
<span class="property">push</span>: <span class="keyword">function</span>(<span class="variabledef">element</span>) {
<span class="comment">// Add the new element to the end of the array.</span>
<span class="localvariable">this</span>.<span class="property">content</span>.<span class="property">push</span>(<span class="localvariable">element</span>);
<span class="comment">// Allow it to bubble up.</span>
<span class="localvariable">this</span>.<span class="property">bubbleUp</span>(<span class="localvariable">this</span>.<span class="property">content</span>.<span class="property">length</span> - <span class="atom">1</span>);
},
<span class="property">pop</span>: <span class="keyword">function</span>() {
<span class="comment">// Store the first element so we can return it later.</span>
<span class="keyword">var</span> <span class="variabledef">result</span> = <span class="localvariable">this</span>.<span class="property">content</span>[<span class="atom">0</span>];
<span class="comment">// Get the element at the end of the array.</span>
<span class="keyword">var</span> <span class="variabledef">end</span> = <span class="localvariable">this</span>.<span class="property">content</span>.<span class="property">pop</span>();
<span class="comment">// If there are any elements left, put the end element at the</span>
<span class="comment">// start, and let it sink down.</span>
<span class="keyword">if</span> (<span class="localvariable">this</span>.<span class="property">content</span>.<span class="property">length</span> > <span class="atom">0</span>) {
<span class="localvariable">this</span>.<span class="property">content</span>[<span class="atom">0</span>] = <span class="localvariable">end</span>;
<span class="localvariable">this</span>.<span class="property">sinkDown</span>(<span class="atom">0</span>);
}
<span class="keyword">return</span> <span class="localvariable">result</span>;
},
<span class="property">remove</span>: <span class="keyword">function</span>(<span class="variabledef">node</span>) {
<span class="keyword">var</span> <span class="variabledef">len</span> = <span class="localvariable">this</span>.<span class="property">content</span>.<span class="property">length</span>;
<span class="comment">// To remove a value, we must search through the array to find</span>
<span class="comment">// it.</span>
<span class="keyword">for</span> (<span class="keyword">var</span> <span class="variabledef">i</span> = <span class="atom">0</span>; <span class="localvariable">i</span> < <span class="localvariable">len</span>; <span class="localvariable">i</span>++) {
<span class="keyword">if</span> (<span class="localvariable">this</span>.<span class="property">content</span>[<span class="localvariable">i</span>] == <span class="localvariable">node</span>) {
<span class="comment">// When it is found, the process seen in 'pop' is repeated</span>
<span class="comment">// to fill up the hole.</span>
<span class="keyword">var</span> <span class="variabledef">end</span> = <span class="localvariable">this</span>.<span class="property">content</span>.<span class="property">pop</span>();
<span class="keyword">if</span> (<span class="localvariable">i</span> != <span class="localvariable">len</span> - <span class="atom">1</span>) {
<span class="localvariable">this</span>.<span class="property">content</span>[<span class="localvariable">i</span>] = <span class="localvariable">end</span>;
<span class="keyword">if</span> (<span class="localvariable">this</span>.<span class="property">scoreFunction</span>(<span class="localvariable">end</span>) < <span class="localvariable">this</span>.<span class="property">scoreFunction</span>(<span class="localvariable">node</span>))
<span class="localvariable">this</span>.<span class="property">bubbleUp</span>(<span class="localvariable">i</span>);
<span class="keyword">else</span>
<span class="localvariable">this</span>.<span class="property">sinkDown</span>(<span class="localvariable">i</span>);
}
<span class="keyword">return</span>;
}
}
<span class="keyword">throw</span> <span class="keyword">new</span> <span class="variable">Error</span>(<span class="string">"Node not found."</span>);
},
<span class="property">size</span>: <span class="keyword">function</span>() {
<span class="keyword">return</span> <span class="localvariable">this</span>.<span class="property">content</span>.<span class="property">length</span>;
},
<span class="property">bubbleUp</span>: <span class="keyword">function</span>(<span class="variabledef">n</span>) {
<span class="comment">// Fetch the element that has to be moved.</span>
<span class="keyword">var</span> <span class="variabledef">element</span> = <span class="localvariable">this</span>.<span class="property">content</span>[<span class="localvariable">n</span>];
<span class="comment">// When at 0, an element can not go up any further.</span>
<span class="keyword">while</span> (<span class="localvariable">n</span> > <span class="atom">0</span>) {
<span class="comment">// Compute the parent element's index, and fetch it.</span>
<span class="keyword">var</span> <span class="variabledef">parentN</span> = <span class="variable">Math</span>.<span class="property">floor</span>((<span class="localvariable">n</span> + <span class="atom">1</span>) / <span class="atom">2</span>) - <span class="atom">1</span>,
<span class="variabledef">parent</span> = <span class="localvariable">this</span>.<span class="property">content</span>[<span class="localvariable">parentN</span>];
<span class="comment">// Swap the elements if the parent is greater.</span>
<span class="keyword">if</span> (<span class="localvariable">this</span>.<span class="property">scoreFunction</span>(<span class="localvariable">element</span>) < <span class="localvariable">this</span>.<span class="property">scoreFunction</span>(<span class="localvariable">parent</span>)) {
<span class="localvariable">this</span>.<span class="property">content</span>[<span class="localvariable">parentN</span>] = <span class="localvariable">element</span>;
<span class="localvariable">this</span>.<span class="property">content</span>[<span class="localvariable">n</span>] = <span class="localvariable">parent</span>;
<span class="comment">// Update 'n' to continue at the new position.</span>
<span class="localvariable">n</span> = <span class="localvariable">parentN</span>;
}
<span class="comment">// Found a parent that is less, no need to move it further.</span>
<span class="keyword">else</span> {
<span class="keyword">break</span>;
}
}
},
<span class="property">sinkDown</span>: <span class="keyword">function</span>(<span class="variabledef">n</span>) {
<span class="comment">// Look up the target element and its score.</span>
<span class="keyword">var</span> <span class="variabledef">length</span> = <span class="localvariable">this</span>.<span class="property">content</span>.<span class="property">length</span>,
<span class="variabledef">element</span> = <span class="localvariable">this</span>.<span class="property">content</span>[<span class="localvariable">n</span>],
<span class="variabledef">elemScore</span> = <span class="localvariable">this</span>.<span class="property">scoreFunction</span>(<span class="localvariable">element</span>);
<span class="keyword">while</span>(<span class="atom">true</span>) {
<span class="comment">// Compute the indices of the child elements.</span>
<span class="keyword">var</span> <span class="variabledef">child2N</span> = (<span class="localvariable">n</span> + <span class="atom">1</span>) * <span class="atom">2</span>, <span class="variabledef">child1N</span> = <span class="localvariable">child2N</span> - <span class="atom">1</span>;
<span class="comment">// This is used to store the new position of the element,</span>
<span class="comment">// if any.</span>
<span class="keyword">var</span> <span class="variabledef">swap</span> = <span class="atom">null</span>;
<span class="comment">// If the first child exists (is inside the array)...</span>
<span class="keyword">if</span> (<span class="localvariable">child1N</span> < <span class="localvariable">length</span>) {
<span class="comment">// Look it up and compute its score.</span>
<span class="keyword">var</span> <span class="variabledef">child1</span> = <span class="localvariable">this</span>.<span class="property">content</span>[<span class="localvariable">child1N</span>],
<span class="variabledef">child1Score</span> = <span class="localvariable">this</span>.<span class="property">scoreFunction</span>(<span class="localvariable">child1</span>);
<span class="comment">// If the score is less than our element's, we need to swap.</span>
<span class="keyword">if</span> (<span class="localvariable">child1Score</span> < <span class="localvariable">elemScore</span>)
<span class="localvariable">swap</span> = <span class="localvariable">child1N</span>;
}
<span class="comment">// Do the same checks for the other child.</span>
<span class="keyword">if</span> (<span class="localvariable">child2N</span> < <span class="localvariable">length</span>) {
<span class="keyword">var</span> <span class="variabledef">child2</span> = <span class="localvariable">this</span>.<span class="property">content</span>[<span class="localvariable">child2N</span>],
<span class="variabledef">child2Score</span> = <span class="localvariable">this</span>.<span class="property">scoreFunction</span>(<span class="localvariable">child2</span>);
<span class="keyword">if</span> (<span class="localvariable">child2Score</span> < (<span class="localvariable">swap</span> == <span class="atom">null</span> ? <span class="localvariable">elemScore</span> : <span class="localvariable">child1Score</span>))
<span class="localvariable">swap</span> = <span class="localvariable">child2N</span>;
}
<span class="comment">// If the element needs to be moved, swap it, and continue.</span>
<span class="keyword">if</span> (<span class="localvariable">swap</span> != <span class="atom">null</span>) {
<span class="localvariable">this</span>.<span class="property">content</span>[<span class="localvariable">n</span>] = <span class="localvariable">this</span>.<span class="property">content</span>[<span class="localvariable">swap</span>];
<span class="localvariable">this</span>.<span class="property">content</span>[<span class="localvariable">swap</span>] = <span class="localvariable">element</span>;
<span class="localvariable">n</span> = <span class="localvariable">swap</span>;
}
<span class="comment">// Otherwise, we are done.</span>
<span class="keyword">else</span> {
<span class="keyword">break</span>;
}
}
}
};</pre><p><a class="paragraph" href="#p1c872a7c" name="p1c872a7c"> ¶ </a>And a simple test...</p><pre class="code"><span class="keyword">var</span> <span class="variable">heap</span> = <span class="keyword">new</span> <span class="variable">BinaryHeap</span>(<span class="keyword">function</span>(<span class="variabledef">x</span>){<span class="keyword">return</span> <span class="localvariable">x</span>;});
<span class="variable">forEach</span>([<span class="atom">10</span>, <span class="atom">3</span>, <span class="atom">4</span>, <span class="atom">8</span>, <span class="atom">2</span>, <span class="atom">9</span>, <span class="atom">7</span>, <span class="atom">1</span>, <span class="atom">2</span>, <span class="atom">6</span>, <span class="atom">5</span>],
<span class="variable">method</span>(<span class="variable">heap</span>, <span class="string">"push"</span>));
<span class="variable">heap</span>.<span class="property">remove</span>(<span class="atom">2</span>);
<span class="keyword">while</span> (<span class="variable">heap</span>.<span class="property">size</span>() > <span class="atom">0</span>)
<span class="variable">print</span>(<span class="variable">heap</span>.<span class="property">pop</span>());
</pre></div><ol class="footnotes"><li><a name="footnote1"></a>The amount of comparisons and swaps that are needed ― in the worst
case ― can be approached by taking the logarithm (base 2) of the
amount of elements in the heap.</li></ol><div class="navigation"><a href="appendix1.html"><< Previous chapter</a> | <a href="contents.html">Contents</a> | <a href="index.html">Cover</a> | Next chapter >></div><div class="footer">© <a href="mailto:marijnh@gmail.com">Marijn Haverbeke</a> (<a href="http://creativecommons.org/licenses/by/3.0/">license</a>), written March to July 2007, last modified on May 10 2012.</div></div><script type="text/javascript" src="js/mochi.js"> </script><script type="text/javascript" src="js/codemirror.js"> </script><script type="text/javascript" src="js/ejs.js"> </script></body></html>