-
Notifications
You must be signed in to change notification settings - Fork 55
Expand file tree
/
Copy pathHeapsort.html
More file actions
635 lines (587 loc) · 23.7 KB
/
Heapsort.html
File metadata and controls
635 lines (587 loc) · 23.7 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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
<html>
<!-- THIS FILE WAS GENERATED BY A SCRIPT: DO NOT EDIT IT! -->
<head>
<link href="style.css" rel="stylesheet" type="text/css"/>
<title>
Design and Analysis of Algorithms: Heapsort
</title>
</head>
<body>
<div id="header">
<div id="logo">
<img src="graphics/Julia.png">
</div>
<div id="user-tools">
<a href="index.html">Home</a>
<a href="about.html">About</a>
<a href="feedback.html">Feedback</a>
</div>
</div>
<h1>
Design and Analysis of Algorithms: Heapsort
</h1>
<div style="text-align:center">
<p>
<img src="https://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif">
</p>
</div>
<details>
<summary class="sum1">
Overview
</summary>
<details>
<summary class="sum2">
What is a heap?
</summary>
<p>
Heaps are used in many famous algorithms such as:
</p>
<ul>
<li>
Dijkstra's algorithm for finding the shortest path
</li>
<li>
The heapsort sorting algorithm
</li>
<li>
Implementing priority queues
</li>
</ul>
<p>
Essentially,
heaps are the data structure you want to use when you want to be
able to access the maximum or minimum element very quickly.There
are many variations of heaps, each offering advantages and
tradeoffs.<br>
<b>Definition</b><br>
The (binary) heap data structure is an array object that we can
view as a nearly complete binary tree as shown in the figure
below.Each node of the tree corresponds to an element of the
array. The tree is completely filled on all levels except
possibly the lowest, which is filled from the left up to a point.
<br><br><br>
</p>
<figure>
<iframe width="560" height="315"
src="https://www.youtube.com/embed/M3B0UJWS_ag"
frameborder="0" allowfullscreen></iframe>
<figcaption>
Heapify
</figcaption>
</figure>
</details>
<details>
<summary class="sum2">
Notes
</summary>
<p>
A heap data structure
(not garbage-collected storage) is a nearly complete
binary tree.
</p>
<ul>
<li>
Height of node = # of edges on a longest simple path
from the node down to a leaf.<br>
</li>
<li>
Height of heap = height of root = (lg n). A heap can
be stored as an array A.<br>
</li>
<li>
Root of tree is A[0].<br>
</li>
<li>
Parent of A[i] = A[⌊i/2⌋].<br>
</li>
<li>
Left child of A[i] = A[2i ].<br>
</li>
<li>
Right child of A[i] = A[2i + 1].<br>
</li>
</ul>
</details>
</details>
<details>
<summary class="sum1">
Maintaining the heap property
</summary>
<p>
Heapify is a procedure for manipulating heap data structures.
It is given an array A and index i into the array.
The subtree rooted at the children of A[i] are heap but node A[i]
itself may possibly violate the heap
property i.e., A[i] < A[2i]
or A[i] < A[2i +1]. The procedure
'Heapify' manipulates the tree
rooted at A[i] so it becomes a heap. In other words, 'Heapify'
is let the value at A[i] "float down" in a heap so that subtree
rooted at index i becomes a heap.<br><br>
There are two general versions of the heap property: a min-heap
property and a max-heap property.
</p>
<details>
<summary class="sum2">
Types of Heap Property
</summary>
<details>
<summary class="sum3">
Max Heap Property
</summary>
<p>
If A is an array representation of a heap, then in Max-heap: <br>
A[parent(i)] > A[i] <br>
which means that a node can't have a greater value than its
parent. In a max-heap, the largest element
is stored at the root, and the minimum elements are in the
leaves.
</p>
</details>
<details>
<summary class="sum3">
Min Heap Property
</summary>
<p>
If B is an array representation of a heap then, in Min-heap:<br>
B[parent(i)] < B[i] <br> which means that a parent node can't
have a greater value than its children. Thus, the minimum
element is located at the root, and the maximum elements are
located in the leaves
</p>
</details>
</details>
<details>
<summary class="sum2">
Outline of the Heapify Procedure
</summary>
<p>
Heapify picks the largest child key and compare it to the parent
key.
If parent key is larger, then heapify quits, otherwise it swaps the
parent key with the largest child key. So that the parent is now
becomes larger than its children.
It is important to note that swap may
destroy the heap property of the subtree rooted at the largest
child node.
If this is the case, Heapify calls itself again using largest
child node as the new root. <br><br>
<code>
Heapify(A, i) <br>
l = left [i] <br>
r = right [i] <br>
if l ≤ heap-size [A] and A[l] > A[i] <br>
largest = l <br>
else largest = i <br>
if r ≤ heap-size [A] and A[r] > A[largest] <br>
largest = r <br>
if largest != i <br>
exchange A[i] with A[largest] <br>
Heapify (A, largest) <br><br>
</code>
</p>
<br><br><br>
<figure>
<iframe width="560" height="315"
src="https://www.youtube.com/embed/CAbDbiCfERY"
frameborder="0" allowfullscreen></iframe>
<figcaption>
Build Heap
</figcaption>
</figure>
</details>
<details>
<summary class="sum2">
Quiz
</summary>
<ol>
<li>
The max heap property means that
</li>
<ol type="a" class="nested">
<li>
<input type="radio" name="q1" value="a">
a node can't have a greater value than its parent
</li>
<li>
<input type="radio" name="q1" value="b">
a node must have a value equal to its parent
</li>
<li>
<input type="radio" name="q1" value="c">
a node can't have a lesser than its parent
</li>
<li>
<input type="radio" name="q1" value="d">
all values must be heaped up in one node
</li>
</ol>
<li>
In a max-heap, element with the greatest key is always in the which node?
</li>
<ol type="a" class="nested">
<li>
<input type="radio" name="q2" value="a">
first node to the right
</li>
<li>
<input type="radio" name="q2" value="b">
root node
</li>
<li>
<input type="radio" name="q2" value="c">
first node to the left
</li>
<li>
<input type="radio" name="q2" value="d">
leaf node
</li>
</ol>
<li>
What is the complexity of adding an element to the heap.
</li>
<ol type="a" class="nested">
<li>
<input type="radio" name="q3" value="a">
O(nlogn)
</li>
<li>
<input type="radio" name="q3" value="b">
o(n^2)
</li>
<li>
<input type="radio" name="q3" value="c">
O(logn)
</li>
<li>
<input type="radio" name="q3" value="d">
O(n)
</li>
</ol>
</ol>
<details>
<summary class="sum3">
Answers
</summary>
<p>
1. a; 2. b; 3. c;
</p>
</details>
</details>
</details>
<details>
<summary class="sum1">
Building a heap
</summary>
<blockquote>
<ul>
<li style="font-size:15px" ><p><strong>Build Heap</strong>:
Constructs the heap. Build-Heap is usually implemented using
the <code>Insert</code> and <code>Heapify</code> function
repeatedly. So starting from an empty heap,
nodes are added with <code>Insert</code> and then
<code>Heapify</code> is called to make sure the
heap maintains the heap properties at each step.</p></li>
<li style="font-size:15px" ><p><strong>Heapify</strong>:
Used to maintain the heap properties (described in above sections).</p></li>
<li style="font-size:15px"><p><strong>Insert</strong>:
Add elements to the heap. </p></li>
<li style="font-size:15px"><p><strong>Remove</strong>:
Delete elements from the heap. </p></li>
<li style="font-size:15px"><p><strong>Find Minimum/Maximum</strong> and <strong>Extract Minimum/Maximum</strong>:
Depending
on the purpose of the heap, return the the largest or smallest elements.</p></li>
</ul>
</blockquote>
<figure>
<iframe width="560" height="315"
src="https://www.youtube.com/embed/2ihStWiKQTA"
frameborder="0" allowfullscreen></iframe>
<figcaption>
Building a heap
</figcaption>
</figure>
</details>
<details>
<summary class="sum1">
The heap sort algorithm
</summary>
<p>
Heapsort is a comparison based sorting algorithm that uses a
binary heap data structure. Like mergesort, heapsort has a running
time of O(nlogn) and like insertion sort, heapsort sorts in-place
so no extra space is needed during the sort. The binary heap data
structure allows the heapsort algorithm to take advantage of the
heap's heap properties and the heapsort algorithm makes use of the
efficient running time for inserting to and deleting from the heap
.<br>
</p>
<details>
<summary class="sum2">
Implementation
</summary>
<p>
The heap sort algorithm starts by using procedure BUILD-HEAP to
build a heap on the input array A[1 . . n]. Since the maximum
element of the array stored at the root A[1], it can be put into
its correct final position by exchanging it with A[n] (the last
element in A). If we now discard node n from the heap than the
remaining elements can be made into heap. Note that the new
element at the root may violate the heap property. All that is
needed to restore the heap property. <br><br>
<code>
HEAPSORT(A) <br>
  BUILD-MAX-HEAP(A) <br>
  for i = A.length downto 2 <br>
      exchange A[1] with A[i] <br>
      A.heap-size = A.head-size - 1 <br>
      MAX-HEAPIFY(A, 1) <br><br><br>
</code>
The HEAPSORT procedure takes time O(n lg n), since the call to
BUILD_HEAP takes time O(n) and each of the n -1 calls to Heapify
takes time O(lg n).
</p>
<figure>
<iframe width="560" height="315"
src="https://www.youtube.com/embed/2DmK_H7IdTo"
frameborder="0" allowfullscreen></iframe>
<figcaption>
Heap Sort
</figcaption>
</figure>
</details>
</details>
<details>
<summary class="sum1">
Priority queues
</summary>
<details>
<summary class="sum2">
Overview
</summary>
<p>
<br>According to wikipedia: A <strong>Priority queue</strong> is an
abstract data type which is like a regular queue or stack data
structure, but where additionally each element has a "priority"
associated with it.<br><br>
Simply priority queue is an extension of queue with the following
properties.<br>
1) Every item has a priority associated with it. <br>
2) A high priority element is dequeued before an element with low
priority <br>
3) If two elements have the same priority, they are served
according to their order in the queue <br>
</p>
<figure>
<iframe width="560" height="315"
src="https://www.youtube.com/embed/-WEku8ZnynU"
frameborder="0" allowfullscreen></iframe>
<figcaption>
Priority queue
</figcaption>
</figure>
</details>
<details>
<summary class="sum2">
Heaps as priority queues
</summary>
<p>
Although heapsort is an excellent algorithm, a good implementation
of quicksort will beat
heapsort in practice. The heap data structure has a lot of varied
use but it is most popularly used to implement priority queues.
<br><br>
Heapa are generally preferred for priority queue implementation
because heaps provide better performance when compared to priority
queues implemented using arrays or linked list. In a Binary Heap,
<code>heap-maximum()</code> can be implemented in <code>
O(1) time</code>, <code> insert() </code> can be implemented in
<code> O(lg n) </code> time and <code> extract-maximum()
</code> can also be implemented in <code> O(lg n) </code> time
as compared to <code> O(n) </code> in case of linked list.
</p>
</details>
<details>
<summary class="sum2">
Max priority queues
</summary>
<p>
A max priority queue is priority queue based on a max heap and
supports the following operations: <br>
1) <code>max-heap-insert(A, key) </code>
inserts the element x into the heap A while maintaining the heap
property.
</p>
<pre>
max-heap-insert(A, key)
A.heap-size = A.heap-size + 1;
A[A.heap-size] = -Inf;
heap-increase-key(A, A.heap-size, key);
Complexity: O(lg N).
</pre>
<p>
2) <code> maximum(S) </code> returns the element of S with the
largest key.<br>
</p>
<pre>
maximum(A)
return A[1]
Complexity: O(1)
</pre>
<p>
3) <code>extract-max(A)</code> removes and returns the element
of S with the largest key. <br>
</p>
<pre>
extract_maximum (A)
if(A.heap-size < 1)
error("Cannot remove element as queue is empty");
int max = Arr[1];
Arr[1] = Arr[length];
length = length -1;
max_heapify(Arr, 1);
return max;
}
Complexity: O(lg n)
</pre>
<p>
4) <code> increase-key(A, x, k) </code> increases the value of
element x's key to the new value k, which is assumed to be at
least as large as x's current key value.<br>
</p>
<pre>
increase-key (A, x, key) {
if(key < A[i]) {
error("New value is less than current value, can't be
inserted");
}
A[i] = key;
while( i > 1 and A[i/2] < A[i]){
swap(A[i/2], A[i]);
i = i/2;
}
}
Complexity: O(log N).
</pre>
</details>
<details>
<summary class="sum2">
Applications
</summary>
<p>
Some of the applications of the priority queues are as follows<br>
<br>
1) <strong> Schedule jobs on a shared computer</strong>:
We can use max-priority queues to schedule jobs on a
shared computer. The max-priority queue keeps track of the jobs
to be performed and their relative priorities. When a job is
finished or interrupted, the scheduler selects the
highest-priority job from among those pending by calling
<code>EXTRACT-MAX</code>. The scheduler can add a new job to
the queue at any time by calling <code>INSERT</code>. <br>
2) <strong>Event driven simulator</strong>: A min-priority queue
can be used in an event driven simulator.The items in the queue
are events to be simulated, each with an associated time of
occurrence that serves as its key. The events must be simulated
in order of their time of occurrence, because the simulation
of an event can cause other events to be simulated in the future
<br>
3) <strong>Graph Search Algorithms</strong>: Many efficient graph
search algorithms such as <code>A* search</code> and
<code>Dijkstra's algorithm </code> use priority queues to know
which nodes to explore next.<br>
4) <strong>Bandwidth Management</strong>: Priority queues are used
to handle data flows on the network. As not all data are of same
importance by prioritizing the important data packets the router
can make sure that the network performs optimally and all the
prioritized traffic is forwarded with the least delay and the
least likelihood of being rejected in case of the router reaching
its max traffic capacity.
</p>
</details>
</details>
<details>
<summary class="sum1">
Run the Python code
</summary>
<p>
In the console below, type or paste:
<br/>
<code>
!git clone https://gist.github.com/17b7d4beac379c4e11448a62a9a94a1b.git
<br/>
cd 17b7d4beac379c4e11448a62a9a94a1b
<br/>
from heapsort import *
<br/>
A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
<br/>
</code>
</p>
<div class="python-console">
<iframe style="width: 640; height: 480;"
name="embedded_python_anywhere"
src="https://www.pythonanywhere.com/embedded3/" scrolling="yes">
</iframe>
<figcaption>
Python console
</figcaption>
</div>
<p>
To run the example from the textbook, type:
<br/>
<code>
A
<br/>
# MAX or MIN
<br/>
build_heap(A, MAX)
<br/>
heapsort(A, MAX)
</code>
</p>
<p>
Now you can experiment with the algorithm by typing
in your own array (my_array = [x, y, z])
and running build_heap(my_array) or
heapsort(a_array, b_array).
</p>
</details>
<details>
<summary class="sum1">
Source Code
</summary>
<p>
<a href="https://github.com/gcallah/algorithms/tree/master/Java/Heapsort">Java</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/Ruby/Heapsort">Ruby</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/C++/Heapsort">C++</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/Python/Heapsort">Python</a><br>
</p>
</details>
<h2>
For Further Study
</h2>
<figure>
<iframe width="560" height="315"
src="https://www.youtube.com/embed/6NB0GHY11Iw" frameborder="0"
allowfullscreen>
</iframe>
</figure>
<h2>
Homework
</h2>
<p>
On NYU Classes.
</p>
</body>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-97026578-2', 'auto');
ga('send', 'pageview');
</script>
</html>