Algorithms

and Data
Structures

(c) Marcin
Sydow

Priority
Queue
Algorithms and Data Structures
Example Priority Queue
Applications

Extensions of
Priority
Queue
(c) Marcin Sydow
Binomial
Heap

Summary
 Topics covered by this lecture:

Algorithms
and Data
Structures

(c) Marcin
Sydow

Priority Priority Queue

Queue
Naive Implementations
Example
Applications
Binary Heap
Extensions of
Priority HeapSort and other examples
Queue

Binomial Extended Priority Queues

Heap
(*) Binomial Heap
Summary
 Priority Queue Denition

Algorithms Priority Queue (PQ) is an abstract data structure supporting

and Data
Structures the following operations:
(c) Marcin
Sydow
insert(T e) // add to PQ a new element with assigned
Priority priority
Queue

Example
T ndMin() // return the element with minimum priority
Applications
T delMin() // return and delete the elt. with min. prior.
Extensions of
Priority (optional operation: construct(sequence<T> s) // create a PQ
Queue

Binomial
given set of elements)
Heap

Summary Each element has associated priority.

One can also consider a max-type priority queue, dened

analogously

Note: priority queue queue

is not a specialised

(why? hint: remember the denition of queue)

 Implementations of Priority Queue

Algorithms
and Data
Structures
The implementations evolve, for example:
(c) Marcin
Sydow

Priority naive (as an array or list)

Queue
Binary Heap (1964 Williams; Floyd 1964)
Example
Applications
Binomial Heap (1978 Vuillemin)
Extensions of
Priority Pairing Heap* (1986 Fredman, Sedgewick, Sleator, Tarjan;
Queue
2000 Iacono; Pettie 2005)
Binomial
Heap
Fibonacci Heap* (1987 Fredman, Tarjan)
Summary
Thin Heaps and Fat Heaps* (1999 Kaplan, Tarjan)

* - not in this lecture

 Naive implementations

Algorithms
and Data
Structures

(c) Marcin
Sydow

Priority
Queue
unsorted sequence:

Example insert: O(1), deleteMin: O(n), construct: O(n)

Applications
sorted sequence:
Extensions of
Priority insert: O(n), deleteMin: O(1): construct: O(n log(n))
Queue

Binomial
Heap
(sequence can be an array or linked list)
Summary
 Binary Heap

Algorithms
and Data
Structures
complete1 binary tree satisfying the following
Binary Heap is a

(c) Marcin
heap-order condition (for each (non-root) node x ):
Sydow

Priority
(priority of parent [x ]) ≤ (priority of x )
Queue

Example Observations:
Applications
minimum priority is at root
Extensions of
Priority
Queue
priorities on each path from the root to a leaf form a

Binomial non-decreasing sequence

Θ(log (n))
Heap
height of n-element binary heap is (due to
Summary
completeness)

(there is also a max variant of the above denition)

1
Leaves (except may be the right-most ones, that can be 1 level
higher), have equal depths
 Array Representation of Binary Heap

Algorithms
and Data
Structures

(c) Marcin
Sydow

Due to the fact that it is a complete binary tree, Binary Heap

Priority
Queue can be compactly represented as an array:
Example
Applications
Navigation:
Extensions of
Priority (assume the root is under index 1)
Queue

Binomial
parent [i ] == i /2 (for non-root i)
Heap

Summary
i .left == 2i , i .right == 2i + 1 (for non-leaf i)
 Restoring the Heap Order

Algorithms
and Data
Structures

(c) Marcin Two helper, internal operations.

Sydow
Both assume the heap order is correct except the position i:
Priority
Queue
upheap(i) (call when (key of parent[i] > key of i), assert:
Example
Applications heap ok below i): the key under i goes up until ok
Extensions of
Priority downheap(i) (call when one of children of i has lower key
Queue
than i, assert: heap ok above i and for both its subtrees):
Binomial
Heap the key under i goes down until ok
Summary

Both operations use O (log (n)) key comparisons (n - number of

elements)
 Upheap

Algorithms
and Data
Structures

(c) Marcin
Sydow
Example of upheap(i) implementation:
Priority
Queue upheap(i) // i > 0, heap ok under i
Example key = heap[i]
Applications parent = i/2
Extensions of while((parent > 0) && (heap[parent] > key))
Priority heap[i] = heap[parent]
Queue i = parent
Binomial parent /= 2
Heap heap[i] = key
Summary
 Downheap

Algorithms
and Data
Structures Example of downheap(i) implementation:
(c) Marcin
Sydow
downheap(i)
l = 2i // left son
Priority
r = 2i + 1 // right son
Queue if l <= n and heap[l] < heap[i]:
Example
min = l
Applications else:
min = i
Extensions of
Priority if r <= n and heap[r] < heap[min]: // n is the size of heap
Queue min = r
Binomial
if min != i:
Heap swap(i,min) // swap the elements under indexes (not indexes themse
Summary
downheap(min) // go down

Remarks: recursion used here only for keeping the code short,

swapping too. Both can be avoided to make the implementation

more ecient.
 Priority Queue implemented on Binary Heap

Algorithms
and Data
Structures

(c) Marcin (data size: number of elements (n), dom. oper.: comparison of
Sydow
priorities)

Priority
Queue
insert(x): add x to the bottom and upheap(bottom)

Example ( O (log (n)))

O (1))
Applications
ndMin(): return root (
Extensions of
Priority
Queue delMin(): move the bottom element to the root and

Binomial downheap(root) ( O (log (n)))

Heap

Summary
What is the complexity of construct?
 Priority Queue implemented on Binary Heap

Algorithms
and Data
Structures

(c) Marcin (data size: number of elements (n), dom. oper.: comparison of
Sydow
priorities)

Priority
Queue
insert(x): add x to the bottom and upheap(bottom)

Example ( O (log (n)))

O (1))
Applications
ndMin(): return root (
Extensions of
Priority
Queue delMin(): move the bottom element to the root and

Binomial downheap(root) ( O (log (n)))

Heap

Summary
What is the complexity of construct?

Interestingly, construct has fast, Θ(n) implementation.

 Complexity of construct

Algorithms
and Data

n × insert Θ(nlog (n))))

Structures
(naive: (which gives
(c) Marcin
Sydow faster way:

Priority
Queue
for(i = n/2; i > 0; i--) downHeap(i)
Example
Analysis: downHeap is called at most 2
d times for nodes of
Applications

Extensions of
Priority
depth d , each such call costs O (h − d ) (where h is the height
Queue of heap). Thus, the total cost is:
Binomial
Heap
h−d j
O( d
(h−d )) = O (2h ) = O (2h ) = O (n)
X X X
2
2 h −d 2j
Summary

0≤d <h 0≤d <h j ≥1

i −i
P
(the last equation holds because: i ≥1 2 = 2)
 ≥1 i 2 = 2: a proof
−i
P
i

n
q i = 11−−qq q 6= 1
Algorithms
Pn−1
and Data nite geometric series: i =0 for
Structures

(c) Marcin innite geometric series:

n
q i = limn→∞ 11−−qq ≤q<1
Sydow
1
P
i ≥0 = 1−q
for 0
Priority
Queue
Thus:
Example −i
P
Applications i ≥0 2 = 1 + 1/2 + 1/4 + ... = 2 (a geometric series with q = 1/2)
Extensions of
Priority 2
Queue Now:

Binomial
i 2−i = −i −i −i
X X X X
Heap 2 + 2 + 2 +... = (1+1/2+1/4+...) = 2
Summary
i ≥1 i ≥1 i ≥2 i ≥3

(the rst equality is due to the re-grouping of terms (2

−i occurs

in exactly i rst sums))

2
More generally,
P
k ≥0 kx k = (1−xx )2 , for any |x | < 1 (take derivative of
innite geometric series to obtain it)
 Example: HeapSort

Algorithms
and Data
Structures How to sort a sequence s with a Priority Queue?
(c) Marcin
Sydow

Priority
Queue

Example
Applications

Extensions of
Priority
Queue

Binomial
Heap

Summary
 Example: HeapSort

Algorithms
and Data
Structures How to sort a sequence s with a Priority Queue?
(c) Marcin (pq is an object representing priority queue)
Sydow

Priority while(s.hasNext())
Queue

Example
pq.insert(s.next())
Applications

Extensions of
Priority
while(!pq.isEmpty())
Queue result.add(pq.delMin())
Binomial
Heap
data size: # elements (n), dom. op.: comparison
Summary
time complexity: Θ(nlog (n)), space complexity: Θ(n)

Notice: if we put the min element to the last released place in

the array, we obtain O (1) space complexity!
 Other examples of applications of priority queues

Algorithms
and Data
Structures

(c) Marcin
Sydow
Priority queues are typically used in greedy algorithms (for
Priority selecting a next element in the solution in the ecient way), for
Queue
example:
Example
Applications

Extensions of
Human Code computation
Priority
Queue
Dijkstra's shortest-path algorithm (on other lecture)
Binomial
Heap Prim's minimum spanning tree algorithm (on other lecture)
Summary
etc.
 Extensions of Priority Queue

Algorithms
and Data
Structures
Addressable Priority Queue
(c) Marcin
Sydow

construct(sequence<T> s)
Priority
Queue
H insert(T e) // as before but returns a handle to the inserted element
Example
Applications T ndMin()
Extensions of
Priority T delMin()
Queue
decreaseKey(H pointer, T newPriority)
Binomial
Heap
delete (H pointer)
Summary

In addition: Mergeable Priority Queue:

merge(PQ priorityQueue1, PQ priorityQueue2)

 Complexities of Priority Queue Operations

Algorithms
and Data
Structures

(c) Marcin
operation unsort. sort. binary heap binomial heap
Sydow
insert 1 n lg n lg n

Priority ndMin n 1 1 lg n
Queue
delMin n 1 lg n lg n
Example
Applications decreaseKey 1 n lg n lg n

Extensions of delete 1 n lg n lg n
Priority
Queue merge 1 n n lg n
Binomial (the entries have implicit O (.) around them)
Heap

Summary Binomial Heap: a bit more advanced implementation of priority

queue that supports fast merge (and keeps other operations
fast)
 Binomial Trees

Algorithms
and Data A binomial tree Bi of degree i is a rooted tree dened
Structures
recursively as follows:

B0 consists of a single node

(c) Marcin
Sydow

Priority Bi : the root has i sons: Bi −1 , Bi −2 , ..., B0 (in such order)

Queue

Example
Applications Properties of Bi :
Extensions of
Priority
height: i
i

Queue

Binomial
has exactly
j (binomial coecient) nodes at level j
Heap

Summary i
has exactly 2 nodes in total

can be obtained by adding a Bi −1 as a left-most son of a

root of a Bi −1
(Notice the analogies with the properties of binomial
coecients!)
 Binomial Heap

Algorithms
and Data
Structures

(c) Marcin Binomial Heap is a list of binomial trees sorted decreasingly by

Sydow
degrees (from left to right), where each binomial tree satises
Priority
Queue
the heap order.
Example
Applications Properties of a n-element binomial heap:
Extensions of
Priority
it consists of O (logn) binomial trees
Queue
Bi is its part only if the i − th bit in the binary
representation of n is set to 1
Binomial
Heap

Summary

(both properties are implied by the fact that |Bi | == 2i and

properties of binary representation of numbers)
 Operations on Binomial Heap

Algorithms
and Data ndMin: min is among the O (logn) roots
Structures
merge: similar to adding two binary numbers. Summing
(c) Marcin
Sydow two 'ones' on position i : merging two binomial trees Bi to

Priority
obtain one Bi +1 (remind the last property of binomial
Queue trees). The tree with lower key becomes the root, the
Example other becomes its right-most son. The summing goes
Applications
through both lists of binomial trees from left to right (thus
Extensions of
Priority
Queue
it has O (logn) complexity)
Binomial
insert: merge with a 1-element binomial heap ( O (logn))
Heap
delMin: nd the root with the lowest key ( O (logn)), cut it
Summary
out, merge the list of its sons (being a correct binomial
heap itself !) with the rest of the remaining part ( O (logn))
decreaseKey: similarly as in binary heap ( O (logn))
delete: move it to the root, cut, then as in delMin
( O (logn))
 Questions/Problems:

Algorithms
and Data
Structures

(c) Marcin Denition of Priority Queue

Sydow
Complexities on naive implementation (list, array)
Priority
Queue Binary Heap denition
Example Binary Heap represented as Array
Applications

Extensions of Priority Queue operations on Binary Heap (+ complexities)

Priority
Queue HeapSort and other examples of applications
Binomial
Heap Extended Priority Queues (operations)
Summary (*) Binomial Trees and Binomial Heap

(*) Priority Queue implemented on Binomial Heap

(operations + complexities)
 Algorithms
and Data
Structures

(c) Marcin
Sydow

Priority
Queue

Example
Applications
Thank you for your attention
Extensions of
Priority
Queue

Binomial
Heap

Summary