tailieunhanh - 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. | Sắ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 : heap Các phần tử tốt nhất (xấu nhất) sẽ được dờ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 16 12 14 11 4 6 7 1 2 9 13 8 0 10 3 5 12 cha 11 Con (phần tử liên đới) 4 Con (phần tử liên đới) 12 > 11, 12 > 4 16 gốc 16 là giá trị lớn nhấ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 Phần tử cha của nó la a(k-1)/2 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 a0= 16 gốc a1=12 có 2 phần tử liên đới là a 2x1+1=a3 =11 a2x1+2=a4=4 a12=8 có phần tử cha nó là a(12-1)/2 =a5 =9 16 12 14 11 4 6 7 1 2 9 13 8 0 10 3 5 12 cha 4 16 gốc Cấu | Sắ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 : heap Các phần tử tốt nhất (xấu nhất) sẽ được dờ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 16 12 14 11 4 6 7 1 2 9 13 8 0 10 3 5 12 cha 11 Con (phần