[Học lại] Bài 6 - Heap Sort

! Sắp xếp vun đống

Chuỗi thì dài, đống thì cao. Vun chuỗi thành đống xong dàn ra thành chuỗi.

Đống giống kim tự tháp, có đỉnh và đáy. Đỉnh thì cao và nhọn, đâm cũng đau =))
Heap Sort về cơ bản giống Selection Sort. Tìm phần tử lớn nhất đưa lên cao và đưa về đầu mảng, làm tương tự cho các phần tử còn lại.

Nếu như vậy thì có gì cải tiến đâu nhỉ?

Có.

Trước tiên hãy xem một cái định nghĩa tưởng tượng sau nha.
Chúng ta có danh sách gồm 3 phần tử [a, b, c], 3 phần tử đó có thể xây thành một kim tự tháp giống như vầy.

(a)
/
(b) (c)

đỉnh là phần tử thứ 0, hai chân của nó là 1 và 2 tương đương với 2*0 + 1 và 2*0 + 2
Đống 4 phần tử: [a, b, c, d]

       (a)
      /   \
    (b)   (c)
   /
 (d)

Đống 5 phần tử: [a, b, c, d, e]

       (a)
      /   \
    (b)   (c)
   /   \
 (d)   (e)

Đống 6 phần tử: [a, b, c, d, e, f]

        (a)
      /     \
    (b)      (c)
   /   \     / 
 (d)   (e) (f)

Mô hình ở trên gọi là cây nhị phân hoàn chỉnh, tức là mỗi đỉnh đều có 2 chân (hoặc 0) ngoại trừ một cái cuối cùng (c).

Như vậy danh sách thông thường chính là cây nhị phân hoàn chỉnh.

Từ cái cây này, viết một cái giải thuật để đỉnh luôn lớn hơn (hoặc bé hơn) 2 cái chân - Heapify.
Cái kết quả sau khi heapify cây nhị phân gọi là đống nhị phân - Binary heap.

Dưới đây là mô tả cách xây đống có đỉnh lớn (max heap).

func heapify(_ input: inout [Int], _ rootIndex: Int)  {
    let largest = rootIndex
    let leftLeg = rootIndex * 2 + 1
    let rightLeg = rootIndex * 2 + 2
    
    //so trong 3 cai, root, left, right, cai nao lon nhat thi lay ra
    if leftLeg < input.count, input[leftLeg] > input[largest] {
        largest = leftLeg
    }
    if rightLeg < input.count, input[rightLeg] > input[largest] {
        largest = rightLeg
    }
    
    //dua cai lon nhat ve vi tri root, va de quy cho vi tri vua duoc hoan doi
    if largest != rootIndex {
        input.swapAt(rootIndex, largest)
        heapify(input, largest)
    }
}

Có heap rồi chúng ta sẽ thực hiện sort.

func heapSort(_ input: inout [Int]) -> [Int]{
    let count = input.count
    
    //heapify phải làm bottom up để đảm bảo lớn nhất được đưa từ dưới cùng lên đầu.
    for i in stride(from: count / 2 - 1, through: 0, by: -1) {
        heapify(&input, i)
    }
    
    var result: [Int] = [] //cho nay can improve de giam space complexity
    while input.count > 0 {
        result.append(input[0])
        input = Array(input.dropFirst())
        heapify(&input, 0)
    }
    
    return result
}

Heapify tốn O(logn) time vì qua mỗi bước heapify, số lượng phần tử cho bước tiếp theo bằng 1 nửa.

Sau khi có heap, chúng ta phải cắt đỉnh và heapify các phần tử còn lại, như vậy tốn O(n) cho việc cắt toàn bộ đỉnh sau mỗi lần heapify.

Lồng 2 cái lại O(nlogn)

Rõ ràng là nhanh hơn hẳng Selection Sort.
Voila!