Kiến trúc máy tính - P12-2

Chia sẻ: Lê Trung Thống | Ngày: | Loại File: PPT | Số trang:17

Thêm vào BST

Báo xấu

62
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giả sử rằng mức độ ứu tiên thể hiện bằng số • Cũng có thể là một đối tượng bất kỳ, nhưng chúng có thể so sánh được với nhau • Giá trị nhỏ nhất có mức ưu tiên cao nhất • Các giá trị khác là như nhau

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Kiến trúc máy tính - P12-2

Hàng đợi ưu tiên (Priority Queues) Sorting 1
Cấu trúc dữ liệu ưu tiên • Giả sử rằng mức độ ứu tiên thể hiện bằng số Cũng có thể là một đối tượng bất kỳ, nhưng • chúng có thể so sánh được với nhau • Giá trị nhỏ nhất có mức ưu tiên cao nhất Các giá trị khác là như nhau • Sorting 2
Hàng đợi ưu tiên (Priority queue) Là cấu trúc dữ liệu cho việc lưu trữ mọt tập các phần tử có ion of prioritized elements Hỗ trợ chèn thêm phần tử bất kỳ Hỗ trợ loại bỏ phần tử với mức ưu tiên cao nhất tại bất kỳ thời điểm nào. Không như những cấu trúc dữ liệu dựa trên địa chỉ (stacks queues) vì nó không định nghĩa vị trí cho người sử dụng Sorting 3
Cài đặt Bằng danh sách – Đơn giản nhưng không hiệu quả Bằng cây heap – hiệu quả hơn (thời gian yêu cầu là hàm log) Sorting 4
Hàng đợi ưu tiên ADT Một hàng đợi ưu tiên lưu trữ Thêm vào một số phương một tập các phần tử thức Mỗi phần tử là một cặp min()  trả lại phần tử có khóa nhỏ (key, value) nhất nhưng không loại bỏ nó Các phương thức chính của đi Hàng đợi ưu tiên ADT size(), isEmpty()  insert(k, x)  Chèn một phần tử với khóa k và giá trị x Các ứng dụng: removeMin()  Loại bỏ và trả lại phần tử có Các máy bay dự phòng  khóa nhỏ nhất Đấu giá  Thị trường chứng khoán  (Stock market) Sorting 5
Quan hệ thứ tự toàn phần Các khái niệm toán học Các khóa trong hàng về quan hệ thự tự ≤ đợi ưu tiên có thể là các đối tượng bất kỳ toàn phần và trên nó được định T/c phản xạ:  nghĩa một thứ tự x≤ x Hai phần tử phân biệt T/c phẩn đối xứng:  x ≤ y ∧y ≤ x ⇒ x = y trong một hàng đợi ưu tiên có thể có T/c bắc cầu:  x ≤ y ∧y ≤ z ⇒ x ≤ z khóa giống nhau Sorting 6
Phần tử ADT (§ 7.1.2) Một phần tử trong hàng Cài đặt trong C++ đợi ưu tiên đơn giản là template class Entry { Hàng đợi ưu tiên lưu trữ private: các cặp cho phép thêm Object1 value; vào và loại bỏ đi dựa Object2 key; trên các khóa. public: Các phương thức: Object key(); key(): trả lại giá trị khóa  Object value(); của phần tử }; value(): trả lại giá trị của  phần tử Sorting 7
Toán tử so sánh ADT (§ 7.1.2) A comparator encapsulates the action of comparing two objects according to a given total order relation The primary method of the A generic priority queue Comparator ADT: uses an auxiliary comparator compare(x, y): Returns an  The comparator is external integer i such that i b; an error occurs if a and b When the priority queue cannot be compared. needs to compare two keys, it uses its comparator Sorting 8
Example Comparator Lexicographic comparison of 2D points: Point objects: /** Comparator for 2D points under the /** Class representing a point in the standard lexicographic order. */ plane with integer coordinates */ public class Lexicographic implements public class Point2D { Comparator { protected int xc, yc; // coordinates int xa, ya, xb, yb; public Point2D(int x, int y) { public int compare(Object a, Object b) xc = x; throws ClassCastException { yc = y; xa = ((Point2D) a).getX(); } ya = ((Point2D) a).getY(); public int getX() { xb = ((Point2D) b).getX(); return xc; yb = ((Point2D) b).getY(); } if (xa != xb) public int getY() { return (xb xa); return yc; else } return (yb ya); } } } Sorting 9
Priority Queue Sorting (§ 7.1.4) We can use a priority Algorithm PQ-Sort(S, C) queue to sort a set of Input sequence S, comparator C comparable elements for the elements of S 1. Insert the elements one Output sequence S sorted in by one with a series of increasing order according to C insert operations P ← priority queue with 2. Remove the elements in comparator C sorted order with a series of removeMin operations while ¬S.isEmpty () The running time of this e ← S.removeFirst () sorting method depends on P.insert (e, 0) the priority queue while ¬P.isEmpty() implementation e ← P.removeMin().key() S.insertLast(e) Sorting 10
Sequencebased Priority Queue Implementation with an Implementation with a unsorted list sorted list 4 5 2 3 1 1 2 3 4 5 Performance: Performance: insert takes O(1) time  insert takes O(n) time since we can insert the  since we have to find the item at the beginning or place where to insert the end of the sequence item removeMin and min take  O(n) time since we have removeMin and min take  to traverse the entire O(1) time, since the sequence to find the smallest key is at the smallest key beginning Sorting 11
SelectionSort Selectionsort is the variation of PQsort where the priority queue is implemented with an unsorted sequence Running time of Selectionsort: 1. Inserting the elements into the priority queue with n insert operations takes O(n) time 2. Removing the elements in sorted order from the priority queue with n removeMin operations takes time proportional to 1 + 2 + …+ n Selectionsort runs in O(n2) time Sorting 12
SelectionSort Example Sequence S Priority Queue P Input: (7,4,8,2,5,3,9) () Phase 1 (a) (4,8,2,5,3,9) (7) (b) (8,2,5,3,9) (7,4) .. .. .. . . . (g) () (7,4,8,2,5,3,9) Phase 2 (a) (2) (7,4,8,5,3,9) (b) (2,3) (7,4,8,5,9) (c) (2,3,4) (7,8,5,9) (d) (2,3,4,5) (7,8,9) (e) (2,3,4,5,7) (8,9) (f) (2,3,4,5,7,8) (9) (g) (2,3,4,5,7,8,9) () Sorting 13
InsertionSort Insertionsort is the variation of PQsort where the priority queue is implemented with a sorted sequence Running time of Insertionsort: 1. Inserting the elements into the priority queue with n insert operations takes time proportional to 1 + 2 + …+ n 2. Removing the elements in sorted order from the priority queue with a series of n removeMin operations takes O(n) time Insertionsort runs in O(n2) time Sorting 14
InsertionSort Example Sequence S Priority queue P Input: (7,4,8,2,5,3,9) () Phase 1 (a) (4,8,2,5,3,9) (7) (b) (8,2,5,3,9) (4,7) (c) (2,5,3,9) (4,7,8) (d) (5,3,9) (2,4,7,8) (e) (3,9) (2,4,5,7,8) (f) (9) (2,3,4,5,7,8) (g) () (2,3,4,5,7,8,9) Phase 2 (a) (2) (3,4,5,7,8,9) (b) (2,3) (4,5,7,8,9) .. .. .. . . . (g) (2,3,4,5,7,8,9) () Sorting 15
Inplace Insertionsort 5 4 2 3 1 Instead of using an external data structure, we can implement 5 4 2 3 1 selectionsort and insertionsort inplace 4 5 2 3 1 A portion of the input sequence itself serves as 2 4 5 3 1 the priority queue For inplace insertionsort 2 3 4 5 1 We keep sorted the initial  portion of the sequence 1 2 3 4 5 We can use swaps  instead of modifying the sequence 1 2 3 4 5 Sorting 16
Break Sorting 17