Priority Queues and Heaps
Priority Queues and Heaps
October 2004
John Edgar
2
A queue should implement at least the first
two of these operations:
insert
– insert item at the back of the queue
remove
– remove an item from the front
peek
– return the item at the front of the queue
without removing it
I
t is assumed that these operations will be
implemented efficiently
That is, in constant time
Either with an array
Or with a linked list
October 2004
John Edgar
3
Queues are first-in first-out (FIFO)
Priority queues are a fancier type of queue
Maintains an ordering of items in the queue, not
necessarily first-in first-out
October 2004
John Edgar
4
September 2004
John Edgar
5
Items in a priority queue are given a priority
value
Which could be numerical or something else
The highest priority item is removed first
Uses include
System requests
Data structure to support Dijkstra’s Algorithm
September 2004
John Edgar
6
Can items be inserted and removed
efficiently
from a priority queue?
Using an array, or
Using a linked list?
Note that items are not removed based on
the order in which they are inserted
September 2004
John Edgar
7
Now we’ll see how we can do these efficiently
(using a different data structure)
Items in a priority queue have a
priority
Not necessarily numerical
Could be lowest first or highest first
The highest priority item is removed first
Priority queue operations
Insert
Remove in priority queue order
▪
Both operations should be performed in at most
O
(log
n
) time
October 2004
John Edgar
8
September 2004
John Edgar
9
Items have to be removed in priority order
This can only be done efficiently if the items are ordered in
some way
One option would be to use a balanced binary
search tree
Binary search trees are fully ordered and insertion and
removal can be implemented in
O
(log
n
) time
▪
Some operations (e.g. removal) are complex
▪
Although operations are
O
(log
n
) they require quite a lot of
structural overhead
There is a much simpler binary tree solution
October 2004
John Edgar
10
A
heap
is binary tree with two properties
Heaps are
complete
All levels, except the bottom, are completely filled in
The leaves on the bottom level are as far to the left as
possible.
Heaps are
partially ordered
The value of a node is at least as large as its children’s
values, for a
max
heap or
The value of a node is no greater than its children’s values,
for a
min
heap
October 2004
John Edgar
11
October 2004
John Edgar
12
complete binary trees
incomplete binary trees
October 2004
John Edgar
13
H
e
a
p
s
a
r
e
n
o
t
f
u
l
l
y
o
r
d
e
r
e
d
,
a
n
i
n
o
r
d
e
r
t
r
a
v
e
r
s
a
l
w
o
u
l
d
r
e
s
u
l
t
i
n
:
9
,
1
3
,
1
0
,
8
6
,
4
4
,
6
5
,
2
3
,
9
8
,
2
1
,
3
2
,
1
7
,
4
1
,
2
9
A heap can implement a priority queue
The item at the top of the heap must always be the
highest priority value
Because of the partial ordering property
Implement priority queue operations:
Insertions – insert an item into a heap
Removal – remove and return the heap’s root
For both operations preserve the heap property
October 2004
John Edgar
14
September 2004
John Edgar
15
Heaps can be implemented
using
arrays
There is a natural method of
indexing tree nodes
Index nodes from top to bottom
and left to right as shown on the
right
Because heaps are
complete
binary trees there can be no
gaps in the array
October 2004
John Edgar
16
0
1
2
3
4
5
6
It will be necessary to find the index of the
parents of a node
Or the children of a node
The array is indexed from 0 to
n
– 1
Each level's nodes are indexed from:
▪
2
level
– 1 to 2
level+1
– 2 (where the root is level 0)
The children of a node
i
, are the array elements
indexed at 2
i
+ 1 and 2
i
+ 2
The parent of a node
i
, is the array element
indexed at floor((
i
– 1) / 2)
October 2004
John Edgar
17
October 2004
John Edgar
18
Heap
0
1
2
3
5
4
6
7
8
9
10
11
12
September 2004
John Edgar
19
On insertion the heap properties have to be
maintained; remember that
A heap is a complete binary tree and
A partially ordered binary tree
There are two general strategies that could be used
to maintain the heap properties
Make sure that the tree is complete and then fix the
ordering or
Make sure the ordering is correct first
Which is better?
October 2004
John Edgar
20
The insertion algorithm first ensures that the tree is
complete
Make the new item the first available (left-most) leaf on
the bottom level
i.e. the first free element in the underlying array
Fix the partial ordering
Compare the new value to its parent
Swap them if the new value is greater than the parent
Repeat until this is not the case
▪
Referred to as
bubbling up
, or
trickling up
October 2004
John Edgar
21
October 2004
John Edgar
22
I
n
s
e
r
t
8
1
October 2004
John Edgar
23
Insert 81
(13-1)/2 = 6
8
1
i
s
l
e
s
s
t
h
a
n
9
8
s
o
f
i
n
i
s
h
e
d
September 2004
John Edgar
24
Make a temporary copy of the root’s data
Similarly to the insertion algorithm, first ensure that
the heap remains complete
Replace the root node with the right-most leaf
i.e. the highest (occupied) index in the array
Swap the new root with its largest valued child until
the partially ordered property holds
i.e.
bubble down
Return the root’s data
October 2004
John Edgar
25
October 2004
John Edgar
26
R
e
m
o
v
e
(
r
o
o
t
)
October 2004
John Edgar
27
Remove (root)
r
e
p
l
a
c
e
r
o
o
t
w
i
t
h
r
i
g
h
t
-
m
o
s
t
l
e
a
f
October 2004
John Edgar
28
Remove (root)
swap with larger child
October 2004
John Edgar
29
Remove (root)
swap with larger child
October 2004
John Edgar
30
Remove (root)
swap with larger child
September 2004
John Edgar
31
Helper functions are usually written for preserving
the heap property
bubbleUp
ensures that the heap property is preserved from
the start node up to the root
bubbleDown
ensures that the heap property is preserved
from the start node down to the leaves
These functions may be implemented recursively or
iteratively
October 2004
John Edgar
32
Go to terminal
October 2004
John Edgar
33
October 2004
John Edgar
34
October 2004
John Edgar
35
Lab next week
Lab next week
October 2004
John Edgar
36
For both insertion and removal the heap performs
at most
height
swaps
For insertion at most
height
comparisons
▪
To bubble up the array
For removal at most
height
* 2 comparisons
▪
To bubble down the array (have to compare two children)
Height of a complete binary tree is
log
2
(
n
)
Both insertion and removal are therefore
O
(log
n
)
October 2004
John Edgar
37
September 2004
John Edgar
38
Observation 1
: Removal of a node from a heap can
be performed in
O
(log
n
) time
Observation 2
: Nodes are removed in order
Conclusion
: Removing all of the nodes one by one
would result in sorted output
Analysis
: Removal of
all
the nodes from a heap is a
O
(
n
*log
n
) operation
October 2004
John Edgar
39
A
h
e
a
p
c
a
n
b
e
u
s
e
d
t
o
r
e
t
u
r
n
s
o
r
t
e
d
d
a
t
a
I
n
O
(
n
*
l
o
g
n
)
t
i
m
e
H
o
w
e
v
e
r
,
w
e
c
a
n
’
t
a
s
s
u
m
e
t
h
a
t
t
h
e
d
a
t
a
t
o
b
e
s
o
r
t
e
d
j
u
s
t
h
a
p
p
e
n
s
t
o
b
e
i
n
a
h
e
a
p
!
A
h
a
!
B
u
t
w
e
c
a
n
p
u
t
i
t
i
n
a
h
e
a
p
.
I
n
s
e
r
t
i
n
g
a
n
i
t
e
m
i
n
t
o
a
h
e
a
p
i
s
a
O
(
l
o
g
n
)
o
p
e
r
a
t
i
o
n
s
o
i
n
s
e
r
t
i
n
g
n
i
t
e
m
s
i
s
O
(
n
*
l
o
g
n
)
B
u
t
w
e
c
a
n
d
o
b
e
t
t
e
r
t
h
a
n
j
u
s
t
r
e
p
e
a
t
e
d
l
y
c
a
l
l
i
n
g
t
h
e
i
n
s
e
r
t
i
o
n
a
l
g
o
r
i
t
h
m
October 2004
John Edgar
40
To create a heap from an unordered array
repeatedly call
bubbleDown
Any subtree in a heap is itself a heap
Call
bubbleDown
on elements in the upper ½ of the array
Start with index
n
/2 and work up to index 0
▪
i.e. from the last non-leaf node to the root
bubbleDown
does not need to be called on the lower
half of the array (the leaves)
Since
bubbleDown
restores the partial ordering from any
given node down to the leaves
October 2004
John Edgar
41
October 2004
John Edgar
42
27
70
13
76
37
42
58
Assume unsorted input is contained in
an array as shown here (indexed from
top to bottom and left to right)
0
1
2
3
5
4
6
7
8
9
10
11
12
October 2004
John Edgar
43
13
0
1
2
3
5
4
6
7
8
9
10
11
12
n = 12, (n-1)/2 = 5
bubbleDown(5)
October 2004
John Edgar
44
13
0
1
2
3
5
4
6
7
8
9
10
11
12
bubbleDown(5)
bubbleDown(4)
n = 12, (n-1)/2 = 5
October 2004
John Edgar
45
13
0
1
2
3
5
4
6
7
8
9
10
11
12
bubbleDown(5)
bubbleDown(4)
bubbleDown(3)
n = 12, (n-1)/2 = 5
October 2004
John Edgar
46
0
1
2
3
5
4
6
7
8
9
10
11
12
bubbleDown(5)
bubbleDown(4)
bubbleDown(3)
bubbleDown(2)
n = 12, (n-1)/2 = 5
October 2004
John Edgar
47
13
0
1
2
3
5
4
6
7
8
9
10
11
12
bubbleDown(5)
bubbleDown(4)
bubbleDown(3)
bubbleDown(2)
bubbleDown(1)
n = 12, (n-1)/2 = 5
October 2004
John Edgar
48
13
0
1
2
3
5
4
6
7
8
9
10
11
12
bubbleDown(5)
bubbleDown(4)
bubbleDown(3)
bubbleDown(2)
bubbleDown(1)
bubbleDown(0)
n = 12, (n-1)/2 = 5
bubbleDown
is called on half the array
The cost for
bubbleDown
is
O
(
height
)
It would appear that heapify cost is
O
(
n
*log
n
)
In fact the cost is
O
(
n
)
The analysis is complex but
bubbleDown
is only called on n/2 nodes
and mostly on sub-trees
October 2004
John Edgar
49
Heapify the array
Repeatedly remove the root
After each removal swap the root with the last element in
the tree
The array is divided into a heap part and a sorted part
At the end of the sort the array will be sorted in
reverse order
October 2004
John Edgar
50
The algorithm runs in
O
(
n
*log
n
) time
Considerably more efficient than selection sort
and insertion sort
The same average case complexity as MergeSort
and QuickSort
The sort can be carried out
in-place
That is, it does not require that a copy of the array
to be made
October 2004
John Edgar
51
September 2004
John Edgar
52
Define the ADT priority queue
Define the partially ordered property
Define a heap
Implement a heap using an array
Implement the heapSort algorithm
October 2004
John Edgar
53
Java Ch. 12
C++ Ch. 11
October 2004
John Edgar
54
Priority queues differ from regular queues by maintaining an ordering of items based on priority rather than first-in-first-out. Items in a priority queue are assigned priority values and the highest priority item is removed first. Different data structures can be used to efficiently insert and remove items from a priority queue while ensuring operations are performed in a timely manner.
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
A queue should implement at least the first two of these operations: insert insert item at the back of the queue remove remove an item from the front peek return the item at the front of the queue without removing it It is assumed that these operations will be implemented efficiently That is, in constant time October 2004 John Edgar 2
4 0 18 25 1 2 3 5 4 Either with an array 2 5 6 7 6 front back 4 Or with a linked list 7 3 October 2004 John Edgar 3
Queues are first-in first-out (FIFO) Priority queues are a fancier type of queue Maintains an ordering of items in the queue, not necessarily first-in first-out October 2004 John Edgar 4
4 5 1 2 6 3 September 2004 John Edgar 5
Items in a priority queue are given a priority value Which could be numerical or something else The highest priority item is removed first Uses include System requests Data structure to support Dijkstra s Algorithm September 2004 John Edgar 6
Can items be inserted and removed efficiently from a priority queue? Using an array, or Using a linked list? Note that items are not removed based on the order in which they are inserted Now we ll see how we can do these efficiently (using a different data structure) September 2004 John Edgar 7
Items in a priority queue have a priority Not necessarily numerical Could be lowest first or highest first The highest priority item is removed first Priority queue operations Insert Remove in priority queue order Both operations should be performed in at most O(log n) time October 2004 John Edgar 8
September 2004 John Edgar 9
Items have to be removed in priority order This can only be done efficiently if the items are ordered in some way One option would be to use a balanced binary search tree Binary search trees are fully ordered and insertion and removal can be implemented in O(log n) time Some operations (e.g. removal) are complex Although operations are O(logn) they require quite a lot of structural overhead There is a much simpler binary tree solution October 2004 John Edgar 10
A heap is binary tree with two properties Heaps are complete All levels, except the bottom, are completely filled in The leaves on the bottom level are as far to the left as possible. Heaps are partially ordered The value of a node is at least as large as its children s values, for a maxheap or The value of a node is no greater than its children s values, for a minheap October 2004 John Edgar 11
complete binary trees incomplete binary trees October 2004 John Edgar 12
98 86 41 13 65 32 29 9 10 44 23 21 17 Heaps are not fully ordered, an inorder traversal would result in: 9, 13, 10, 86, 44, 65, 23, 98, 21, 32, 17, 41, 29 October 2004 John Edgar 13
A heap can implement a priority queue The item at the top of the heap must always be the highest priority value Because of the partial ordering property Implement priority queue operations: Insertions insert an item into a heap Removal remove and return the heap s root For both operations preserve the heap property October 2004 John Edgar 14
September 2004 John Edgar 15
Heaps can be implemented using arrays There is a natural method of indexing tree nodes Index nodes from top to bottom and left to right as shown on the right Because heaps are complete binary trees there can be no gaps in the array 0 2 1 3 4 5 6 October 2004 John Edgar 16
It will be necessary to find the index of the parents of a node Or the children of a node The array is indexed from 0 to n 1 Each level's nodes are indexed from: 2level 1 to 2level+1 2 (where the root is level 0) The children of a node i, are the array elements indexed at 2i + 1 and 2i+ 2 The parent of a node i, is the array element indexed at floor((i 1) / 2) October 2004 John Edgar 17
0 98 1 2 86 41 Heap 3 4 5 6 13 65 32 29 7 8 9 10 11 12 9 10 44 23 21 17 index 0 1 2 3 4 5 6 7 8 9 10 11 12 value 98 86 41 13 65 32 29 9 10 44 23 21 17 Underlying Array October 2004 John Edgar 18
September 2004 John Edgar 19
On insertion the heap properties have to be maintained; remember that A heap is a complete binary tree and A partially ordered binary tree There are two general strategies that could be used to maintain the heap properties Make sure that the tree is complete and then fix the ordering or Make sure the ordering is correct first Which is better? October 2004 John Edgar 20
The insertion algorithm first ensures that the tree is complete Make the new item the first available (left-most) leaf on the bottom level i.e. the first free element in the underlying array Fix the partial ordering Compare the new value to its parent Swap them if the new value is greater than the parent Repeat until this is not the case Referred to as bubbling up, or trickling up October 2004 John Edgar 21
Insert 81 98 86 41 13 65 32 29 9 10 44 23 21 17 index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 value 98 86 41 13 65 32 29 9 10 44 23 21 17 October 2004 John Edgar 22
81 is less than 98 so finished Insert 81 98 41 81 86 13 65 32 29 81 41 9 10 44 23 21 17 81 29 (13-1)/2 = 6 index index index index 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 10 11 10 11 10 11 10 11 12 12 12 12 13 13 13 13 value value value value 98 86 41 98 86 41 98 86 41 98 86 81 13 13 13 13 65 32 29 65 32 29 65 32 81 65 32 41 9 9 9 9 10 44 23 21 10 44 23 21 10 44 23 21 10 44 23 21 17 17 17 17 81 29 29 October 2004 John Edgar 23
September 2004 John Edgar 24
Make a temporary copy of the roots data Similarly to the insertion algorithm, first ensure that the heap remains complete Replace the root node with the right-most leaf i.e. the highest (occupied) index in the array Swap the new root with its largest valued child until the partially ordered property holds i.e. bubble down Return the root s data October 2004 John Edgar 25
Remove (root) 98 86 41 13 65 32 29 9 10 44 23 21 17 index 0 1 2 3 4 5 6 7 8 9 10 11 12 value 98 86 41 13 65 32 29 9 10 44 23 21 17 October 2004 John Edgar 26
replace root with right-most leaf Remove (root) 98 17 86 41 13 65 32 29 9 10 44 23 21 17 index index 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 value value 98 86 17 86 41 41 13 13 65 65 32 32 29 29 9 9 10 10 44 44 23 23 21 21 17 October 2004 John Edgar 27
? ? swap with larger child Remove (root) 17 86 86 17 41 13 65 32 29 9 10 44 23 21 index index 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 value value 17 86 86 17 41 41 13 13 65 65 32 32 29 29 9 9 10 10 44 44 23 23 21 21 children of root: 2*0+1, 2*0+2 = 1, 2 October 2004 John Edgar 28
swap with larger child Remove (root) 86 ? ? 17 65 41 13 65 17 32 29 9 10 44 23 21 index index 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 value value 86 86 65 17 41 41 13 13 65 17 32 32 29 29 9 9 10 10 44 44 23 23 21 21 children of 1: 2*1+1, 2*1+2 = 3, 4 October 2004 John Edgar 29
swap with larger child Remove (root) 86 65 41 13 17 44 32 29 ? ? 9 10 44 17 23 21 index index 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 value value 86 65 86 65 41 41 13 13 17 44 32 32 29 29 9 9 10 10 44 17 23 23 21 21 children of 4: 2*4+1, 2*4+2 = 9, 10 October 2004 John Edgar 30
September 2004 John Edgar 31
Helper functions are usually written for preserving the heap property bubbleUp ensures that the heap property is preserved from the start node up to the root bubbleDown ensures that the heap property is preserved from the start node down to the leaves These functions may be implemented recursively or iteratively October 2004 John Edgar 32
Go to terminal October 2004 John Edgar 33
October 2004 John Edgar 34
Lab next week October 2004 John Edgar 35
Lab next week October 2004 John Edgar 36
For both insertion and removal the heap performs at most height swaps For insertion at most height comparisons To bubble up the array For removal at most height* 2 comparisons To bubble down the array (have to compare two children) Height of a complete binary tree is log2(n) Both insertion and removal are therefore O(logn) October 2004 John Edgar 37
September 2004 John Edgar 38
Observation 1: Removal of a node from a heap can be performed in O(logn) time Observation 2: Nodes are removed in order Conclusion: Removing all of the nodes one by one would result in sorted output Analysis: Removal ofall the nodes from a heap is a O(n*logn) operation October 2004 John Edgar 39
A heap can be used to return sorted data In O(n*logn) time However, we can t assume that the data to be sorted just happens to be in a heap! Aha! But we can put it in a heap. Inserting an item into a heap is a O(logn) operation so inserting n items is O(n*logn) But we can do better than just repeatedly calling the insertion algorithm October 2004 John Edgar 40
To create a heap from an unordered array repeatedly call bubbleDown Any subtree in a heap is itself a heap Call bubbleDown on elements in the upper of the array Start with index n/2 and work up to index 0 i.e. from the last non-leaf node to the root bubbleDown does not need to be called on the lower half of the array (the leaves) Since bubbleDown restores the partial ordering from any given node down to the leaves October 2004 John Edgar 41
Assume unsorted input is contained in an array as shown here (indexed from top to bottom and left to right) 0 89 2 29 23 1 3 6 4 5 36 48 94 13 7 8 9 10 11 12 27 70 76 37 42 58 October 2004 John Edgar 42
n = 12, (n-1)/2 = 5 bubbleDown(5) 0 89 2 29 23 1 3 6 4 5 36 48 94 94 13 7 8 9 10 11 12 27 70 76 37 42 42 58 58 October 2004 John Edgar 43
n = 12, (n-1)/2 = 5 bubbleDown(5) 0 89 bubbleDown(4) 2 29 23 1 3 6 4 5 36 48 76 94 13 7 8 9 10 11 12 27 70 76 48 37 37 42 58 October 2004 John Edgar 44
n = 12, (n-1)/2 = 5 bubbleDown(5) 0 89 bubbleDown(4) 2 29 23 1 bubbleDown(3) 3 6 4 5 36 70 76 94 13 7 8 9 10 11 12 27 27 70 36 48 37 42 58 October 2004 John Edgar 45
n = 12, (n-1)/2 = 5 bubbleDown(5) 0 89 bubbleDown(4) 2 23 94 29 1 bubbleDown(3) bubbleDown(2) 3 6 4 5 13 13 70 76 94 23 58 7 8 9 10 11 12 27 36 48 37 42 58 23 October 2004 John Edgar 46
n = 12, (n-1)/2 = 5 bubbleDown(5) 0 89 bubbleDown(4) 2 29 76 94 1 bubbleDown(3) bubbleDown(2) 3 6 4 5 70 76 29 48 13 13 58 bubbleDown(1) 7 8 9 10 11 12 27 36 48 29 37 42 23 October 2004 John Edgar 47
n = 12, (n-1)/2 = 5 bubbleDown(5) 0 89 94 bubbleDown(4) 2 94 89 76 1 bubbleDown(3) bubbleDown(2) 3 6 4 5 70 13 13 48 58 bubbleDown(1) bubbleDown(0) 7 8 9 10 11 12 27 36 37 29 42 23 October 2004 John Edgar 48
bubbleDown is called on half the array The cost for bubbleDown is O(height) It would appear that heapify cost is O(n*logn) In fact the cost is O(n) The analysis is complex but bubbleDown is only called on n/2 nodes and mostly on sub-trees October 2004 John Edgar 49
Heapify the array Repeatedly remove the root After each removal swap the root with the last element in the tree The array is divided into a heap part and a sorted part At the end of the sort the array will be sorted in reverse order October 2004 John Edgar 50
