CS代考 Lecture 9: More Sorting Algorithms

Lecture 9: More Sorting Algorithms
Priority Queues, Heaps, and Heapsort

Priority Queue: Motivating Example

3 jobs have been submitted to a printer in the order A, B, C. Consider the printing pool at this moment.
Sizes: Job A — 100 pages Job B — 10 pages
Job C — 1 page
Average finish time with FIFO service: (100+110+111) / 3 = 107 time units
Average finish time for shortest-job-first service: (1+11+111) / 3 = 41 time units
FIFO = First In First Out

Priority Queue: Motivating Example
 The elements in the queue are printing jobs, each with the associated number of pages that serves as its priority
 Processing the shortest job first corresponds to extracting the smallest element from the queue
 Insert new printing jobs as they arrive
Want a queue capable of supporting two operations: Insert and Extract-Min.

Priority Queue
A Priority Queue is an abstract data structure that supports two operations
 Insert: inserts the new element into the queue
 Extract-Min: removes and returns the smallest element
from the queue
Priority Queue

Possible Implementations
 unsorted list a pointer to the smallest element
 Insert in
 Extract-Min in
time, since it requires a linear scan to
find the new minimum
 sorted doubly linked list + a pointer to first element
 Insert in time (to insert at proper location)
 Extract-Min in time
Is there any data structure that supports both these priority queue operations faster at the same time?
In time for each?

(Binary) Heap
Pack to the left
Heaps are “almost complete binary trees”
 All levels are full except possibly the lowest level
 If the lowest level is not full, then nodes must be packed to

Heap-order Property
436 136 A min-heap Not a heap
Heap-order property:
The value of a node is at least the value of its parent — Min-heap

Heap Properties
 If the heap-order property is maintained, we will show that heaps support the following operations efficiently
( is # elements in the heap):
 Insert in time
 Extract-Min in

A heap with height (deepest level)
=> A heap with height => A heap with height
Consider a heap with an
=> an -element heap has height
Heap Properties
Nodes on or above level 𝑖
Level Nodes on 𝑖 = level 𝑖
011 123 247
has 􏰌 nodes on every level nodes above level
has between 􏰒 and 􏰒􏰑􏰆 nodes.
elements and height

Heap Properties
 If the heap-order property is maintained, we will show that heaps support the following operations efficiently
( is # elements in the heap):
 Insert in time
 Extract-Min in
 Structural properties
 an -element heap has height .
 Also, the structure is so regular, it can be represented in an array with no pointers required!!!

Array Implementation of Heap
 The root is in array position
 For any element in array position
 The left child is in position
 The right child is in position
 The parent is in position
1 2 3 4 5 6 7 8 9 10

Array Implementation of Heap
1 2 3 4 5 6 7 8 9 10
Example: C = 𝐴[3]. C’s children are
𝐹=𝐴2􏰻3 =𝐴[6]and𝐺=𝐴2􏰻3+1 =𝐴[7]. G’sparentisC=𝐴3 =𝐴[7/2].
 The root is in array position
 For any element in array position
 The left child is in position
 The right child is in position
 The parent is in position
 We will draw the heaps as trees, with the understanding that an actual implementation will use simple arrays

 Add the new element to the next available position at the lowest level
 Restore the min-heap property if violated
 General strategy is percolate up (or bubble up): if the parent of the
element is larger than the element, then interchange the parent
with child.

Add the new element to the next available position at the lowest level Restore the min-heap property if violated
General strategy is percolate up (or bubble up): if the parent of the element is larger than the element, then interchange the parent
with child.
Percolate up to maintain 7 8 4 the min-heap property
Correctness: after each swap, the min-heap property is satisfied for the subtree rooted at the new element
Time complexity height

Insertion (2nd Example)
 Add the new element to the next available position at the lowest level
 Restore the min-heap property if violated
 General strategy is percolate up (or bubble up): if the parent of the
element is larger than the element, then interchange the parent
with child.

Insert( , ): Add item to heap creating heap begin
while 􏰈􏰙 and do
// is less than its parent
Swap and 􏰈􏰙 ;//BubbleUp 􏰙

Extract-Min: First Attempt
4565 565 6565
678 678 78 Min-heap property preserved, but completeness not preserved!

Extract-Min
 Move the last element X to the root
(i.e., overwrite the minimum element stored there)
 Restore the min-heap property by percolating (or bubbling down): if the element is larger than either of its children, then interchange it with the smaller of its children.
Remove last element and copy its value to the root

Extract-Min
 Copy the last element X to the root
(i.e., overwrite the minimum element stored there)
 Restore the min-heap property by percolating (or bubbling) down): if the element is larger than either of its children, then interchange it with the smaller of its children.
Percolate down to maintain min-heap property

Extract-Min
 Copy the last element X to the root
(i.e., overwrite the minimum element stored there)
 Restore the min-heap property by percolating (or bubbling down): if the element is larger than either of its children, then interchange it with the smaller of its children.
 Correctness: after each swap, the min-heap property is satisfied for all
nodes except the node containing X (with respect to its children) Time complexity height
Percolate down to maintain min-heap property

Extract- -Min( ): Remove (smallest) item in Heap and make a Heap of remaining elements.
Empty array cells will contain an as an empty flag.
Output( );
Swap and ; ; ; // Remove smallest
larger than a child, swap with min child

 Build a binary heap of elements
 the minimum element is at the top of the heap
 insert elements one by one
(A more clever approach can do this in
 Perform Extract-Min operations
 the elements are extracted in sorted order
 each Extract-Min operation takes time
 Total time complexity:

Heapsort example: Insert(10) 01

Heapsort example: Insert(4) 01

Heapsort example: Insert(4) 4

Heapsort example: Insert(6) 4

Heapsort example: Insert(8) 4

Heapsort example: Insert(1) 4

Heapsort example: Insert(1) 1

Heapsort example: Insert(3) 1

Heapsort example

Heapsort example: Insert(5) 1

Heapsort example: Insert(7) 1

Heapsort example: Insert(9) 1

Heapsort example: Now extract the items one at a time 1

Heapsort example: Extract-Min( ) 9

Heapsort example

Heapsort example: Extract-Min( ) 7

Heapsort example

Heapsort example: Extract-Min( ) 01

Heapsort example

Heapsort example: Extract-Min( ) 9

Heapsort example

Heapsort example: Extract-Min( ) 7

Heapsort example

Heapsort example: Extract-Min( ) 9

Heapsort example

Heapsort example: Extract-Min( )

Heapsort example

Heapsort example: Extract-Min( ) 9

Heapsort example: Extract-Min( ) 01

Heapsort example: Extract-Min( )

 A Priority queue is an abstract data structure that supports two operations: Insert and Extract-Min.
 If priority queues are implemented using heaps, then these two operations are supported in time.
 Heapsort takes time, which is as efficient as merge sort and quicksort.

Exercise on merging k sorted arrays
 Suppose that you have k sorted arrays, each with n elements, and you want to combine them into a single sorted array of kn elements
 First strategy: Recall the procedure for merging two sorted arrays used in the “combine” step of merge-sort. Using this procedure, we merge the first two arrays, then merge in the third, then merge in the fourth, and so on. Analyze the worst-case running time of this algorithm, in terms of k and n.
 The cost of merging two sorted arrays of size n into an array of size 2n is 2n. So the first merge step takes 2n, the second step 3n and so on. The final step takes kn. The total running time is 2n + 3n + ∙ ∙ ∙ + kn = O(k2n).

Exercise on merging k sorted arrays (D&C)
 Suppose that you have k sorted arrays, each with n elements, and you want to combine them into a single sorted array of kn elements
 Second strategy: Design a more efficient solution using divide and conquer, and analyze its running time.
 Divide recursively k sorted arrays into two parts, each with k/2 arrays. When the subproblems have been solved, we get two sorted arrays of size kn/2 to merge.
 The merge step is the same as in merge sort and has cost kn. So the recurrence is T(k) = 2T(k/2) + kn. Thus, T(k) = O(knlogk).

Recursion Tree D&C merging k sorted arrays
… … …
𝑇(𝑘/2𝑖) 𝑇(𝑘/2𝑖)
… … …
𝑇 𝑛 =𝑘+𝑘𝑛𝑙𝑜𝑔𝑘=𝑂 𝑘𝑛𝑙𝑜𝑔𝑘

Exercise on merging k sorted arrays (Heaps)
 Suppose that you have k sorted arrays, each with n elements, and you want to combine them into a single sorted array of kn elements
 Third strategy: Design another efficient solution based on the min-heap implementation of priority queues.
 Insert the first element of each array into an empty min- heap. Apply extract-min to get the smallest item in the min-heap, followed by inserting the next item of the array that the previous item belongs to. Repeat doing this until all items have been inserted into and extracted from the min-heap.
 Since, at any time, the size of the min-heap is at most k, each min-heap operation takes O(logk). Each of the kn items is being inserted and extracted exactly once, so the total running time is O(knlogk)

Sometimes priority queues need to support another operation
called Decrease-Key
 Decrease-Key: decreases the value of one specified element
 Decrease-Key is used in later algorithms, e.g., in Dijkstra’s algorithm for finding Shortest Path Trees
How can heaps be modified to support Decrease-Key in time?

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts