Priority Queues: Operations and Implementations
Priority Queues
MakeQueue
create new empty queue
Insert(
Q
,
k
,
p
)
insert key
k
with priority
p
Delete(Q,
k
)
delete key
k
(given a pointer)
DeleteMin(Q)
delete key with min priority
Meld(
Q
1
,
Q
2
)
merge two sets
Empty(
Q
)
returns if empty
Size(
Q
)
returns #keys
FindMin(
Q
)
returns key with min priority
1
Priority Queues – Ideal Times
MakeQueue,
Meld
,
Insert
, Empty, Size, FindMin:
O
(1)
Delete, DeleteMin:
O
(log
n
)
Thm
1)
Meld
O
(
n
1-
ε
)
DeleteMin
Ω
(log
n
)
2)
Insert, Delete
O
(
t
)
FindMin
Ω
(
n
/2
O
(
t
)
)
1)
Follows from
Ω
(
n
∙log
n
) sorting lower bound
2)
[G.S. Brodal, S. Chaudhuri, J. Radhakrishnan,
The Randomized Complexity of Maintaining the Minimum.
In Proc. 5th Scandinavian
Workshop on Algorithm Theory, volume 1097 of Lecture Notes in Computer Science, pages 4-15. Springer Verlag, Berlin, 1996]
2
Binomial Queues
Binomial
tree
–
each node stores a (
k
,
p
) and satisfies
heap order
with respect to priorities
–
all nodes have a
rank
r
(leaf = rank 0, a rank
r
node
has exactly one child of each of the ranks 0..
r
-1)
Binomial
queue
–
forest of binomial trees with roots stored in a list
with strictly increasing root ranks
[Jean Vuillemin,
A data structure for manipulating priority queues,
Communications of the ACM archive, Volume 21(4), 309-315, 1978]
8
2
9
7
3
8
5
5
4
7
6
0
1
2
3
1
1
0
0
0
0
0
3
Problem
Implement binomial queue operations to achieve
the ideal times in the
amortized
sense
Hints
1)
Two rank
i
trees can be linked to create a rank
i
+1 tree in
O
(1) time
2)
Potential
Φ
= max rank + #roots
4
Dijkstra’s Algorithm
(Single source shortest path problem)
n
x
Insert
+
n
x
DeleteMin
+
m
x
DecreaseKey
Binary heaps / Binomial queues : O((
n
+
m
)∙log
n
)
Algorithm
Dijkstra(
V
,
E
,
w
,
s
)
Q
:= MakeQueue
dist[
s
] := 0
Insert
(
Q
,
s
, 0)
for
v
V
\ { s
}
do
dist[
v
] := +∞
Insert
(
Q
,
v
, +∞)
while
Q
≠
do
v
:=
DeleteMin
(
Q
)
foreach
u
: (
v
,
u
)
E
do
if
u
Q
and
dist[
v
]+
w
(
v
,
u
) < dist[
u
]
then
dist[
u
] := dist[v]+
w
(
v
,
u
)
DecreaseKey
(
u
, dist[
u
])
5
Priority Bounds
Empty, FindMin, Size, MakeQueue – O(1) worst-case time
Amortized
Worst-case
(and Minimum Spanning Tree O(
m
∙log*
n
))
6
Fibonacci Heaps
F-tree
–
heap order
with respect to priorities
–
all nodes have a
rank
r
{degree, degree + 1}
(
r
= degree + 1
node is
marked
as having lost a child)
–
The
i
’th child
of a node from the right has
rank
≥
i
- 1
Fibonacci Heap
–
forest (list) of F-trees (trees can have equal rank)
[Fredman, Tarjan,
Fibonacci Heaps and Their Use in Improved Network Algorithms,
Journal of the ACM, Volume 34(3), 596-615, 1987]
7
Proof
A rank
r
node has at least 2 children of rank
≥
r
– 3. By induction subtree size is at least 2└
r/3
┘
□
( in fact the size is at least
r
, where
=(1+
5)/2
)
Fibonnaci Heap Property
Thm
Max rank of a node in an F-tree is O(log
n
)
8
Hints
1)
Two rank
i
trees can be linked to create a rank
i
+1 tree in
O
(1) time
2)
Eliminating nodes violating order or nodes having
lost two children
3)
Potential
Φ
= 2∙marks + #roots
Problem
Implement Fibonacci Heap operations with
amortized
O(1)
time for all operations, except O(log
n
) for deletions
9
Implementation of
Fibonacci Heap Operations
FindMin
Maintain pointer to min root
Insert
Create new tree = new rank 0 node
+1
Join
Concatenate two forests
unchanged
Delete
DecreaseKey -∞ + DeleteMin
DeleteMin
Remove min root
-1
+ add children to forest
+O(log
n
)
+ bucketsort roots by rank
only O(log
n
) not linked below
+ link while two roots equal rank
-1 each
DecreaseKey
Update priority + cut edge to parent
+3
+ if parent now has
r
– 2 children,
recursively cut parent edges
-1 each, +1 final cut
*
= potential change
10
Worst-Case Operations
(without Join)
Basic ideas
Require ≤ max-rank + 1
trees
in forest
(otherwise
rank r where two trees can be linked
)
Replace cutting in F-trees by having O(log n) nodes
violating heap order
Transformation
replacing two rank
r
violations by
one rank
r
+1 violation
[Driscoll, Gabow, Shrairman, Tarjan,
Relaxed Heaps: An Alternative to Fibonacci Heaps with Applications to Parallel Computation,
Communications of the ACM, Volume 34(3), 596-615, 1987]
11
Question: What implementations do you know (search tree, unordered list, binary heaps) – what will the time be for these?
Priority queues are data structures that allow efficient insertion, deletion, and retrieval of elements based on their priority. This information-rich content covers various aspects of priority queues, including ideal times, binomial queues, Dijkstra's algorithm for single-source shortest paths, and run-relaxed heaps. It discusses key operations such as insertion, deletion, finding the minimum, merging sets, and more. Implementations like binary heaps and binomial queues are explored to achieve optimal time complexities for priority queue operations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Priority Queues MakeQueue Insert(Q,k,p) Delete(Q,k) DeleteMin(Q) Meld(Q1,Q2) Empty(Q) Size(Q) FindMin(Q) create new empty queue insert key k with priority p delete key k (given a pointer) delete key with min priority merge two sets returns if empty returns #keys returns key with min priority 1
Priority Queues Ideal Times MakeQueue, Meld, Insert, Empty, Size, FindMin: O(1) Delete, DeleteMin: O(log n) Thm 1)Meld O(n1- ) DeleteMin (log n) 2) Insert, Delete O(t) FindMin (n/2O(t)) 1) 2) [G.S. Brodal, S. Chaudhuri, J. Radhakrishnan,The Randomized Complexity of Maintaining the Minimum. In Proc. 5th Scandinavian Workshop on Algorithm Theory, volume 1097 of Lecture Notes in Computer Science, pages 4-15. Springer Verlag, Berlin, 1996] Follows from (n log n) sorting lower bound 2
0 3 1 3 2 9 2 0 0 1 Binomial Queues 4 5 7 8 1 0 0 [Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM archive, Volume 21(4), 309-315, 1978] 6 5 8 0 7 Binomial tree each node stores a (k,p) and satisfies heap order with respect to priorities all nodes have a rank r (leaf = rank 0, a rank r node has exactly one child of each of the ranks 0..r-1) Binomial queue forest of binomial trees with roots stored in a list with strictly increasing root ranks 3
Problem Implement binomial queue operations to achieve the ideal times in the amortized sense Hints 1) Two rank i trees can be linked to create a rank i+1 tree in O(1) time r r link x y r+1 r y x y x 2) Potential = max rank + #roots 4
Dijkstras Algorithm (Single source shortest path problem) Algorithm Dijkstra(V, E, w, s) Q := MakeQueue dist[s] := 0 Insert(Q, s, 0) for v V \ { s } do dist[v] := + Insert(Q, v, + ) while Q do v := DeleteMin(Q) foreach u : (v, u) E do if u Q and dist[v]+w(v, u) < dist[u] then dist[u] := dist[v]+w(v, u) DecreaseKey(u, dist[u]) n x Insert + n x DeleteMin + m x DecreaseKey Binary heaps / Binomial queues : O((n + m) log n) 5
Priority Bounds Run-Relaxed Heaps [Driscoll, Gabow, Shrairman, Tarjan 88] 1 [Brodal 96] [Brodal, Lagogiannis, Tarjan 12] Binomial Queues [Vuillemin 78] 1 Fibonacci Heaps [Fredman, Tarjan 84] 1 Insert 1 Meld 1 1 - 1 Delete DeleteMin log n log n log n log n log n log n log n log n DecreaseKey log n 1 1 1 Amortized Worst-case Dijkstra s Algorithm O(m + n log n) (and Minimum Spanning Tree O(m log* n)) 6 Empty, FindMin, Size, MakeQueue O(1) worst-case time
Fibonacci Heaps [Fredman, Tarjan, Fibonacci Heaps and Their Use in Improved Network Algorithms, Journal of the ACM, Volume 34(3), 596-615, 1987] 3 3 2 0 4 7 1 0 6 5 F-tree heap order with respect to priorities all nodes have a rank r {degree, degree + 1} (r = degree + 1 node is marked as having lost a child) The i th child of a node from the right has rank i - 1 Fibonacci Heap forest (list) of F-trees (trees can have equal rank) 0 7 7
Fibonnaci Heap Property Thm Max rank of a node in an F-tree is O(log n) Proof r 3. By induction subtree size is at least 2 r/3 A rank r node has at least 2 children of rank ( in fact the size is at least r, where =(1+ 5)/2 ) 8
Problem Implement Fibonacci Heap operations with amortized O(1) time for all operations, except O(log n) for deletions Hints 1) Two rank i trees can be linked to create a rank i+1 tree in O(1) time r+1 r r link x y r y x y x 2) Eliminating nodes violating order or nodes having lost two children y y d x r cut degree(x) = d r-2 x 3) Potential = 2 marks + #roots 9
Implementation of Fibonacci Heap Operations FindMin Insert Join Delete DeleteMin Maintain pointer to min root Create new tree = new rank 0 node +1 Concatenate two forestsunchanged DecreaseKey - + DeleteMin Remove min root-1 + add children to forest+O(log n ) + bucketsort roots by rankonly O(log n ) not linked below + link while two roots equal rank-1 each Update priority + cut edge to parent+3 + if parent now has r 2 children, recursively cut parent edges-1 each, +1 final cut DecreaseKey * = potential change 10
Worst-Case Operations (without Join) [Driscoll, Gabow, Shrairman, Tarjan, Relaxed Heaps: An Alternative to Fibonacci Heaps with Applications to Parallel Computation, Communications of the ACM, Volume 34(3), 596-615, 1987] Basic ideas Require max-rank + 1 trees in forest (otherwise rank r where two trees can be linked) Replace cutting in F-trees by having O(log n) nodes violating heap order Transformation replacing two rank r violations by one rank r+1 violation 11
