Tag Archives: algorithm

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)