University of California, Santa Cruz

Prof. Paulo Franca - Spring 2000

Introduction

Syllabus

Guidelines for labs

Lab sections

Take quiz & check grades

Build Heap

running time:

bulletyou call heapify from each node i
bulletrunning time of heapify for a node whose subtree's height h is O(h)

example:

bullettree with 31 nodes
bullet16*O(0)+8*O(1)+4*O(2)+2*O(3)+1*O(4)
bullettree with 15 nodes:
bullet8 * O(0) + 4 * O(1) + 2 * O(2) + 1 * O(3)
bullettree with 7 nodes
bullet4*O(0)+2*O(1)+1*O(2)
bullettree with 3 nodes
bullet2*O(0) + 1 * O(1)

Notice that, as you increase one level (double N), the new running time will be doubled (since there will be two subtrees) plus O(h) where h is the new height.

T(h) = 2 * T( h-1) + O (h)

Book formula:

Summation for h=0 to floor(lg n)

ceiling ( n / ( 2 h+1 )) O(h)  ... =  n * Sum (  h / 2 h )

formula 3.6 in the book ->   O ( n Sum ( h / 2 h))    form h=0 to infinity

---> O (n)