Định nghĩa và cấu trúc
Một pairing heap có thể là một heap rỗng, hoặc một pairing tree bao gồm một phần tử gốc và một danh sách có thể rỗng các pairing tree.
Tính chất thứ tự heap yêu cầu cha của bất kỳ nút nào không lớn hơn chính nút đó.
Mô tả sau xem xét một heap thuần hàm (purely functional) không hỗ trợ thao tác decrease-key.
type PairingTree[Element] = Heap(element: Element, subheaps: List[PairingTree[Element]])
type PairingHeap[Element] = Empty | PairingTree[Element]Hai loại Pairing Heap
Pairing heap tồn tại dưới hai dạng – min pairing heap và max pairing heap. Min pairing heap dùng khi cần biểu diễn hàng đợi ưu tiên nhỏ nhất (min priority queue), max pairing heap dùng cho hàng đợi ưu tiên lớn nhất. Theo thảo luận về heap và cây leftist, chúng ta thảo luận rõ ràng về max pairing heap ở đây. Min pairing heap có thể suy diễn tương tự.
Một max pairing heap đơn giản là một max tree.
Hình dưới minh họa bốn max pairing heap. Lưu ý pairing heap không yêu cầu phải là cây nhị phân.
