Một đống ghép nối được định nghĩa là một loại cấu trúc dữ liệu đống với việc triển khai tương đối dễ dàng và hiệu suất khấu hao thực tế tuyệt vời.
Ghép cặp heap là cấu trúc cây đa đường được sắp xếp theo thứ tự đống và có thể được ký hiệu là đống Fibonacci đơn giản hóa.
Chúng được coi là "lựa chọn mạnh mẽ" để triển khai các Thuật toán như Thuật toán MST của Prim và hỗ trợ các hoạt động sau (giả sử là min-heap) -
- tối thiểu tìm thấy - Hàm này chịu trách nhiệm trả về phần tử trên cùng của heap.
- meld − Hàm này có nhiệm vụ so sánh hai phần tử gốc, phần tử nhỏ hơn vẫn là phần tử gốc của kết quả, phần tử lớn hơn và cây con của nó được thêm vào dưới dạng con của phần tử gốc này.
- chèn - Hàm này chịu trách nhiệm tạo một heap mới cho phần tử được chèn và kết hợp với heap ban đầu.
- phím giảm (tùy chọn) - Chức năng này có nhiệm vụ xóa cây con gốc ở khóa bị giảm, thay thế khóa bằng khóa nhỏ hơn, sau đó ghép kết quả lại vào heap.
- xóa tối thiểu - Chức năng này có nhiệm vụ loại bỏ gốc và thực hiện lặp lại các phép ghép của các cây con của nó cho đến khi còn lại một cây. Nhiều chiến lược hợp nhất khác nhau được áp dụng.
- Mỗi nút có một con trỏ hướng tới nút con bên trái và nút con bên trái hướng tới nút anh chị em tiếp theo của nút đó.
- Ví dụ về Ghép cặp Heap được đưa ra bên dưới -
Việc phân tích độ phức tạp về thời gian của các đống ghép nối chủ yếu được lấy cảm hứng từ phân tích cây ghép. Thời gian phân bổ trên mỗi lần xóa tối thiểu được coi là O (log n), và các hoạt động tìm tối thiểu, kết hợp và chèn chạy trong thời gian phân bổ O (1).