Heap build analysis proof Slideshow

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.

depth 4 -------

depth 3 ----------

depth 2 ----------------

depth 1 ----------------------------

depth 0 ----------------------------------------------------

$2^3$

$2^2$

$2$

$1$

$2^3$

$2^2$

$2$

$1$

Proficient

Saving...

Error Saving

Server Error
Resubmit