程序代写 The University of 1

The University of 1
COMMONWEALTH OF AUSTRALIA Copyright Regulations 1969
This material has been reproduced and communicated to you by or on behalf of the University of Sydney pursuant to Part VB of the Copyright Act 1968 (the Act). The material in this communication may be subject to copyright under the Act. Any further copying or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.

Copyright By PowCoder代写 加微信 powcoder

Data structures and Algorithms
Lecture 5: Priority Queues [GT 5]
Dr. André van Renssen School of Computer Science
Some content is taken from material provided by the textbook publisher Wiley.
The University of 2

Priority Queue ADT
Special type of ADT map to store a collection of key-value items where we can only remove smallest key:
– insert(k, v): insert item with key k and value v
– remove_min(): remove and return the item with smallest key – min(): return item with smallest key
– size(): return how many items are stored
– is_empty(): test if queue is empty
We can also have a max version of this min version, but we cannot use both versions at once.
The University of 3

A sequence of priority queue methods:
The University of 4
insert(5,A) insert(9,C) insert(3,B) min() remove_min() insert(7,D) remove_min() remove_min() remove_min() is_empty()
Return value
(3,B) (3,B)
(5,A) (7,D) (9,C) true
Priority queue
{(5,A)} {(5,A),(9,C)} {(3,B),(5,A),(9,C)} {(3,B),(5,A),(9,C)} {(5,A),(9,C)} {(5,A),(7,D),(9,C)} {(7,D),(9,C)} {(9,C)}

Application: Stock Matching Engines
At the heart of modern stock trading systems are highly reliable systems known as matching engines, which match the stock trades of buyers and sellers.
Buyers post bids to buy a number of shares of a given stock
at or below a specified price
Sellers post offers (asks) to sell a number of shares of a given stock at or above a specified price.
The University of 5

Application: Stock Matching Engines
Buy and sell orders are organized according to a price-time priority, where price has highest priority and time is used to break ties
When a new order is entered, the matching engine determines if a trade can be immediately executed and if so, then it performs the appropriate matches according to price-time priority.
Matching Engine
Sell orders
The University of 6
Buy orders

Application: Stock Matching Engines
A matching engine can be implemented with two priority queues, one for buy orders and one for sell orders.
This data structure performs element removals based on priorities assigned to elements when they are inserted.
while True:
bid ← buy_orders.remove_max()
ask ← sell_orders.remove_min() if bid.price ≥ ask.price then
carry out trade (bid, ask)
buy_orders.insert(bid)
sell_orders.insert(ask)
The University of 7

Sequence-based Priority Queue
Unsorted list implementation Sorted list implementation
45231 12345
– insert in O(1) time since we can insert the item at the beginning or end of the sequence
– remove_min and min in O(n) time since we have to traverse the entire list to find the smallest key
– insert in O(n) time since we have to find the place where to insert the item
– remove_min and min in O(1) time since the smallest key is at the beginning
The University of 8

Priority Queue Sorting
We can use a priority queue to sort a list of keys:
1. iteratively insert keys into an empty priority queue
2. iteratively remove_min to get the keys in sorted order
Complexity analysis:
– n insert operations
– n remove_min operations
Either sequence-based implementation take O(n )
def priority_queue_sorting(A): pq ← new priority queue
n ← size(A)
for i in [0, n) do
pq.insert(A[i])
for i in [0, n) do
A[i] = pq.remove_min()
The University of 9

Selection-Sort
Variant of pq-sort using unsorted sequence implementation:
1. inserting elements with n insert operations takes O(n) time
2. removing elements with n remove_min operations takes O(n2)
Can be done in place
(no need for extra space)
Top level loop invariant:
– A[0, i) is sorted
– A[i, n) is the priority queue and all ⩾ A[i-1]
The University of Sydney
def selection_sort(A): n ← size(A)
for i in [0, n) do
# find s ⩾ i minimizing A[s] s←i
for j in [i, n) do
if A[j] < A[s] then s←j # swap A[i] and A[s] A[i], A[s] ← A[s], A[i] Page 10 Selection-Sort Example 7, 4, 8, 2, 5, 3, 9 2, 4, 8, 7, 5, 3, 9 2, 3, 8, 7, 5, 4, 9 2, 3, 4, 7, 5, 8, 9 2, 3, 4, 5, 7, 8, 9 2, 3, 4, 5, 7, 8, 9 2, 3, 4, 5, 7, 8, 9 def selection_sort(A): n ← size(A) for i in [0, n) do # find s ⩾ i minimizing A[s] for j in [i, n) do if A[j] < A[s] then s←j # swap A[i] and A[s] A[i], A[s] ← A[s], A[i] The University of 11 Insertion-Sort Variant of pq-sort using sorted sequence implementation: 1. inserting elements with n insert operations takes O(n2) time 2. removing elements with n remove_min operations takes O(n) Can be done in place (no need for extra space) Top level loop invariant: – A[0, i) is the priority queue (and thus sorted) – A[i, n) is yet-to-be-inserted The University of Sydney def insertion_sort(A): n ← size(A) for i in [1, n) do x ← A[i] # move forward entries > x
while j > 0 and x < A[j-1] do A[j] ← A[j-1] j←j-1 #ifj>0 ⇒ x≥A[j-1] #ifj x
while j > 0 and x < A[j-1] do A[j] ← A[j-1] j←j-1 #ifj>0 ⇒ x≥A[j-1] #ifj key(z) do swap key of z and parent(z) z ← parent(z)
Correctness: after swapping the subtree rooted at z has the property
Complexity: O(log n) time because the height of the heap is log n
The University of 19