Bạn có thể đọc bản dịch bằng các ngôn ngữ khác: English
Trong khoa học máy tính, một cây heap là một cấu trúc dữ liệu dựa trên cây đặc biệt được thiết kế để thỏa mãn thuộc tính cây heap mô tả dưới đây.
Trong một heap tối thiểu, nếu P là một nút cha của C, thì khóa (giá trị) của P phải nhỏ hơn hoặc bằng khóa của C.
Tạo với okso.app
Trong một heap tối đa, khóa của P phải lớn hơn hoặc bằng khóa của C.
Nút ở "đỉnh" của heap mà không có nút cha được gọi là nút gốc.
Dưới đây là phức tạp thời gian của các cấu trúc dữ liệu heap khác nhau. Tên hàm giả sử một heap tối đa.
| Hoạt Động | tìm-max | xóa-max | chèn | tăng-khóa | hợp |
|---|---|---|---|---|---|
| Nhị Phân | Θ(1) |
Θ(log n) |
O(log n) |
O(log n) |
Θ(n) |
| Leftist | Θ(1) |
Θ(log n) |
Θ(log n) |
O(log n) |
Θ(log n) |
| Hình thái nhị phân | Θ(1) |
Θ(log n) |
Θ(1) |
O(log n) |
O(log n) |
| Hình thái Fibonacci | Θ(1) |
Θ(log n) |
Θ(1) |
Θ(1) |
Θ(1) |
| Hình thái Pairing | Θ(1) |
Θ(log n) |
Θ(1) |
o(log n) |
Θ(1) |
| Brodal | Θ(1) |
Θ(log n) |
Θ(1) |
Θ(1) |
Θ(1) |
| Xếp hạng-Pairing | Θ(1) |
Θ(log n) |
Θ(1) |
Θ(1) |
Θ(1) |
| Fibonacci nghiêm ngặt | Θ(1) |
Θ(log n) |
Θ(1) |
Θ(1) |
Θ(1) |
| 2-3 heap | O(log n) |
O(log n) |
O(log n) |
Θ(1) |
? |
Trong đó:
- tìm-max (hoặc tìm-min): tìm một phần tử tối đa của heap tối đa hoặc một phần tử tối thiểu của heap tối thiểu, tương ứng (còn được gọi là đỉnh)
- xóa-max (hoặc xóa-min): loại bỏ nút gốc của heap tối đa (hoặc heap tối thiểu), tương ứng
- chèn: thêm một khóa mới vào heap (còn được gọi là đẩy)
- tăng-khóa hoặc giảm-khóa: cập nhật một khóa trong heap tối đa hoặc tối thiểu, tương ứng
- hợp: kết hợp hai heap để tạo ra một heap mới hợp lệ chứa tất cả các phần tử của cả hai, phá hủy các heap gốc.
Trong kho lưu trữ này, MaxHeap.js và MinHeap.js là các ví dụ về heap Nhị phân.
- MaxHeap.js và MinHeap.js
- MaxHeapAdhoc.js và MinHeapAdhoc.js - Phiên bản tối giản (tùy ý) của cấu trúc dữ liệu MinHeap/MaxHeap không có các phụ thuộc bên ngoài và dễ dàng sao chép và sử dụng trong quá trình phỏng vấn lập trình nếu được phép bởi người phỏng vấn (vì nhiều cấu trúc dữ liệu trong JS thiếu).