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¶

1 / 6 Settings
<<<>>>

Here is the process for inserting a new record into a heap.

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¶

1 / 7 Settings
<<<>>>

Here is the process for removing the maximum value from the max heap. We know that this value is at the root (array position 0), but we also need to update the heap when we remove it.

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 »