In các phần tử K lớn nhất trong một đống nhất định trong O (K * log (K))?

Question

Với vấn đề sau đây, tôi không hoàn toàn chắc chắn với các giải pháp hiện tại của tôi:

Câu hỏi:

Cho một đống tối đa với n yếu tố, được lưu trữ trong một mảng A, là nó có thể in tất cả các phần tử K lớn nhất trong O(K*log(K))?

câu trả lời của tôi:

Vâng, đó là, kể từ khi tìm kiếm một yếu tố đòi hỏi O(log(K)), do đó làm điều đó

cho K yếu tố sẽ mất O(K * log(K)) thời gian chạy.

Answer 1

Điều này có thể ở mức tối đa vì bạn chỉ in các phần tử từ cây, chứ không phải trích xuất chúng.

Bắt đầu bằng cách xác định phần tử tối đa, nằm ở nút gốc. Tạo một con trỏ tới một nút và thêm nó vào một danh sách "tối đa" trống rỗng.Sau đó, đối với mỗi giá trị k, hãy thực hiện các bước sau trong vòng lặp.

• Bật phần tử tối đa từ danh sách, lấy O (1).
• In giá trị của nó, lấy O (1).
• Chèn từng phần tử con của phần tử tối đa này vào danh sách. Duy trì sắp xếp khi bạn chèn chúng, lấy thời gian O (log (size of list)). Kích thước tối đa của danh sách này, vì chúng tôi đang thực hiện k lần lặp này, là kích thước chi nhánh * k. Do đó, bước này có thời gian O (log (k)).

Tổng cộng, sau đó, thời gian chạy là O (klog (k)), như mong muốn.

Answer 2

Thật vậy, quá dễ dàng, việc giải nén phần tử tối đa là O(log(N)) trong đó N là kích thước của vùng heap. và N≠K.

Tôi sẽ thêm tìm kiếm yếu tố ngẫu nhiên là O(N) chứ không phải O(Log(N)), nhưng trong trường hợp này, chúng tôi muốn trích xuất giá thầu CPC

Answer 3

Tìm kiếm một phần tử có kích thước N không phải là O (K). Đầu tiên, nó không có nghĩa là phức tạp về thời gian để tìm kiếm một yếu tố phụ thuộc vào số phần tử bạn đang cố gắng trích xuất (đó là những gì mà K đại diện). Ngoài ra, không có những thứ như tìm kiếm trong một heap — trừ khi bạn đếm tìm kiếm tiêu chuẩn ở mọi phần tử trong O (N).

Tuy nhiên, việc tìm phần tử lớn nhất trong heap là O (1) theo thiết kế (tôi rõ ràng cho rằng đó là phần lớn nhất, do đó phần tử tối đa nằm ở đầu heap) và loại bỏ phần tử lớn nhất từ một đống kích thước N là O (log (N)) (thay thế nó bằng một phần tử lá, và có lá đó thấm ngược trở lại đống).

Vì vậy, trích xuất các phần tử K từ một đống, và trả về đống các phần tử không được trích xuất, sẽ mất thời gian O (K & middot; log (N)).

Điều gì xảy ra nếu bạn trích xuất các phần tử K không phá hủy từ vùng heap? Bạn có thể làm điều này bằng cách giữ một heap-of-heaps (trong đó giá trị của một đống là giá trị của phần tử tối đa của nó). Ban đầu, heap-of-heap này chỉ chứa một phần tử (heap gốc). Để trích xuất phần tử tối đa tiếp theo, bạn giải nén heap trên cùng, trích xuất phần tử trên cùng của nó (đó là phần tử tối đa) và sau đó lắp lại hai phần con trở lại vào vùng heap-of-heap.

Điều này sẽ tăng heap-of-heap của mỗi loại bỏ (loại bỏ một, thêm hai), có nghĩa là nó sẽ không bao giờ chứa nhiều hơn K elements, và do đó, một-thêm-hai sẽ mất O (log (K)). Lặp lại điều này, và bạn nhận được một thuật toán O (K & middot; log (K)) thực sự trả về các phần tử K trên cùng, nhưng không thể trả về đống các phần tử không được trích xuất.

Answer 4

It is a simple and elegant algorithm to get first k elements of a max heap in k log(k) time. 

steps:- 

1.construct another max heap name it auxiliary heap 
2.add root element of main heap to auxiliary heap 
3.pop out the element from auxiliary heap and add it's 2 children to the heap 
4.do step 2 and 3 till k elements have been popped out from auxiliary heap. Add the popped element's children to the auxiliary heap. 

Answer 5

Tôi thấy các câu trả lời khác khó hiểu nên tôi quyết định giải thích nó bằng một ví dụ thực tế. Giả sử heap ban đầu là kích thước N và bạn muốn tìm các phần tử lớn nhất thứ k, Giải pháp này có thời gian O (klogk) và không gian O (k).

10 
/\ 
    5 3 
/\ /\ 
4 1 2 0 
Original Heap, N = 7 

Muốn tìm phần tử lớn thứ 5. k = 5 Lưu ý: Trong heap mới, bạn cần lưu con trỏ vào heap gốc. Điều này có nghĩa là bạn không xóa hoặc thay đổi vùng gốc. Vùng heap ban đầu là chỉ đọc. Do đó, bạn không bao giờ phải thực hiện bất kỳ thao tác nào yêu cầu thời gian O (logN).

Cho x 'là con trỏ đến giá trị x trong vùng gốc.

Iteration 1: Nhận con trỏ nút gốc của thành đống mới

Bước 1: Thêm con trỏ đến nút 10

10' 
New Heap, size = 1, root = 10', root->left = 5, root right->3 

In phần tử lớn nhất 1 = 10

lặp 2: Tham khảo heap ban đầu và chèn cả hai đó là trẻ em vào heap mới. (Lưu trữ các con trỏ cho họ và không phải là giá trị bản thân). Lý do bạn muốn lưu trữ con trỏ là để bạn có thể truy cập chúng trong O (1) từ heap ban đầu sau đó để tìm kiếm con của chúng thay vì O (N) để tìm kiếm nơi mà giá trị đó nằm trong heap gốc.

Bước 2a: Tìm con trái của nút gốc của vùng heap mới từ vùng gốc. Thêm một con trỏ cho con trái (trong trường hợp này là 5 ') vào heap mới.

10' 
/
5' 
New Heap, size = 2, root = 10', root->left = 5, root right->3 

Bước 2b: Tìm con phải của nút gốc của heap mới từ vùng gốc. Thêm một con trỏ cho con trái (trong trường hợp này là 3 ') vào heap mới.

10' 
/\ 
5' 3' 
New Heap, size = 3, root = 10', root->left = 5, root right->3 

Bước 2c: Xóa nút gốc khỏi Heap mới. (Swap nút max với đúng nhất rời, loại bỏ nút gốc và bong bóng xuống gốc hiện tại để duy trì sở hữu đống)

10' swap 3' remove & bubble 5'  
/\  => /\  =>  /
5' 3'  5' 10'    3' 
New Heap, size = 2, root = 5', root->left = 4, root right->1 

In phần tử lớn nhất thứ 2 = 5

Bước 3a: Nhìn cho con trái của gốc nút của heap mới từ heap ban đầu. Thêm một con trỏ cho con trái (trong trường hợp này là 4 ') vào heap mới.

5' 
/\ 
3' 4' 
New Heap, size = 3, root = 5', root->left = 4, root right->1 

Bước 3b: Tìm con phải của nút gốc của heap mới từ vùng gốc. Thêm con trỏ cho con bên trái (trong trường hợp này là 1 ') vào heap mới.

5' 
/\ 
    3' 4' 
/
1' 
New Heap, size = 4, root = 5', root->left = 4, root right->1 

Bước 3c: Xóa nút gốc khỏi Heap mới. (Nút Swap max (5 ') New Heap với quyền của mình nhất khởi hành từ đống gốc (1') từ Heap mới, loại bỏ nút gốc và bong bóng xuống gốc hiện tại để duy trì sở hữu đống)

5'  Swap  1' remove & bubble  4' 
/\   => /\  =>   /\ 
    3' 4'   3' 4'     3' 1' 
/    /
1'    5' 
New Heap, size = 3, root = 4', root->left = NULL, root right->NULL 

In phần tử lớn thứ 3 = 4

Bước 4a & Bước 4b không làm gì vì nút gốc không có bất kỳ trẻ nào trong trường hợp này từ vùng gốc.

Bước 4c: Xóa nút gốc khỏi Heap mới. (nút max Swap với đúng nhất rời, loại bỏ nút gốc và bong bóng xuống gốc hiện tại để duy trì sở hữu đống ở New Heap)

4'  Swap  1' remove & bubble  3' 
/\   => /\  =>   /
    3' 1'   3' 4'     1' 
New Heap, size = 2, root = 3', root->left = 2, root right->0 

In phần tử lớn nhất 4 = 3

Bước 5a: Tìm trái con của nút gốc của heap mới từ heap gốc. Thêm con trỏ cho con trái (trong trường hợp này là 2 ') vào heap mới.

 3' 
    /\ 
    1' 2' 
New Heap, size = 3, root = 3', root->left = 2, root right->0 

Bước 5b: Tìm con phải của nút gốc của heap mới từ vùng gốc. Thêm con trỏ cho con trái (trong trường hợp này là 0 ') vào heap mới.

 3' 
    /\ 
    1' 2' 
/
0' 
New Heap, size = 4, root = 3', root->left = 2, root right->0 

Bước 5c: Xóa nút gốc khỏi Heap mới. (Hoán đổi nút tối đa (3 ') với phần lớn nhất của nó từ heap gốc (là 0') trong Heap Mới, loại bỏ nút gốc và bong bóng xuống gốc hiện tại để duy trì tài sản heap trong New Heap)

 3' Swap  0' Remove & Bubble  2' 
    /\  =>  /\   =>   /\ 
    1' 2'   1' 2'     1' 0' 
/    /
0'    3' 
New Heap, size = 3, root = 2', root->left = NULL, root->right = NULL 

In phần tử lớn thứ 5 = 2

Cuối cùng, vì chúng ta đã trải qua k lần lặp, k = 5. Bây giờ chúng ta có thể trích xuất giá trị của phần tử gốc từ vùng mới. Trong trường hợp này, giá trị là 2. Do đó, chúng tôi đã tìm thấy giá trị lớn thứ k từ heap gốc.

Thời gian phức tạp, T (N, k) = O (klogk) Space phức tạp, S (N, k) = O (k)

Hope this helps!

Sớm Chee Loong,

Đại học Toronto.