Khác biệt giữa các bản “Sắp xếp vun đống”

n
Thêm mô phỏng thuật toán vun đống
(Sửa đổi mã theo cấu trúc dữ liệu để có thể áp dụng trong nhiều bài toán khác nhau và nhiều dự án lớn.)
n (Thêm mô phỏng thuật toán vun đống)
[[Tập tin:Heap Sort.gif|nhỏ|Mô phỏng thuật toán sắp xếp vun đống]]
'''Sắp xếp vun đống''' (''Heapsort'') dựa trên một [[cấu trúc dữ liệu]] được gọi là [[đống nhị phân]] (''binary heap''), gọi đơn giản là đống. Trong mục này chỉ nói về đống trong bài toán sắp xếp.
 
==Đống (Heap)==
* [[Tập tin:Tree array.PNG|nhỏ|230px|phải|Ví dụ về mảng và cây nhị phân tương ứng]]Mỗi mảng ''a''[1..n] có thể xem như một [[cây (lý thuyết đồ thị)|cây]] nhị phân gần đầy (có trọng số là các giá trị của mảng), với gốc ở phần tử thứ nhất, con bên trái của đỉnh ''a''[i] là ''a''[2*i] con bên phải là ''a''[2*i+1] (nếu mảng bắt đầu từ 1 còn nếu mảng bắt đầu từ 0 thì 2 con là ''a''[2*i+1] và ''a''[2*i+2]) (nếu 2*''i''<=''n'' hoặc 2*''i''+1<=''n'', khi đó các phần tử có chỉ số lớn hơn <math>int\left(\frac n 2 \right)</math> không có con, do đó là [[lá (lý thuyết đồ thị)|lá]]).
* [[Tập tin:Dong.PNG|nhỏ|230px|phải|Ví dụ mảng (45,23,35,13,15,12,15,7,9) là một đống]]
 
** Một cây nhị phân, được gọi là đống cực đại nếu khóa của mọi nút không nhỏ hơn khóa các con của nó. Khi biểu diễn một mảng ''a[]'' bởi một cây nhi phân theo thứ tự tự nhiên điều đó nghĩa là ''a''[i]>=''a''[2*i] và ''a''[i]>=''a''[2*i+1] với mọi ''i'' =1..int(n/2). Ta cũng sẽ gọi mảng như vậy là đống. Như vậy trong đống ''a''[1] (ứng với gốc của cây) là phần tử lớn nhất. Mảng bất kỳ chỉ có một phần tử luôn luôn là một đống.
25

lần sửa đổi