cấu trúc dữ liệu để trích xuất trung bình và yếu tố nhỏ nhất 2 trong thời gian O (LGN)

Question

Tôi cần phải tìm một cấu trúc dữ liệu đáp ứng các yêu cầu:

• thể xây dựng nó từ một danh sách các mục n trong thời gian O (n)
• chèn một mục mất O (LGN)
• chiết xuất trung bình phải mất O (LGN)
• giải nén mục nhỏ thứ 2 mất O (LGN)

trong ba r đầu tiên equirements, công trình này: giữ n/2 mục nhỏ nhất trong một heap tối đa và n/2 lớn nhất trong một heap min. Rễ của những đống đó sẽ là trung bình dưới/trên.

Nhưng tôi bị mắc kẹt với yêu cầu thứ tư. Bất kỳ ý tưởng?

Answer 1

Giữ n/2 mục lớn nhất trong một đống nhỏ. Đối với các mục nhỏ nhất n/2 duy trì một cặp đống tối đa và tối thiểu. Heaps trong cặp này được tăng cường với chỉ số của cùng một phần tử trong đống ghép nối, để bất kỳ sửa đổi heap cập nhật chỉ mục trong đống ghép nối cho tất cả các mục đã di chuyển.

giải thích đống Paired

Cả đống chứa chính xác cùng một tập hợp các mặt hàng. Cùng với mỗi mục có một trường chỉ mục bổ sung. Khi heap được sửa đổi, một số mục có thể thay đổi địa điểm của chúng. Nếu một mục được di chuyển từ chỉ mục x đến chỉ mục y, mục tương ứng trong vùng ghép nối phải được thông báo. Mục tương ứng này có thể dễ dàng định vị trong vùng ghép đôi với trường chỉ mục của mục đã di chuyển. Và nội dung của trường chỉ mục của mục tương ứng được thay đổi từ x thành y. Điều này cho phép tất cả các mục heap biết chính xác vị trí các cặp của chúng. Giữ các mục tương ứng trong cả hai heaps in-sync cho phép (trong khi trích xuất mục lớn nhất từ ​​heap tối đa hoặc mục nhỏ nhất thứ 2 từ min heap) trích xuất mục tương ứng từ đống ghép nối. Và việc giữ đống đồng bộ hóa không làm tăng bất kỳ yêu cầu phức tạp nào.