Sắp xếp vun đống

Sắp xếp vun đống - Heap sort • Khi tìm phần tử nhỏ nhất ở bước i, phương pháp sắp xếp chọn trực tiếp không tận dụng được các thông tin đã có được do các phép so sánh ở bước i-1. Vì lý do trên người ta tìm cách xây dựng một thuật toán sắp xếp có thể khắc phục nhược điểm này.
Nội dung trích xuất từ tài liệu:
Sắp xếp vun đốngSắp xếp vun đống Heap sort Sắp xếp vun đống - Heap sort• Khi tìm phần tử nhỏ nhất ở bước i, phương pháp sắp xếp chọn trực tiếp không tận dụng được các thông tin đã có được do các phép so sánh ở bước i-1. Vì lý do trên người ta tìm cách xây dựng một thuật toán sắp xếp có thể khắc phục nhược điểm này.• Mấu chôt để giải quyết vấn đề vừa nêu là phải tìm ra được một cấu trúc dữ liệu cho phép tích lũy các thông tin về sự so sánh giá trị các phần tử trong qua trình sắp xếp.• Giả sử dữ liệu cần sắp xếp được bố trí theo quan hệ so sánh và tạo thành sơ đồ dạng cây như sau : heapCác phần tử tốt nhất (xấu nhất) sẽ đượcdời lên trên Cấu trúc heap• Heap là một cấu trúc dữ liệu dạng hình cây có tính chất sau:• Mổi một phần tử sẽ có nhiều nhất 2 phần tử là con của nó (phần tử liên đới)• Bất kỳ Phần tử ở trên (cha) sẽ có giá trị lớn hơn giá trị 2 phần tử con của nó• Phần tử đầu (phần tử gốc) sẽ là phần tử có giá trị lớn nhất trong heap Cấu trúc heap gốc 16 cha 12 14 Con Con 11 4 9 13(phần tử liên đới) (phần tử liên đới) 7 6 2 1 0 8 3 10 5 16 l giá 12 n nh 12 >à11, trị lớ> 4 ất trong heap• Heap có các tính chất sau :• Tính chất 1 : Nếu al , al+1 ,al+2... , ar là một heap thì khi cắt bỏ một số phần tử ở hai đầu của heap, dãy con còn lại vẫn là một heap.• Tính chất 2 : Nếu a1 , a2 ,... , an là một heap thì phần tử a1 (đầu heap) luôn là phần tử lớn nhất trong heap.• Tính chất 3 : Mọi dãy al , al+1 ,al+2... , ar với 2l > r là một heap. Cấu trúc heap• Cài đặt cấu trúc heap bằng mảng a0, a1 ,... , ar thoả các quan hệ sau với mọi i ‫ﻴ‬ 0], r]: - ai > = a2i+1 - ai >= a2i+2 (a2i+1, a2i+2) là các cặp phần tử liên đới• phần tử a0 (đầu heap) luôn là phần tử lớn nhất trong heap.• Vậy ak có phần tử liên đới là a2k+1, a2k+2 gốc 16 cha 12 14 11 4 9 13 7 6 2 1 0 8 3 105 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1516 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 a0= 16  gốc a1=12 có 2 phần tử liên đới là a 2x1+1=a3 =11 a2x1+2=a4=4 Cấu trúc heap• Vấn đề cần quan tâm – Làm sao xây dựng heap – Thêm 1 phần tử – Xóa 1 phần tử phải đảm bảo tính chất heap Cấu trúc heap• Thêm 1 phần tử – Thêm vào cuối mảng  mất tính chất heap Cập nhật lại heap (upheap) Bước 1:tại k kiểm tra so với cha của nó (k1-1)/2 Nếu ak a(k-1)/2 đổi vị trí  bước 1 Cấu trúc heap 16• Thêm 15 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Cấu trúc heap 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 1516 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 150 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Cấu trúc heap 16 12 14 11 4 9 13 15 6 ...