Priority Queues: Understanding Heaps
Priority Queues (Heaps)
•
Queues are a standard mechanism for ordering tasks on
a first-come, first-served basis
•
However, some tasks may be more important or timely
than others (higher priority)
•
Priority queues
•
Store tasks using a partial ordering based on priority
•
Ensure highest priority task at head of queue
•
Heaps
are the underlying data structure of priority
queues
Priority Queues: Specification
Main operations
•
insert
(i.e., enqueue)
•
Dynamic insert
•
specification of a priority level (0-high, 1,2.. Low)
•
deleteMin
(i.e., dequeue)
•
Finds the current minimum element (read: “highest
priority”) in the queue, deletes it from the queue, and
returns it
•
Performance goal is for operations to be “fast”
Using priority queues
5
3
10
13
19
8
4
22
11
deleteMin()
2
Dequeues the next element
with the highest priority
insert()
Simple Implementations
•
Unordered linked list
•
O(1) insert
•
O(n) deleteMin
•
Ordered linked list
•
O(n) insert
•
O(1) deleteMin
•
Ordered array
•
O(lg n + n) insert
•
O(n) deleteMin
•
Balanced BST
•
O(log
2
n) insert and deleteMin
Binary Heap
A Heap
is a Binary Tree
H
that stores a collection of
keys at its internal nodes and that satisfies two
additional properties:
-1)
Relational
Property
-2)
Structural
Property
Heap-order Property
(Relational Property)
•
Heap-order property (for a “MinHeap”)
•
For every node X, key(parent(X)) ≤ key(X)
•
Except root node, which has no parent
•
Thus, minimum key always at root
•
Alternatively, for a “MaxHeap”, always keep
the maximum key at the root
•
Insert and deleteMin must maintain heap-
order property
Minimum
element
Structure Property
•
A binary heap is a complete binary tree
•
Each level (except possibly the bottom
most level) is completely filled
•
The bottom most level may be partially
filled
(from left to right)
•
Height of a complete binary tree with N
elements is
Every level
(except last)
saturated
N=10
H
e
i
g
h
t
=
3
A structure which fails to fulfill the Structural
Property
•
A binary tree satisfies the (
min-
)
heap-order
property if every child greater than (or equal to)
parent
(if exist).
•
A
binary min-heap
is a left-complete binary tree that also satisfies the heap-order property.
13
21
24
31
16
19
68
65
26
32
Note that there is no definite
order between values in
sibling nodes; also, it is
obvious that the minimum
value is at the root.
A binary min-heap
Binary Heaps: Array Implementation
•
Implementing binary heaps.
•
Use an array: no need for explicit parent
or child pointers
(or index values)
.
•
Parent(i) =
i/2
•
Left(i) = 2i
+ 1
•
Right(i) = 2i +
2
06
14
78
18
81
77
91
45
53
47
64
84
99
83
0
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
index
Array
Binary Heap: Insertion
•
Insert element x into heap.
•
Insert into next available slot.
•
Bubble up until it's heap ordered.
12
06
14
78
18
81
77
91
45
53
47
64
84
99
83
Binary Heap: Insertion
13
06
14
78
18
81
77
91
45
53
47
64
84
99
83
swap with parent
Binary Heap: Insertion
06
14
78
18
81
77
91
45
42
47
64
84
99
83
53
swap with parent
Binary Heap: Insertion
•
O(log N) operations
06
14
78
18
81
77
91
42
45
47
64
84
99
83
53
stop: heap ordered
Binary Heap: Decrease Key
•
Decrease key of element x to k.
•
Bubble up until it's heap ordered.
•
O(log N) operations.
•
Ex: Decrease 77 to 10
06
14
78
18
81
77
91
42
45
47
64
84
99
83
53
Binary Heap: Delete Min
•
Delete minimum element from heap.
•
Exchange root with rightmost leaf.
•
Bubble root down until it's heap ordered.
06
14
78
18
81
77
91
42
45
47
64
84
99
83
53
Binary Heap: Delete Min
•
Delete minimum element from heap.
•
Exchange root with rightmost leaf.
•
Bubble root down until it's heap ordered.
06
14
78
18
81
77
91
42
45
47
64
84
99
83
53
53
14
78
18
81
77
91
42
45
47
64
84
99
83
06
Binary Heap: Delete Min
53
14
78
18
81
77
91
42
45
47
64
84
99
83
exchange with left child
14
53
78
18
81
77
91
42
45
47
64
84
99
83
exchange with right child
Binary Heap: Delete Min
•
Delete minimum element from heap.
•
Exchange root with rightmost leaf.
•
Bubble root down until it's heap ordered.
•
O(log N) operations.
14
18
78
53
81
77
91
42
45
47
64
84
99
83
stop: heap ordered
Binary Heap: Heapsort
•
Heapsort.
•
Insert N items into binary heap.
•
Perform N delete-min operations.
•
O(N log N) sort.
•
No extra storage.
make-heap
Operation
insert
find-min
delete-min
union
decrease-key
delete
1
Binary
log N
1
log N
N
log N
log N
1
Linked List
1
N
N
1
1
N
is-empty
1
1
Heap
Master the concept of priority queues using heaps. Explore the intricacies of implementing and working with priority queues in your applications. Learn how heaps optimize access to elements based on their priority levels, enhancing the efficiency of your algorithms.
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
Queues are a standard mechanism for ordering tasks on a first-come, first-served basis However, some tasks may be more important or timely than others (higher priority) Priority queues Store tasks using a partial ordering based on priority Ensure highest priority task at head of queue Heaps are the underlying data structure of priority queues
Priority Queues: Specification Main operations insert (i.e., enqueue) Dynamic insert specification of a priority level (0-high, 1,2.. Low) deleteMin (i.e., dequeue) Finds the current minimum element (read: highest priority ) in the queue, deletes it from the queue, and returns it Performance goal is for operations to be fast
Using priority queues 4 10 19 3 5 13 8 22 11 insert() deleteMin() Dequeues the next element with the highest priority 2
Simple Implementations Unordered linked list O(1) insert O(n) deleteMin Ordered linked list O(n) insert O(1) deleteMin Ordered array O(lg n + n) insert O(n) deleteMin Balanced BST O(log2n) insert and deleteMin 3 10 2 5 10 5 3 2 2 3 5 10
Binary Heap A Heap is a Binary Tree H that stores a collection of keys at its internal nodes and that satisfies two additional properties: -1)Relational Property -2)Structural Property
Heap-order Property(Relational Property) Heap-order property (for a MinHeap ) For every node X, key(parent(X)) key(X) Except root node, which has no parent Thus, minimum key always at root Alternatively, for a MaxHeap , always keep the maximum key at the root Insert and deleteMin must maintain heap- order property Minimum element
Structure Property A binary heap is a complete binary tree Each level (except possibly the bottom most level) is completely filled The bottom most level may be partially filled (from left to right) N=10 Height = 3 Every level (except last) saturated Height of a complete binary tree with N elements is N 2 log
A binary tree satisfies the (min-)heap-order property if every child greater than (or equal to) parent (if exist). A binary min-heap is a left-complete binary tree that also satisfies the heap-order property. 13 Note that there is no definite order between values in sibling nodes; also, it is obvious that the minimum value is at the root. 21 16 24 31 19 68 65 26 32 A binary min-heap
Binary Heaps: Array Implementation 06 0 Implementing binary heaps. Use an array: no need for explicit parent or child pointers(or index values). Parent(i) = i/2 Left(i) = 2i+ 1 Right(i) = 2i + 2 14 1 45 2 78 3 18 4 47 5 53 6 91 77 83 84 81 9 99 64 7 8 11 13 10 12 index 0 1 2 3 4 5 6 7 8 9 11 12 13 14 06 14 45 78 18 47 53 83 91 81 77 84 99 64 Array
Binary Heap: Insertion Insert element x into heap. Insert into next available slot. Bubble up until it's heap ordered. 06 14 45 78 18 47 53 91 77 83 84 81 99 64 42 next free slot 12
Binary Heap: Insertion swap with parent 06 14 45 78 18 47 53 91 77 83 84 81 99 64 42 42 13
Binary Heap: Insertion swap with parent 06 14 45 78 18 47 42 91 77 83 84 81 99 64 42 53
Binary Heap: Insertion O(log N) operations stop: heap ordered 06 14 42 78 18 47 45 91 77 83 84 81 99 64 53
Binary Heap: Decrease Key Decrease key of element x to k. Bubble up until it's heap ordered. O(log N) operations. Ex: Decrease 77 to 10 06 14 42 78 18 47 45 91 77 83 84 81 99 64 53
Binary Heap: Delete Min Delete minimum element from heap. Exchange root with rightmost leaf. Bubble root down until it's heap ordered. 06 14 42 78 18 47 45 91 77 83 84 81 99 64 53
Binary Heap: Delete Min Delete minimum element from heap. Exchange root with rightmost leaf. Bubble root down until it's heap ordered. 53 06 14 42 14 42 78 18 47 45 78 18 47 45 91 77 83 84 81 99 64 06 91 77 83 84 81 99 64 53
Binary Heap: Delete Min exchange with right child exchange with left child 53 14 14 42 53 42 78 18 47 45 78 18 47 45 91 77 83 84 81 99 64 91 77 83 84 81 99 64
Binary Heap: Delete Min Delete minimum element from heap. Exchange root with rightmost leaf. Bubble root down until it's heap ordered. O(log N) operations. stop: heap ordered 14 18 42 78 53 47 45 91 77 83 84 81 99 64
Binary Heap: Heapsort Heapsort. Insert N items into binary heap. Perform N delete-min operations. O(N log N) sort. No extra storage.
Heap Operation Linked List Binary make-heap 1 1 insert 1 log N find-min N 1 delete-min N log N union 1 N decrease-key 1 log N delete N log N is-empty 1 1
