একটি পেয়ারিং হিপ বা তখন একটি খালি হিপ হতে পারে, অথবা একটি রুট এলিমেন্ট এবং একটি সম্ভাব্য খালি পেয়ারিং ট্রির লিস্ট ধারণকারী একটি পেয়ারিং ট্রি হতে পারে।
হিপ অর্ডারিং প্রোপার্টি অনুযায়ী যেকোনো নোডের প্যারেন্ট সেই নোড থেকে কম হবে।
নিচের বর্ণনা একটি পিউরলি ফাংশনাল হিপ বিবেচনা করে যা decrease-key অপারেশন সাপোর্ট করে না।
type PairingTree[Element] = Heap(element: Element, subheaps: List[PairingTree[Element]]) type PairingHeap[Element] = Empty | PairingTree[Element]
পেয়ারিং হিপ দুটি ধরনের হয়—মিন পেয়ারিং হিপ এবং ম্যাক্স পেয়ারিং হিপ। মিন পেয়ারিং হিপ তখন ব্যবহৃত হয় যখন আমরা একটি মিন প্রায়োরিটি কিউ রিপ্রেজেন্ট করতে চাই, এবং ম্যাক্স পেয়ারিং হিপ ম্যাক্স প্রায়োরিটি কিউর জন্য ব্যবহৃত হয়। টেক্সটে হিপ ও লेफটিস্ট ট্রি নিয়ে আমাদের আলোচনানুযায়ী, এখানে আমরা স্পষ্টভাবে ম্যাক্স পেয়ারিং হিপ আলোচনা করছি। মিন পেয়ারিং হিপ аналগাস হতে পারে।
একটি ম্যাক্স পেয়ারিং হিপকে সহজে একটি ম্যাক্স ট্রি হিসেবে ডিফাইন করা যায়।
নিচে চারটি ম্যাক্স পেয়ারিং হিপ দেখানো হয়েছে। লক্ষ্য করুন যে পেয়ারিং হিপ বাইনারি ট্রি হওয়া বাধ্যতামূলক নয়।
