Processing math: 100%

DSA Coursenotes

Chapter 5 Week 6

Show Source | | About « 4.4. Comparison :: Contents :: 5.2. Huffman Coding »

5.1. Heaps¶

5.1.1. Heaps¶

5.1.1.1. Complete Trees¶

$\begin{split}\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \textrm{Position} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\ \hline \hline \textrm{Parent} & \,--\, & 0 & 0 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5\\ \hline \textrm{Left Child} & 1 & 3 & 5 & 7 & 9 & 11 & \,--\, & \,--\, & \,--\, & \,--\, & \,--\, & \,--\,\\ \hline \textrm{Right Child} & 2 & 4 & 6 & 8 & 10 & \,--\, & \,--\, & \,--\, & \,--\, & \,--\, & \,--\, & \,--\,\\ \hline \textrm{Left Sibling} & \,--\, & \,--\, & 1 & \,--\, & 3 & \,--\, & 5 & \,--\, & 7 & \,--\, & 9 & \,--\,\\ \hline \textrm{Right Sibling} & \,--\, & 2 & \,--\, & 4 & \,--\, & 6 & \,--\, & 8 & \,--\, & 10 & \,--\, & \,--\,\\ \hline \end{array}\end{split}$

5.1.1.2. Heap insert¶

0 / 0 Settings
<<<>>>

880
851
832
723
734
425
576
67
488
609
10
88
85
83
72
73
6
48
60
42
57

Saving...
Server Error
Resubmit

5.1.1.3. Building a Heap¶

1 / 10 Settings
<<<>>>

Let's look at an efficient way to build the heap. We are going to make a max-heap from a set of input values.

10
21
32
43
54
65
76
1
2
3
4
5
6
7

Saving...
Server Error
Resubmit

5.1.1.4. Building a Heap Proof¶

1 / 13 Settings
<<<>>>

Let's look at a visualization to explain why the cost for buildheap is $\theta(n)$ . We will use an example with 31 records in the heap. This means that there are 16 leaf nodes and 15 internal nodes.

0
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
depth 4 -------
depth 3 ----------
depth 2 ----------------
depth 1 ----------------------------
depth 0 ----------------------------------------------------
$2^3$
$2^2$
$2$
$1$
depth = 4
$2^3$
$2^2$
$2$
$1$
-1
-1
-1
-1

Saving...
Server Error
Resubmit

5.1.1.5. Delete the maximum value¶

0 / 0 Settings
<<<>>>

880
851
832
723
734
425
576
67
488
609
88
85
83
72
73
6
48
60
42
57

Saving...
Server Error
Resubmit

Contact Us || Privacy | | License « 4.4. Comparison :: Contents :: 5.2. Huffman Coding »