Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 5: Sắp xếp - Nguyễn Khánh Phương

nhất của max-heap!”
 5 2
 MAX-Heap
 Đống là cây nhị phân được điền theo thứ tự
Cài đặt đống bởi mảng (array)
• Đống được cài đặt bởi mảng A.
 – Gốc của cây là A[1]
 – Con trái của A[i] = A[2*i]
 – Con phải của A[i] = A[2*i + 1]
 – Cha của A[i] = A[ i/2 ]
 – Số lượng phần tử Heapsize[A] ≤ length[A]
• Các phần tử thuộc mảng con A[( n/2 +1) .. n] 
 đều là lá của cây
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Hai dạng đống
• Đống max (Max Heap) – phần tử lớn nhất ở gốc
 – Sử dụng để sắp xếp mảng theo thứ tự tăng dần
 – Có tính chất max-heap: với mọi nút i, ngoại trừ gốc: 
 A[PARENT(i)] ≥ A[i]
• Đống min (Min Heap) – phần tử nhỏ nhất ở gốc
 – Sử dụng để sắp xếp mảng theo thứ tự giảm dần
 – Có tính chất min-heap: với mọi nút i, ngoại trừ gốc:
 A[PARENT(i)] ≤ A[i]
Các phép toán đối với đống (Operations on Heaps)
• Khôi phục tính chất max-heap (Vun lại đống)
 – MAX-HEAPIFY
• Tạo max-heap từ một mảng không được sắp xếp
 – BUILD-MAX-HEAP
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Các phép toán đối với đống (Operations on Heaps)
• Khôi phục tính chất max-heap (Vun lại đống)
 – MAX-HEAPIFY
• Tạo max-heap từ một mảng không được sắp xếp
 – BUILD-MAX-HEAP
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Max-heap: MAX-HEAPIFY
• Giả sử có nút i với giá trị bé hơn con của nó (đã giả thiết là cây con trái và cây con phải
 của nút i đều là max-heaps), để loại bỏ sự vi phạm tính chất max-heap này, ta gọi thủ tục
 MAX-HEAPIFY tiến hành thực hiện cách bước sau:
 – Đổi chỗ nút i với nút con lớn hơn
 – Di chuyển xuống theo cây
 – Tiếp tục quá trình cho đến khi nút không còn bé hơn con
 i 4 14 14
 Swap 4 và 14 Swap 4 và 8
 14 7 4 i 7 8 7
 2 8 1 2 4 1
 2 8 1
 Không phải max-heap vì: Không phải max-heap vì: Max heap
 Tính chất Max-heap bị vi phạm Tính chất Max-heap bị vi phạm
 tại nút i tại nút i
MAX-HEAPIFY: khôi phục tính chất Max-Heap
• Giảthiết: Alg: MAX-HEAPIFY(A, i, n)
 – Cây con trái và phải 1. l ← LEFT(i)
 của nút i đều là max-
 heaps 2. r ← RIGHT(i)
 – A[i] A[i]
 hơn các con của nó
 4. then largest ←l
 5. else largest ←i
 6. if r ≤ n and A[r] > A[largest]
 7. then largest ←r
 8. if largest i
 9. then exchange A[i] ↔ A[largest]
 10. MAX-HEAPIFY(A, largest, n)
Ví dụ
 A[2]  A[4]
 A[2] vi phạm tính chất max-heap A[4] vi phạm tính chất max-heap
 GỌI: MAX-HEAPIFY(A, 2, 10);
 Để khôi phục tính chất max-heap
 A[4]  A[9] MAX-HEAPIFY(A,2,10) kết
 thúc; và ta thu được một Max 
 heap
 Tính chất max-heap được khôi phục
Các phép toán đối với đống (Operations on Heaps)
• Khôi phục tính chất max-heap (Vun lại đống)
 – MAX-HEAPIFY
• Tạo max-heap từ một mảng không được sắp xếp
 – BUILD-MAX-HEAP
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Tạo max-heap từ một mảng không được sắp xếp: BUILD-MAX-HEAP
Biến đổi mảng A[1  n] thành max-heap (n = length[A]) sao cho các phần tử
thuộc mảng con A[( n/2 +1) .. n] là các lá:
• Do đó, để tạo đống, ta chỉ cần áp dụng MAX-HEAPIFY đối với các phần tử
 từ 1 đến n/2 
 Alg: BUILD-MAX-HEAP(A)
 1. n = length[A]
 Áp dụng MAX-HEAPIFY trên các
 2. for i ← n/2 downto 1 nút trong A[ n/2 ]  A[1]
 1
 3. do MAX-HEAPIFY(A, i, n) 4
 2 3
 1 3
 4 56 7
 4 1 3 2 16 9 1014 8 7
 2 16 9 10
 A: 8 910
 14 8 7
Ví dụ: cho mảng A, xây dựng max-heap biểu diễn A
 A: 4 1 3 2 16 9 1014 8 7
Khởi tạo:
(không phải max-heap) 1
 4
 Để chuyển cây này thành max-heap: ta cần áp
 2 3 dụng MAX-HEAPIFY trên tất cả các nút trong: 
 1 3 
 4 56 7 A[ n/2 ] A[1]
 2 16 9 10
 8 910 10/2 = 5
 14 8 7
 i = 5: Gọi MAX-HEAPIFY(A,5,10)
 1
 4
 2 3 A[5] = 16 không lớn hơn các con của nó (A[10]=7)
 1 3
 4 56 7 ok; không cần làm gì
 2 16 9 10
 8 910
 14 8 7
 Ví dụ: cho mảng A, xây dựng max-heap biểu diễn A
 A: 4 1 3 2 16 9 1014 8 7
 i = 4: Gọi MAX-HEAPIFY(A,4,10) i = 3: Gọi MAX-HEAPIFY(A,3,10) i = 2: Gọi MAX-HEAPIFY(A,2,10)
 1 1
 1
 4 4
 4
 A[4]  A[8] A[3]  A[7]
 2 3 2 3
 2 3
 1 3 1 3
 1 10
 4 56 7 4 56 7
 4 56 7
 2 16 9 10 14 16 9 10
 8 910 8 910 14 16 9 3
 8 910
14 8 7 2 8 7
 2 8 7
 i = 1: Gọi MAX-HEAPIFY(A,1,10)
 1 1
 4 4
 A[2]  A[5] 2 3 A[5]  A[10] 2 3
 16 10 16 10
 4 56 7 4 56 7
 14 5 9 3 14 7 9 3
 8 910 8 910
 2 8 7 2 8 5
Ví dụ: cho mảng A, xây dựng max-heap biểu diễn A
 A: 4 1 3 2 16 9 1014 8 7
 i = 1: Gọi MAX-HEAPIFY(A,1,10)
 1 1
 4 16
 2 3 A[1]  A[2] 2 3 A[2]  A[4]
 16 10 4 10
 4 56 7 4 56 7
 14 7 9 3 14 7 9 3
 8 910 8 910
 2 8 1 2 8 1
 1 1
 16 16
 2 3 A[4]  A[9] 2 3 Max heap
 14 10 14 10
 4 56 7 4 56 7
 4 7 9 3 8 7 9 3
 8 910 8 910
 2 8 1 2 4 1
6. Sắp xếp vun đống (Heap sort)
6.1. Cấu trúc dữ liệu đống (heap)
6.2. Sắp xếp vun đống
6.3. Hàng đợi có ưu tiên (priority queue)
 NGUYỄN KHÁNH PHƯƠNG 146
 Bộ môn KHMT – ĐHBK HN
Sắp xếp vun đống
Mục đích: Sắp xếp mảng theo thứ tự tăng dần nhờ sử dụng đống
Sơ đồ thuật toán:
1. Sử dụng BUILD-MAX-HEAP để tạo đống max-heap từ mảng đã cho A[1 . . n]. 
2. Vì phần tử lớn nhất của mảng được lưu ở gốc A[1]: ta cần di chuyển nó về đúng vị trí
 của nó trong mảng: đổi chỗ gốc với phần tử cuối cùng của mảng A[n]. 
3. Loại bỏ nút cuối n ra khỏi đống max-heap bằng cách giảm kích thước đống đi 1.
4. Phần tử mới đang nằm ở gốc có thể vi phạm tính chất max-heap. Vì vậy, cần gọi thủ tục
 MAX-HEAPIFY đối với nút gốc mới này để khôi phục tính chất max-heap. 
Lặp lại quá trình (2-3-4) cho đến khi đống chỉ còn lại 1 nút
Alg: HEAPSORT(A)
 Alg: HEAPSORT(A)
 1. BUILD-MAX-HEAP(A) O(n)
 2. n = length[A]
 3. for i ← n downto 2 {
 4. exchange A[1] ↔ A[i] n-1 times
 5. MAX-HEAPIFY(A, 1, i - 1) O(log2n)
 6. }
 Thời gian tính: O(nlog2n)
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Ví dụ: sắp xếp mảng A theo thứ tự tăng dần
A: 16 4 7 1 12 19
 A[1] A[2] A[3] A[4] A[5] A[6]
• Bước 1: Biểu diễn mảng A bởi cây nhị phân đầy đủ
 1 16
 2 4 3 7
 4 1 5 12 19 6
• Bước 2: Gọi HEAPSORT(A):
 1. Gọi BUILD-MAX-HEAP(A): để đưa cây này về đống max-heap
 149
Ví dụ: sắp xếp mảng A theo thứ tự tăng dần
• Bước 2: Gọi HEAPSORT(A):
 – BUILD-MAX-HEAP(A)
 • n = 6
 1 16
 Để đưa cây này về dạng đống max-heap: ta cần áp
 2 4 3 7
 dụng MAX-HEAPIFY trên tất cả các nút trong: 
 A[ n/2 ] A[1]
 6/2 = 3
 4 1 5 12 19 6
 NGUYỄN KHÁNH PHƯƠNG 150
 Bộ môn KHMT – ĐHBK HN
 BUILD-MAX-HEAP(A): 
 gọi MAX-HEAPIFY trên tất cả các nút trong
 i = 3: Gọi MAX-HEAPIFY(A,3,6) i = 2: Gọi MAX-HEAPIFY(A,2,6)
 1
 16 1 16
 2
 4 3 7 A[3]  A[6] 2 4 3 19 A[2]  A[5]
 4 1 512 7 6
 4 1 5 12 7 6
 i = 1: Gọi MAX-HEAPIFY(A,1,6)
 1 16 1 19
 2 12 3 19 A[1]  A[3] 2 12 3 16 Max heap
4 1 5 4 7 6 4 1 5 4 7 6
 151
Ví dụ: sắp xếp mảng A theo thứ tự tăng dần
A: 16 4 7 1 12 19
 A[1] A[2] A[3] A[4] A[5] A[6]
• Bước 1: Biểu diễn mảng A thành cây nhị phân đầy đủ
• Bước 2: Gọi HEAPSORT(A):
 1. Gọi BUILD-MAX-HEAP(A): để biến đổi cây này về đống max-heap
 152
Ví dụ: sắp xếp mảng A theo thứ tự tăng dần
A: 16 4 7 1 12 19
 A[1] A[2] A[3] A[4] A[5] A[6]
• Bước 1: Biểu diễn mảng A thành cây nhị phân đầy đủ
• Bước 2: Gọi HEAPSORT(A):
 1. Gọi BUILD-MAX-HEAP(A): để biến đổi cây này về đống max-heap
 2. Thực hiện bước lines 3-6
 153
 Ví dụ:
 Max-heap: 1 7
 i=6:
 1 19
 A[1]  A[6]
 2 12 3 16
 2 12 3 16 Đổi chỗ phần
 tử cuỗi cùng
 và gốc cho
 nhau Xóa nút lớn nhất
4 1 5 4 7 6 4 1 5 4 19 6 19
 Gọi MAX-HEAPIFY(A,1,5)
 1 7
 Array A: Sorted:
 2 12 3 16 7 12 16 1 4 19
 4 1 5 4 19 6 154
Ví dụ:
 Gọi MAX-HEAPIFY(A,1,5)
 để khôi phục tính chất max-heap
 1 7 1 16
 A[1]  A[3] i=5:
 2 12 3 16 2 12 3 7
 A[1]  A[5]
 Đổi chỗ phần
 tử cuốivàgốc
 4
4 1 5 4 19 1 5 4 19 cho nhau
 6 6
 Gọi MAX-HEAPIFY(A,1,4)
 1 4
 Array A: Sorted:
 2 12 3 7 4 12 7 1 16 19
 Xóa phầntử lớn nhất
 16
 4
 1 5 16 19 6 155
 Ví dụ
 Gọi MAX-HEAPIFY(A,1,4)
 để khôi phục tính chất max-heap
 1 4 1 12
 A[1]  A[2]
 2 12 3 7 2 4 3 7 i=4:
 A[1]  A[4]
 Đổi chỗ phần
 tử cuốivàgốc
4 1 5 16 19 4 1 5 16 19
 6 6 cho nhau
 Gọi MAX-HEAPIFY(A,1,3)
 1 1
 Array A: Sorted:
 2 4 3 7 1 4 7 12 16 19
 Xóa phầntử lớn nhất
 12
 4 12 5 16 19 6 156
 Ví dụ:
 Call MAX-HEAPIFY(A,1,3)
 để khôi phục tính chất max-heap
 1 1 1 7
 A[1]  A[3]
 2 4 3 7 2 4 3 1 i=3:
 A[1]  A[3]
 Đổi chỗ phần
 tử cuốivàgốc
4 12 5 16 19 4
 12 5 16 19 cho nhau
 6 6
 Call MAX-HEAPIFY(A,1,2)
 1 1
 Array A: Sorted:
 2 4 3 7 1 4 7 12 16 19
 Xóa phầntử lớn nhất
 7
 4 12 5 16 19 6 157
 Ví dụ:
 Gọi MAX-HEAPIFY(A,1,2)
 để khôi phục tính chất max-heap
 1 1 1 4
 A[1]  A[2]
 2 4 3 7 2 1 3 7 i=2:
 A[1]  A[2]
 Đổi chỗ phần
 tử cuốivàgốc
4 12 5 16 19 4
 12 5 16 19 cho nhau
 6 6
 1 1
 Mảng A: Sorted:
 2 4 3 7 1 4 7 12 16 19
 Xóa phầntử lớn nhất
 4
 Thu đượcmảng A đượcxếp theo thứ
 4 12 5 16 19 tự tăng dần
 6 158
Bài tập 1: sử dụng thuật toán heap sort 
• Sắp xếp các phần tử của mảng A theo thứ tự tăng dần
 A: 7 4 3 1 2
 1 2 3 4 5
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Bài tập 2: sử dụng thuật toán heap sort 
• Sắp xếp các phần tử của mảng A theo thứ tự tăng dần
 A: 26 24 20 18 17 19 13 12 14 11
 1 2 3 4 5 6 7 8 9 10
 26
 24 20
 18 17 19 13
 12 14 11
6. Sắp xếp vun đống (Heap sort)
6.1. Cấu trúc dữ liệu đống (heap)
6.2. Sắp xếp vun đống
6.3. Hàng đợi có ưu tiên (priority queue)
 NGUYỄN KHÁNH PHƯƠNG 161
 Bộ môn KHMT – ĐHBK HN
6.3. Hàng đợi có ưu tiên - Priority Queues
• Cho tập S thường xuyên biến động, mỗi phần tử x được gán với một giá trị gọi là khoá
 (hay độ ưu tiên). Cần một cấu trúc dữ liệu hỗ trợ hiệu quả các thao tác chính sau:
 – Insert(S, x): Bổ sung phần tử x vào S
 – Max(S): trả lại phần tử lớn nhất
 – Extract-Max(S): loại bỏ và trả lại phần tử lớn nhất
 – Increase-Key(S,x,k): tăng khoá của x thành k
Cấu trúc dữ liệu đáp ứng các yêu cầu đó là hàng đợi có ưu tiên.
Hàng đợi có ưu tiên có thể tổ chức nhờ sử dụng cấu trúc dữ liệu đống để cất giữ các khoá.
• Chú ý: Có thể thay "max" bởi "min" .
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Các phép toán đối với hàng đợi có ưu tiên
Operations on Priority Queues
• Hàng đợi có ưu tiên (max) có các phép toán cơ bản sau:
 – Insert(S, x): bổ sung phần tử x vào tập S
 – Extract-Max(S): loại bỏ và trả lại phần tử của S với khoá lớn nhất
 – Maximum(S): trả lại phần tử của S với khoá lớn nhất
 – Increase-Key(S, x, k): tăng giá trị của khoá của phần tử x lên thành k 
 (Giả sử k ≥ khoá hiện tại của x)
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Các phép toán đối với hàng đợi có ưu tiên
Operations on Priority Queues
• Hàng đợi có ưu tiên (min) có các phép toán cơ bản sau:
 – Insert(S, x): bổ sung phần tử x vào tập S
 – Extract-Min(S): loại bỏ và trả lại phần tử của S với khoá nhỏ nhất
 – Minimum(S): trả lại phần tử của S với khoá nhỏ nhất
 – Decrease-Key(S, x, k): giảm giá trị của khoá của phần tử x xuống
 thành k (Giả sử k khoá hiện tại của x)
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Phép toán HEAP-MAXIMUM
Chức năng: Trả lại phần tử lớn nhất của đống
Alg: Heap-Maximum(A)
1. return A[1]
 Thời gian tính: O(1)
 Heap A:
 Heap-Maximum(A) trả lại 7
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Phép toán Heap-Extract-Max
Chức năng: Trả lại phần tử lớn nhất và loại bỏ nó khỏi đống
Thuật toán: 
 – Hoán đổi gốc với phần tử cuối cùng (A[0] và A[n-1])
 – Giảm kích thước của đống đi 1
 – Gọi Max-Heapify đối với gốc mới trên đống có kích thước n-1
 Đống A: Gốc là phần tử lớn nhất
Ví dụ: Heap-Extract-Max
 16 1
 14 10 max = 16 14 10
 8 7 9 3 8 7 9 3
 2 4 1 2 4
 Kích thước đống giảm đi 1
 Thực hiện Max-Heapify(A, 1, n-1) 14
 8 10
 4 7 9 3
 2 1
Heap-Extract-Max
 Alg: Heap-Extract-Max(A, n)
 1. if n < 1
 2. then error “heap underflow”
 3. max ← A[1]
 4. A[1] ← A[n]
 5. Max-Heapify(A, 1, n-1) // Vun lại đống
 6. return max
 Thời gian tính: O(log n)
Phép toán Heap-Increase-Key
• Chức năng: Tăng giá trị khoá của phần tử i trong đống
• Thuật toán:
 – Tăng khoá của A[i] thành giá trị mới
 – Nếu tính chất max-heap bị vi phạm: di chuyển theo đường đến gốc để
 tìm chỗ thích hợp cho khoá mới bị tăng này
 16
 14 10
 8 7 9 3
 i
 Key [i] ← 15 2 4 1
 NGUYỄN KHÁNH PHƯƠNG
 169 Bộ môn KHMT – ĐHBK HN
Ví dụ: Heap-Increase-Key
 16 16
 14 10 14 10
 8 7 9 3 8 7 9 3
 i i
 2 4 1 2 15 1
 Key [i ] ← 15
 16 16
 i
 14 10 15 10
 i
 15 7 9 3 14 7 9 3
 2 8 1 2 8 1
Heap-Increase-Key
Alg: Heap-Increase-Key(A, i, key)
1. if key < A[i]
2. then error “khoá mới nhỏ hơn khoá hiện tại”
3. A[i] ← key
4. while i > 1 and A[parent(i)] < A[i]
5. do hoán đổi A[i] ↔ A[parent(i)]
 16
6. i← parent(i)
 14 10
 8 7 9 3
• Thời gian tính: O(log n) i
 2 4 1
 Key [i] ← 15
Ví dụ: Heap-Increase-Key (1)
 1
 16
 2 3
 14 10
 4 5 6 7
 8 7 9 3
 8 9 10
 2 4 1
 increase 4 to 15
Ví dụ: Heap-Increase-Key (2)
 1
 16
 2 3
 14 10
 4 5 6 7
 8 7 9 3
 8 9
 10
 2 15 1
 thay 4 bởi 15
Ví dụ: Heap-Increase-Key (3)
 1
 16
 2 3
 14 10
 4 5 6 7
 15 7 9 3
 8 9
 10
 2 8 1
 đi ngược lên để sửa vi phạm
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Ví dụ: Heap-Increase-Key (4)
 1
 16
 2 3
 15 10
 4 5 6 7
 14 7 9 3
 8 9
 10
 2 8 1
 đã đặt đúng vị trí
Phép toán Max-Heap-Insert
• Chức năng: Chèn một phần tử
 mới vào max-heap 16
• Thuật toán:
 14 10
 – Mở rộng max-heap với một nút mới 8 7 9 3
 có khoá là - 2 4 1 - 
 – Gọi Heap-Increase-Key để tăng 16
 khoá của nút mới này thành giá trị
 của phần tử mới và vun lại đống 14 10
 8 7 9 3
 2 4 1 15
 NGUYỄN KHÁNH PHƯƠNG
 Bộ môn KHMT – ĐHBK HN
Ví dụ: Max-Heap-Insert
 Chèn giá trị 15: Tăng khoá thành 15
 - Bắt đầu với - Gọi Heap-Increase-Key với A[11] = 15
 16 16
 14 10 14 10
 8 7 9 3 8 7 9 3
 2 4 1 - 2 4 1 15
 16 Vun lại đống 16
 với phần tử 
 14 10 mới bổ sung 15 10
 8 15 9 3 8 14 9 3
 2 4 1 7 2 4 1 7
Max-Heap-Insert
Alg: Max-Heap-Insert(A, key, n)
1. heap-size[A] ← n + 1
2. A[n + 1] ← - 
 16
3. Heap-Increase-Key(A, n + 1, key)
 14 10
 8 7 9 3
 2 4 1 - 
 Running time: O(log n)
Tổng kết
• Chúng ta có thể thực hiện các phép toán sau đây với đống:
 Phép toán Thời gian tính
 – Max-Heapify O(log n)
 – Build-Max-Heap O(n)
 – Heap-Sort O(n log n)
 – Max-Heap-Insert O(log n)
 – Heap-Extract-Max O(log n)
 – Heap-Increase-Key O(log n)
 – Heap-Maximum O(1)
Cài đặt hàng đợi có ưu tiên bởi danh sách móc nối
• Priority Queues sử dụng heaps:
 – Tìm phần tử lớn nhất: Heap-Maximum O(1)
 – Lấy và loại phần tử lớn nhất: Heap-Extract-Max O(log n) 
 – Bổ sung phần tử mới: Heap-Insert O(logn)
 – Tăng giá trị phần tử: Heap-Increase-Key O(log n)
• Priority Queues sử dụng danh sách móc nối được sắp thứ tự:
 – Tìm phần tử lớn nhất: O(1)
 – Lấy và loại phần tử lớn nhất: O(1) 
 – Bổ sung phần tử mới: O(n)
 – Tăng giá trị phần tử: O(n)
 header
 15 8 3 NULL
Tổng kết: 
Các thuật toán sắp xếp dựa trên phép so sánh
 Name Average Worst In place Stable
 Bubble sort — O(n²) Yes Yes
 Selection sort O(n²) O(n²) Yes No
 Insertion sort O(n + d) O(n²) Yes Yes
 Merge sort O(n log n) O(n log n) No Yes
 Heapsort O(n log n) O(n log n) Yes No
 Quicksort O(n log n) O(n²) Yes No
 NGUYỄN KHÁNH PHƯƠNG
 181 Bộ môn KHMT – ĐHBK HN