Tại sao siftDown tốt hơn siftUp trong heapify?

Question

Để xây dựng một cây heap MAX, chúng tôi có thể siftDown hoặc siftUp, bằng cách chọn xuống chúng tôi bắt đầu từ gốc và so sánh nó với hai đứa con của nó, sau đó chúng tôi thay thế nó bằng phần tử lớn hơn của hai đứa trẻ, nếu cả hai trẻ nhỏ hơn sau đó chúng tôi dừng lại, nếu không chúng tôi tiếp tục chọn yếu tố đó cho đến khi chúng tôi đạt đến nút lá (hoặc tất nhiên một lần nữa, cho đến khi phần tử đó lớn hơn cả hai con của nó).

Bây giờ chúng ta chỉ cần thực hiện điều đó n/2 lần, vì số lá là n/2 và lá sẽ thỏa mãn thuộc tính vùng heap khi chúng ta kết thúc phần tử cuối cùng trên mức trước dấu cuối cùng (trước lá) vì vậy chúng tôi sẽ để lại với các yếu tố n/2 để heapify.

Bây giờ nếu chúng ta sử dụng siftUp, chúng ta sẽ bắt đầu với lá, và cuối cùng chúng ta sẽ cần phải heapify tất cả các yếu tố n.

Câu hỏi của tôi là: khi chúng tôi sử dụng siftDown, về cơ bản chúng tôi thực hiện hai so sánh (so sánh yếu tố với cả hai con), thay vì chỉ so sánh khi sử dụng siftUp, vì chúng tôi chỉ so sánh phần tử đó với một phần tử ? Nếu có, điều đó không có nghĩa là chúng ta đang tăng gấp đôi sự phức tạp và thực sự kết thúc với sự phức tạp chính xác giống như chọn lọc xuống?

Answer 1

Thực ra, việc xây dựng một đống với các cuộc gọi lặp lại siftDown có độ phức tạp là O(n) trong khi xây dựng nó với các cuộc gọi lặp lại siftUp có độ phức tạp là O(nlogn).

Điều này là do thực tế khi bạn sử dụng siftDown, thời gian được thực hiện bởi mỗi cuộc gọi giảm với độ sâu của nút vì các nút này gần với lá hơn. Khi bạn sử dụng siftUp, số lượng hoán đổi tăng với độ sâu của nút vì nếu bạn đang ở độ sâu đầy đủ, bạn có thể phải trao đổi tất cả các cách vào thư mục gốc. Vì số lượng các nút tăng theo cấp số nhân với độ sâu của cây, sử dụng siftUp mang lại một thuật toán đắt tiền hơn. Ngoài ra, nếu bạn đang sử dụng Max-heap để thực hiện một số loại sắp xếp nơi bạn bật phần tử tối đa của heap và sau đó phục hồi lại, việc thực hiện dễ dàng hơn bằng cách sử dụng siftDown là dễ dàng hơn. Bạn có thể phục hồi lại trong thời gian O(logn) bằng cách popping phần tử tối đa, đặt phần tử cuối cùng vào nút gốc (nút này trống vì bạn đã bật nó) và sau đó chọn nó xuống tất cả trở lại đúng vị trí của nó.