Priority Queues and Heaps in Data Structures
CSCI 104
Priority Queues / Heaps
Mark Redekopp
David Kempe
Sandra Batista
Aaron Cote’
Traditional Queue
•
Traditional Queues
–
Accesses/orders items based on POSITION
(front/back)
–
Did not care about item's VALUE
•
Priority Queue
–
Orders items based on VALUE
•
Either minimum or maximum
–
Items arrive in some arbitrary order
–
When removing an item, we always want the
minimum or maximum depending on the
implementation
–
Leads to a "sorted" list
–
Examples:
•
Think hospital ER, air-traffic control, etc.
T
r
a
d
i
t
i
o
n
a
l
Q
u
e
u
e
P
r
i
o
r
i
t
y
Q
u
e
u
e
Priority Queue
•
What member functions does a Priority Queue have?
–
push(item) – Add an item to the appropriate location of the
PQ
–
top() – Return the min./max. value
–
pop() - Remove the front (min. or max) item from the PQ
–
size() - Number of items in the PQ
–
empty() - Check if the PQ is empty
–
[Optional]: changePriority(item, new_priority)
•
Useful in many algorithms (especially graph and search
algorithms)
•
Priority can be based on…
–
Intrinsic data-type being stored (i.e. operator<()
of type T)
–
Separate parameter from data type, T, and
passed in which allows the same object to have
different priorities based on the programmer's
desire (i.e. same object can be assigned different
priorities)
P
r
i
o
r
i
t
y
Q
u
e
u
e
(
P
r
i
o
r
i
t
y
b
a
s
e
d
o
n
i
n
t
r
i
n
s
i
c
p
r
o
p
e
r
t
y
o
f
t
h
e
d
a
t
a
)
class Patient {public:
bool operator<(...);
};
P
r
i
o
r
i
t
y
Q
u
e
u
e
(
P
r
i
o
r
i
t
y
b
a
s
e
d
o
n
s
e
p
a
r
a
t
e
p
r
i
o
r
i
t
y
p
a
r
a
m
e
t
e
r
)
Priority Queue Efficiency
•
If implemented as a sorted array list
–
Insert() = ___________
–
Top() = ___________
–
Pop() = ____________
•
If implemented as an unsorted array list
–
Insert() = ___________
–
Top() = ___________
–
Pop() = ____________
Priority Queue Efficiency
•
If implemented as a sorted array list
–
[Use back of array as location of top element]
–
Insert() = O(n)
–
Top() = O(1)
–
Pop() = O(1)
•
If implemented as an unsorted array list
–
Insert() = O(1)
–
Top() = O(n)
–
Pop() = O(n)
Heap Data Structure
•
Provides an efficient implementation for a priority queue
•
Can think of heap as a
complete
binary tree that maintains
the
heap property
:
–
Heap Property
: Every parent is less-than-or-equal (if min-heap) or greater-
than-or-equal (if max-heap)
both
children,
but no ordering property
between children
•
Minimum/Maximum value is always the top element
M
i
n
-
H
e
a
p
7
9
18
19
35
14
10
28
39
36
43
16
25
A
l
w
a
y
s
a
c
o
m
p
l
e
t
e
t
r
e
e
Heap Operations
•
Push: Add a new item to the
heap and modify heap as
necessary
•
Pop: Remove min/max item
and modify heap as
necessary
•
Top: Returns min/max
•
Since heaps are complete
binary trees we can use an
array/vector as the
container
template <typename T>
class MinHeap
{ public:MinHeap(int init_capacity);
~MinHeap()
void push(const T& item);
T& top();
void pop();
int size() const;
bool empty() const;
private:
// Helper function
void trickleDown(int idx);
vector<T> items_; // or array
}
Array/Vector Storage for Heap
•
Recall: A
complete
binary tree (i.e. only the lowest-
level contains empty locations and items added left
to right) can be modeled as an array
•
Parent(i) = ______
–
Left_child(p) = ______
–
Right_child(p) = ______
7
9
18
19
35
14
10
28
39
36
43
16
17
7
1
8
9
1
9
0
1
2
3
4
3
5
1
4
1
0
2
8
3
9
5
6
7
8
9
3
6
4
3
1
6
1
7
1
0
1
1
1
2
0
1
2
3
4
5
6
7
8
1
0
1
1
1
2
9
Push Heap / TrickleUp
•
Add item to first free location at
bottom of tree
•
Recursively promote it up while
it is less than its parent
–
Remember valid heap all parents
< children…so we need to promote
it up until that property is satisfied
7
9
18
19
35
14
10
28
39
36
43
16
25
7
8
18
19
35
14
9
28
39
36
43
16
25
8
8
10
P
u
s
h
_
H
e
a
p
(
8
)
0
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
void MinHeap<T>::push(const T& item)
{items_.push_back(item);
trickleUp(size()-1);
}
void MinHeap<T>::trickleUp(int loc)
{// could be implemented recursively
int parent =
_________;
while(parent
______
&&
items_[loc]
___
items_[parent] )
{ swap(items_[parent], items_[loc]);loc =
___________;
parent =
________;
}
}
top()
•
top()
simply needs
to return first item
7
9
18
19
35
14
10
28
39
36
43
16
25
T
o
p
(
)
r
e
t
u
r
n
s
7
T const & MinHeap<T>::top()
{if( empty() )
throw(std::out_of_range());
return items_[0];
}
Pop Heap / TrickleDown
•
Pop utilizes the "heapify"
algorith (a.k.a. trickleDown)
•
Takes last (greatest) node
puts it in the top location
and then recursively swaps
it for the smallest child until
it is in its right place
7
9
18
19
35
14
10
28
39
36
43
16
25
9
10
18
19
35
14
7
28
39
36
43
16
O
r
i
g
i
n
a
l
9
25
9
18
19
35
14
10
28
39
36
43
16
25
void MinHeap<T>::pop()
{ items_[0] = items_.back(); items_.pop_back()trickleDown(0); // a.k.a. trickleDown()
}
void MinHeap<T>::trickleDown(int idx)
{if(2*idx+1 >= size()) return;
int smallerChild = 2*idx+1; // start w/ left
if(smallerChild+1 < size()) {int rChild = smallerChild+1;
if(items_[rChild] < items_[smallerChild])
smallerChild = rChild;
} }
if(items_[idx] > items_[smallerChild]){swap(items_[idx], items_[smallerChild]);
trickleDown(smallerChild);
} }
Practice
7
21
35
26
24
50
29
43
36
18
19
39
28
7
9
35
14
10
36
18
19
39
28
P
u
s
h
(
1
1
)
P
o
p
(
)
4
8
35
26
24
36
17
19
39
28
P
o
p
(
)
7
21
35
26
24
50
29
43
36
18
19
39
28
P
u
s
h
(
2
3
)
Using a Heap to Sort
•
If we could make a valid heap out of an
arbitrary array
, could we use that heap to
sort
our data?
•
Sure, just call top() and pop()
n
times to get data in sorted order
•
How long would that take?
–
n
calls to:
top()=
Θ
(1)
and
pop()=
Θ
(log n)
–
Thus total time =
Θ
(n * log n)
•
But how long does it take to convert the
array
to a
valid heap
?
A
r
r
a
y
C
o
n
v
e
r
t
e
d
t
o
V
a
l
i
d
H
e
a
p
7
14
35
28
18
9
10
19
V
a
l
i
d
H
e
a
p
7
9
1
0
1
4
0
1
2
3
4
1
8
1
9
2
8
3
5
5
6
7
A
r
r
a
y
a
f
t
e
r
t
o
p
/
p
o
p
p
i
n
g
t
h
e
h
e
a
p
n
t
i
m
e
s
7
9
1
4
1
0
0
1
2
3
4
3
5
2
8
1
8
1
9
5
6
7
2
8
9
1
8
1
0
0
1
2
3
4
3
5
1
4
7
1
9
5
6
7
28
18
35
14
7
9
10
19
A
r
b
i
t
r
a
r
y
A
r
r
a
y
C
o
m
p
l
e
t
e
T
r
e
e
V
i
e
w
o
f
A
r
b
i
t
r
a
r
y
A
r
r
a
y
make_heap(): Converting An Unordered
Array to a Heap
•
We can convert an unordered array to
a heap
–
std::make_heap() does this
–
Let's see how…
•
Basic operation: Given two heaps we
can try to make one heap by unifying
them with some new, arbitrary value
but it likely won't be a heap
•
How can we make a heap from this
non-heap
•
TrickleDown!! (we did this in pop() )
2
8
9
7
1
0
0
1
2
3
4
3
5
1
8
1
4
1
9
5
6
7
7
35
18
14
9
10
19
T
r
e
e
V
i
e
w
o
f
A
r
r
a
y
A
r
r
a
y
n
o
t
f
u
l
f
i
l
l
i
n
g
h
e
a
p
p
r
o
p
e
r
t
y
(
i
s
s
u
e
i
s
2
8
a
t
i
n
d
e
x
0
)
28
A
V
a
l
i
d
H
e
a
p
A
V
a
l
i
d
H
e
a
p
Converting An Array to a Heap
•
To convert an array to a heap we can
use the idea of first making heaps of
both sub-trees and then combining
the sub-trees (a.k.a. semi heaps) into
one unified heap by calling
trickleDown() on their parent()
•
First consider all leaf nodes, are they
valid heaps if you think of them as the
root of a tree?
–
Yes!!
•
So just start at the first non-leaf
2
8
9
1
8
1
0
0
1
2
3
4
3
5
1
4
7
1
9
5
6
7
28
18
35
14
7
9
10
19
T
r
e
e
V
i
e
w
o
f
A
r
r
a
y
O
r
i
g
i
n
a
l
A
r
r
a
y
Converting An Array to a Heap
•
First consider all leaf nodes, are they
valid heaps if you think of them as the
root of a tree?
–
Yes!!
•
So just start at the first non-leaf
–
TrickleDown(Loc. 3)
28
18
35
14
7
9
10
19
L
e
a
f
s
a
r
e
v
a
l
i
d
h
e
a
p
s
b
y
d
e
f
i
n
i
t
i
o
n
10
19
trickleDown(3)
10
19
A
l
r
e
a
d
y
i
n
t
h
e
r
i
g
h
t
o
r
d
e
r
trickleDown(2)
S
w
a
p
1
8
&
7
18
14
7
7
14
18
trickleDown(1)
A
l
r
e
a
d
y
a
h
e
a
p
35
9
10
19
trickleDown(0)
28
7
35
14
18
9
10
19
S
w
a
p
2
8
<
-
>
7
S
w
a
p
2
8
<
-
>
1
4
Converting An Array to a Heap
•
Now that we have a valid heap, we can sort by top and popping…
•
Can we do it in place?
–
Yes, Break the array into "heap" and "sorted" areas, iteratively adding to the "sorted" area
7
14
35
28
18
9
10
19
1
9
9
1
4
1
0
0
1
2
3
4
3
5
2
8
1
8
7
5
6
7
9
14
35
28
18
10
19
9
1
0
1
4
1
9
0
1
2
3
4
3
5
2
8
1
8
7
5
6
7
9
14
35
28
18
10
19
1
8
1
0
1
4
1
9
0
1
2
3
4
3
5
2
8
9
7
5
6
7
trickleDown
(0)
S
w
a
p
t
o
p
&
l
a
s
t
10
14
35
28
18
19
1
0
1
8
1
4
1
9
0
1
2
3
4
3
5
2
8
9
7
5
6
7
trickleDown
(0)
S
w
a
p
t
o
p
&
l
a
s
t
Sorting Using a Heap
•
Notice the result is in descending order.
•
How could we make it ascending order?
–
Create a max heap rather than min heap.
18
28
19
35
1
8
1
9
2
8
3
5
0
1
2
3
4
14
10
9
7
5
6
7
35
28
19
18
0
1
2
3
4
14
10
9
7
5
6
7
Build-Heap Run-Time
•
To build a heap from an arbitrary array require n calls to
trickleDown.
•
TrickleDown takes
(___________)
•
Let's be more specific:
–
TrickleDown takes
(h)
–
Because most of the trickleDown calls are made in the bottom of the
tree (shallow h), it turns out Build-Heap can be done in
(n)
•
All calls do constant work at h=1
•
n/2 calls do constant work at h=2
•
n/4 calls do constant work at h=3
•
Totals: n + n/2 + n/4 + …
•
As h approaches infinity, the sum approaches 2n.
28
18
35
14
7
9
10
19
STL Priority Queue
•
Implements a heap
•
Operations:
–
push(new_item)
–
pop(): removes but does not
return top item
–
top() return top item (item at
back/end of the container)
–
size()
–
empty()
•
http://www.cplusplus.com/refere
nce/stl/priority_queue/push/
•
By default, implements a
max
heap.
•
Runtime:
(log(n)) push and pop
while all other functions are
constant (i.e.
(1))
// priority_queue::push/pop
#include <iostream>
#include <queue>
using namespace std;
int main ()
{priority_queue<int> mypq;
mypq.push(30);
mypq.push(100);
mypq.push(25);
mypq.push(40);
cout << "Popping out elements...";
while (!mypq.empty()) {cout<< " " << mypq.top();
mypq.pop();
}
cout<< endl;
return 0;
}
C
o
d
e
h
e
r
e
w
i
l
l
p
r
i
n
t
1
0
0
4
0
3
0
2
5
Priority queues prioritize item retrieval based on value, contrasting with traditional queues that follow a first-in-first-out approach. Priority queues efficiently manage items based on their importance, often utilized in scenarios like emergency rooms or air traffic control. Heaps, a form of binary tree, provide efficient priority queue implementation with the crucial heap property ensuring optimal retrievals.
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
1 CSCI 104 Priority Queues / Heaps Mark Redekopp David Kempe Sandra Batista Aaron Cote
2 Traditional Queue Traditional Queues Accesses/orders items based on POSITION (front/back) Did not care about item's VALUE Priority Queue Orders items based on VALUE Either minimum or maximum Items arrive in some arbitrary order When removing an item, we always want the minimum or maximum depending on the implementation Leads to a "sorted" list Examples: Think hospital ER, air-traffic control, etc. (push_back) 47 (pop_front) 15 33 62 81 Traditional Queue (push) 47 (pop) 15 33 62 81 Priority Queue
3 Priority Queue class Patient { public: bool operator<(...); }; What member functions does a Priority Queue have? push(item) Add an item to the appropriate location of the PQ top() Return the min./max. value pop() - Remove the front (min. or max) item from the PQ size() - Number of items in the PQ empty() - Check if the PQ is empty [Optional]: changePriority(item, new_priority) Useful in many algorithms (especially graph and search algorithms) Priority can be based on Intrinsic data-type being stored (i.e. operator<() of type T) Separate parameter from data type, T, and passed in which allows the same object to have different priorities based on the programmer's desire (i.e. same object can be assigned different priorities) (push) P6 (top) (pop) P2 P3 P4 P5 P1 Priority Queue (Priority based on intrinsic property of the data) (push) 27, P6 (top) (pop) 12, P1 17, P2 31, P3 39, P5 P1 Priority Queue (Priority based on separate priority parameter)
4 Priority Queue Efficiency If implemented as a sorted array list Insert() = ___________ Top() = ___________ Pop() = ____________ If implemented as an unsorted array list Insert() = ___________ Top() = ___________ Pop() = ____________
5 Priority Queue Efficiency If implemented as a sorted array list [Use back of array as location of top element] Insert() = O(n) Top() = O(1) Pop() = O(1) If implemented as an unsorted array list Insert() = O(1) Top() = O(n) Pop() = O(n)
6 Heap Data Structure Provides an efficient implementation for a priority queue Can think of heap as a complete binary tree that maintains the heap property: Heap Property: Every parent is less-than-or-equal (if min-heap) or greater- than-or-equal (if max-heap) both children, but no ordering property between children Minimum/Maximum value is always the top element 7 18 9 Always a complete tree 19 35 14 10 28 39 36 43 16 25 Min-Heap
7 Heap Operations Push: Add a new item to the heap and modify heap as necessary Pop: Remove min/max item and modify heap as necessary Top: Returns min/max Since heaps are complete binary trees we can use an array/vector as the container template <typename T> class MinHeap { public: MinHeap(int init_capacity); ~MinHeap() void push(const T& item); T& top(); void pop(); int size() const; bool empty() const; private: // Helper function void trickleDown(int idx); vector<T> items_; // or array }
8 Array/Vector Storage for Heap Recall: A complete binary tree (i.e. only the lowest- level contains empty locations and items added left to right) can be modeled as an array Parent(i) = ______ Left_child(p) = ______ Right_child(p) = ______ 0 0 1 2 3 4 5 6 7 8 9 10 11 12 7 7 18 9 19 35 14 10 28 39 36 43 16 17 2 1 18 9 3 4 5 6 19 35 14 10 9 10 11 8 12 7 28 39 36 43 16 17
9 Push Heap / TrickleUp Add item to first free location at bottom of tree Recursively promote it up while it is less than its parent Remember valid heap all parents < children so we need to promote it up until that property is satisfied void MinHeap<T>::push(const T& item) { items_.push_back(item); trickleUp(size()-1); } void MinHeap<T>::trickleUp(int loc) { // could be implemented recursively int parent = _________; while(parent ______ && items_[loc] ___ items_[parent] ) { swap(items_[parent], items_[loc]); loc = ___________; parent = ________; } } 0 Push_Heap(8) 7 7 2 1 18 9 18 8 3 4 5 6 19 35 14 10 19 35 14 9 1011 8 9 12 13 7 28 39 36 43 16 25 8 8 28 39 36 43 16 25 10
10 top() T const & MinHeap<T>::top() { if( empty() ) throw(std::out_of_range()); return items_[0]; } top() simply needs to return first item Top() returns 7 7 18 9 19 35 14 10 28 39 36 43 16 25
11 Pop Heap / TrickleDown void MinHeap<T>::pop() { items_[0] = items_.back(); items_.pop_back() trickleDown(0); // a.k.a. trickleDown() } Pop utilizes the "heapify" algorith (a.k.a. trickleDown) Takes last (greatest) node puts it in the top location and then recursively swaps it for the smallest child until it is in its right place void MinHeap<T>::trickleDown(int idx) { if(2*idx+1 >= size()) return; int smallerChild = 2*idx+1; // start w/ left if(smallerChild+1 < size()) { int rChild = smallerChild+1; if(items_[rChild] < items_[smallerChild]) smallerChild = rChild; } } if(items_[idx] > items_[smallerChild]){ swap(items_[idx], items_[smallerChild]); trickleDown(smallerChild); } } Original 7 7 9 9 25 18 9 18 10 18 9 19 35 14 10 19 35 14 25 19 35 14 10 28 39 36 43 16 25 28 39 36 43 16 28 39 36 43 16
12 Practice Push(11) Push(23) 7 7 18 9 18 21 19 35 14 10 19 35 26 24 28 39 36 28 39 36 43 29 50 Pop() Pop() 7 4 18 21 17 8 19 35 26 24 19 35 26 24 28 39 36 43 29 50 28 39 36
13 Using a Heap to Sort If we could make a valid heap out of an arbitrary array, could we use that heap to sort our data? Sure, just call top() and pop() n times to get data in sorted order How long would that take? n calls to: top()= (1) and pop()= (log n) Thus total time = (n * log n) But how long does it take to convert the array to a valid heap? 0 1 2 3 4 5 6 7 7 9 14 10 35 28 18 19 Array Converted to Valid Heap 7 0 1 2 3 4 5 6 7 9 14 28 9 18 10 35 14 7 19 Arbitrary Array 10 35 28 18 28 9 18 Valid Heap 19 10 35 14 7 0 1 2 3 4 5 6 7 7 9 10 14 18 19 28 35 19 Complete Tree View of Arbitrary Array Array after top/popping the heap n times
14 make_heap(): Converting An Unordered Array to a Heap We can convert an unordered array to a heap std::make_heap() does this Let's see how Basic operation: Given two heaps we can try to make one heap by unifying them with some new, arbitrary value but it likely won't be a heap How can we make a heap from this non-heap TrickleDown!! (we did this in pop() ) 0 1 2 3 4 5 6 7 28 9 7 10 35 18 14 19 Array not fulfilling heap property (issue is 28 at index 0) 28 9 7 10 35 18 14 19 A Valid Heap A Valid Heap Tree View of Array
15 Converting An Array to a Heap 0 1 2 3 4 5 6 7 To convert an array to a heap we can use the idea of first making heaps of both sub-trees and then combining the sub-trees (a.k.a. semi heaps) into one unified heap by calling trickleDown() on their parent() 28 9 18 10 35 14 7 19 Original Array 28 9 18 10 35 14 7 First consider all leaf nodes, are they valid heaps if you think of them as the root of a tree? Yes!! So just start at the first non-leaf 19 Tree View of Array
16 Converting An Array to a Heap 28 First consider all leaf nodes, are they valid heaps if you think of them as the root of a tree? Yes!! So just start at the first non-leaf TrickleDown(Loc. 3) 9 18 10 35 14 7 19 Leafs are valid heaps by definition trickleDown(3) trickleDown(2) trickleDown(1) trickleDown(0) Swap 28 <-> 7 Swap 28 <-> 14 Already in the right order Swap 18 & 7 Already a heap 9 28 18 7 10 10 9 7 10 35 19 19 14 7 14 18 19 10 35 14 18 19
17 Converting An Array to a Heap Now that we have a valid heap, we can sort by top and popping Can we do it in place? Yes, Break the array into "heap" and "sorted" areas, iteratively adding to the "sorted" area 7 9 Swap top & last 9 14 10 14 trickleDown(0) 10 35 28 18 19 35 28 18 19 0 1 2 3 4 35 28 18 7 5 6 7 0 1 2 3 4 35 28 18 7 5 6 7 19 9 14 10 9 10 14 19 9 10 Swap top & last 10 14 18 14 trickleDown(0) 19 35 28 18 19 35 28 0 1 2 3 4 35 28 9 7 5 6 7 0 1 2 3 4 35 28 9 7 5 6 7 18 10 14 19 10 18 14 19
18 Sorting Using a Heap 18 19 28 0 1 2 3 4 5 6 7 35 35 28 19 18 14 10 9 7 0 1 2 3 4 5 6 7 14 10 9 7 18 19 28 35 Notice the result is in descending order. How could we make it ascending order? Create a max heap rather than min heap.
19 Build-Heap Run-Time To build a heap from an arbitrary array require n calls to trickleDown. TrickleDown takes (___________) Let's be more specific: TrickleDown takes (h) Because most of the trickleDown calls are made in the bottom of the tree (shallow h), it turns out Build-Heap can be done in (n) All calls do constant work at h=1 n/2 calls do constant work at h=2 n/4 calls do constant work at h=3 Totals: n + n/2 + n/4 + As h approaches infinity, the sum approaches 2n. 28 9 18 10 35 14 7 19
20 STL Priority Queue Implements a heap Operations: push(new_item) pop(): removes but does not return top item top() return top item (item at back/end of the container) size() empty() http://www.cplusplus.com/refere nce/stl/priority_queue/push/ By default, implements a max heap. Runtime: (log(n)) push and pop while all other functions are constant (i.e. (1)) // priority_queue::push/pop #include <iostream> #include <queue> using namespace std; int main () { priority_queue<int> mypq; mypq.push(30); mypq.push(100); mypq.push(25); mypq.push(40); cout << "Popping out elements..."; while (!mypq.empty()) { cout<< " " << mypq.top(); mypq.pop(); } cout<< endl; return 0; } Code here will print 100 40 30 25
