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

n
clean up, replaced: ) → ) (2) using AWB
n (→‎Xem thêm: using AWB)
n (clean up, replaced: ) → ) (2) using AWB)
 
==Đố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]]
 
 
==Ứng dụng==
*Ngoài giải thuật sắp xếp vun đống, cấu trúc đống còn được ứng dụng trong nhiều giải thuật khác, khi cần lấy ra nhanh chóng các phần tử lớn nhất (hoặc nhỏ nhất) của một dãy phần tử, chẳng hạn trong [[hàng đợi có ưu tiên]] trong đó tiêu chuẩn ưu tiên là có khóa lớn nhất (hoặc nhỏ nhất). Có thể tìm thấy điều đó trong giải thuật tìm bộ [[mã hóa Huffman|mã Huffman]] cho một bảng tần số của các kí tự.(tacgia )
 
==Xem thêm==