Tại sao nên sử dụng đống thay vì cây nhị phân khi triển khai hàng đợi ưu tiên?

Question

Dường như với tôi rằng lợi thế duy nhất của đống trên cây nhị phân là tìm mục nhỏ nhất trong heap phức tạp của O (1) thay vì O (log (2) n) trong cây nhị phân.

Khi triển khai hàng đợi ưu tiên, bạn cần phải xóa từng mục nhỏ nhất khỏi cấu trúc dữ liệu. xóa mục nhỏ nhất khỏi cây và cả đống được thực hiện trong độ phức tạp của O (log (2) n). Althogh xóa mục khỏi cây có thể phức tạp hơn. Xóa mục không có trẻ em một cách vô cùng đơn giản.

Câu hỏi của tôi là tại sao sử dụng đống thay vì cây nhị phân (điều này đơn giản hơn trong trường hợp này) khi triển khai hàng đợi ưu tiên?

Answer 1

tệ nhất trường hợp phức tạp trong trường hợp cây nhị phân sẽ là O (n) khi cây nhị phân hội tụ thành một mảng trong khi trong heap nó vẫn là O (log (n)). bạn có thể sử dụng cây nhị phân cân bằng như màu đỏ đen hoặc AVl nhưng sau đó nó trở nên phức tạp hơn và đòi hỏi nhiều bộ nhớ hơn.

Answer 2

Trước hết có các cây nhị phân khác nhau (một số trong số chúng khá khó khăn, một số chỉ cung cấp trung bình O(log n)) và heap là một trong số chúng.

Thứ hai: trong khi các hoạt động trên hầu hết các cây là O(log n), chúng phức tạp hơn, có yếu tố không đổi.

Heap cần bộ nhớ bổ sung liên tục, trong khi cây thường cần lưu trữ con trỏ trong mỗi nút.

Bằng cách này, đống là khá dễ dàng và chỉ sử dụng mảng (Tôi không chắc rằng nếu nó được thực hiện theo cách này trong Java, nhưng tôi nghĩ vậy)

Answer 3

Heaps thường là đơn giản hơn để triển khai thực hiện so với cây nhị phân cân bằng chính xác. Ngoài ra, chúng đòi hỏi ít chi phí bộ nhớ hơn (các phần tử có thể được lưu trữ trực tiếp trong một mảng, mà không cần phải phân bổ các nút cây và con trỏ và mọi thứ), hiệu năng cao hơn (phần lớn là do bộ nhớ của việc sử dụng một mảng liền kề) ... sẽ không bạn sử dụng chúng?

Answer 4

lựa chọn đầu tiên của bạn nên phụ thuộc vào mô hình truy cập mong đợi, và bao nhiêu dữ liệu bạn có thể sẽ lưu trữ: ...

• nếu không bao giờ có nhiều dữ liệu (n ít hơn 30, nói), một mảng unsorted sẽ được sử dụng tốt;
• nếu bạn gần như không bao giờ thêm, xóa hoặc cập nhật, một mảng được sắp xếp sẽ bị phạt;
• nếu n nhỏ hơn 1 triệu và bạn chỉ tìm kiếm phần tử hàng đầu (xếp hạng đầu tiên hoặc cuối cùng), heaps sẽ hoạt động tốt (đặc biệt nếu bạn thường xuyên cập nhật các phần tử đã chọn) một cách ngẫu nhiên, giống như bạn làm trong một hàng đợi LRU (ít được sử dụng gần đây nhất) cho bộ nhớ cache, vì trung bình một bản cập nhật là O (1), chứ không phải O (log (n)))
• nếu n nhỏ hơn 1 triệu, và bạn không chắc chắn mình sẽ tìm kiếm gì trong số , một cây cân bằng (nói, đỏ đen hoặc AVL) sẽ ổn;
• nếu n lớn (1 triệu trở lên), bạn có thể tốt hơn với b-tree hoặc một trie (hiệu suất của cây nhị phân cân bằng có xu hướng "rơi khỏi vách đá" khi n lớn đủ: truy cập bộ nhớ có xu hướng quá phân tán và bộ nhớ cache nhớ thực sự bắt đầu bị tổn thương)

...nhưng tôi khuyên bạn nên để tùy chọn mở càng tốt, để bạn có thể đánh dấu ít nhất một trong các lựa chọn thay thế và chuyển sang tùy chọn đó, nếu nó hoạt động tốt hơn. Trong hai mươi năm qua, tôi đã chỉ làm việc trên hai ứng dụng mà heaps là sự lựa chọn tốt nhất cho bất cứ điều gì (một lần cho một LRU, và một lần trong một ứng dụng nghiên cứu hoạt động khó chịu, khôi phục lại độ nhạy với k-chiều ngẫu nhiên bị nhiễu loạn hypercubes, nơi mà hầu hết các tế bào trong hypercube xuất hiện trong k khác nhau heaps và bộ nhớ là ở phí bảo hiểm). Tuy nhiên, trong hai lần đó, họ thực hiện tốt hơn nhiều so với các lựa chọn thay thế: nghĩa đen nhanh hơn hàng chục lần so với cây cân bằng hoặc cây b. Đối với vấn đề hypercube mà tôi đã đề cập trong đoạn cuối, đội trưởng của tôi nghĩ rằng cây đỏ đen sẽ hoạt động tốt hơn đống, nhưng điểm chuẩn cho thấy cây đỏ đen chậm hơn nhiều (như tôi nhớ lại, chúng là khoảng hai mươi lần chậm hơn), và mặc dù b-cây đã nhanh hơn đáng kể, heaps đánh bại họ thoải mái quá.

Tính năng quan trọng của heap, trong cả hai trường hợp tôi đã đề cập ở trên, không phải là O (1) tra cứu giá trị tối thiểu, mà là O (1) thời gian cập nhật trung bình cho một phần tử được chọn ngẫu nhiên .

-James Barbetti (Vâng, tôi nghĩ rằng tôi đã. Nhưng hình ảnh xác thực không ngừng nói với tôi rằng tôi không phải là người)

Answer 5

Nếu bạn sử dụng một phát hiện hoặc hoạt động tìm kiếm rất nhiều sau đó một cây nhị phân cân đối được ưa thích. Mã phân đoạn đoạn đường sử dụng cây cân bằng thay vì đống vì lý do này.