Vun đống tại đỉnh thứ i

Nếu hai cây con gốc 2 * i và 2 * i + 1 đã là đống thì để cây con gốc i trở thành đống chỉ việc so sánh giá trị a[i] với giá trị lớn hơn trong hai giá trị a[2 * i] và a[2 * i + 1], nếu a[i] nhỏ hơn thì đổi chỗ chúng cho nhau. Nếu đổi chỗ cho a[2 * i], tiếp tục so sánh với con lớn hơn trong hai con của nó cho đên khi hoặc gặp đỉnh lá. (Thủ tục DownHeap trong giả mã dưới đây)

Vun một mảng thành đống

Để vun mảng a[1..n] thành đống ta vun từ dưới lên, bắt đầu từ phần tử a[j]với j =Int(n/2) ngược lên tới a[1]. (Thủ tục MakeHeap trong giả mã dưới đây) kho qua

Sắp xếp bằng vun đống

Đổi chỗ (Swap): Sau khi mảng a[1..n] đã là đống, lấy phần tử a[1] trên đỉnh của đống ra khỏi đống đặt vào vị trí cuối cùng n, và chuyển phần tử thứ cuối cùng a[n] lên đỉnh đống thì phần tử a[n] đã được đứng đúng vị trí.

Vun lại: Phần còn lại của mảng a[1..n-1] chỉ khác cấu trúc đống ở phần tử a[1]. Vun lại mảng này thành đống với n-1 phần tử.

Lặp: Tiếp tục với mảng a[1..n-1]. Quá trình dừng lại khi đống chỉ còn lại một phần tử.

Vun đống

• Vun cây gốc a[3] ta được mảng a=(2,3,7,6,4,1,5)
• Vun cây gốc a[2] ta được mảng a=(2,6,7,3,4,1,5)
• Vun cây gốc a[1] ta được mảng a=(7,6,5,3,4,1,2)
• Bây giờ a=(7,6,5,3,4,1,2) đã là đống.

Sắp xếp

• Đổi chỗ a[1] với a[7]: a=(2,6,5,3,4,1,7)

và vun lại mảng a[1..6] ta được mảng a=(6,4,5,3,2,1,7)

• Đổi chỗ a[1] với a[6]: a=(1,4,5,3,2,6,7)

và vun lại mảng a[1..5] ta được mảng a=(5,4,2,3,1,6,7)

• Đổi chỗ a[1] với a[5]: a=(1,4,2,3,5,6,7)

và vun lại mảng a[1..4] ta được mảng a=(4,3,2,1,5,6,7)

• Đổi chỗ a[1] với a[4]: a=(1,3,2,4,5,6,7)

và vun lại mảng a[1..3] ta được mảng a=(3,1,2,4,5,6,7)

• Đổi chỗ a[1] với a[3]: a=(2,1,3,4,5,6,7)

và vun lại mảng a[1..2] ta được mảng a=(2,1,3,4,5,6,7)

• Đổi chỗ a[1] với a[2]:a=(1,2,3,4,5,6,7)
• Mảng còn lại chỉ một phần tử. Quá trình sắp xếp đã xong.

==Mã giả==(DowHeap)

function heapSort(a[1..count], count) {     var int end := count      

MakeHeap(a,count)      while end > 0      swap(a[end], a[1])     end := end - 1     DownHeap(a, 1, end)      }     function MakeHeap(a, count) {     var int start := Int(count/2)     

while start > 0     DownHeap(a, start, count)     start := start - 1     }     

function DownHeap(a, start, count) {     var int i := start, j          while i * 2 <= count {     j := i * 2      if j+1 <= count and a[j] < a[j + 1]     j := j + 1     if a[i] < a[j]     swap(a[i], a[j])     i := j     else     return     }     }