Calculating the big O of a priority queue insert

A PriorityQueue is a tree-like structure where the nodes are ordered according to a Comparator function, eg. the lower the value of the node the  higher up it will be in the tree, with the root node being the node with the minimum value.

priority queue

New elements are originally inserted at the bottom of the tree then “sift up” to their appropriate position in the tree. Each sift up operation compares the value of the node to the value of its parent, and if the value of the node is smaller then both nodes are swapped.

Cost of the insert operation is then function to the number of sift up operations to execute…which will be function of the height of the tree.

priority queue height


How high is the tree then ?  I
n a balanced binary tree each parent will have  two children nodes, so:

at level 1, total number of nodes N= 1(root node)
at level 2, N= the root node’s two children + the root node = 2*1 + 1 = 3 nodes in total
at level 3, N= 2*2 + 2*1 +1 = 7
at level 4, N= 2*2*2 + 2*2 + 2*1 + 1 = 15
….
at level h, N= sum of (2^i) where i runs from 0 to h

The above is a geometric serie with first term 2,  ratio 2 and h terms , which can be calculated as: N = 2^(h+1)-1

Finally from the inverse relationship between logs and exponentials:
log_2(N) = h+1

… and the big O of an insert in a priority queue is log(N)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s