Кіріспе
Скив-қам (немесе өзін-өзі реттеуші қам) – екілік ағаш түрінде жүзеге асырылған қам дерек құрылымы. Скив-қамдар екілік қамдарға қарағанда жылдам біріктірілу мүмкіндігі арқасында тиімді. Екілік қамдардан өзгеше, құрылымдық шектеулер жоқ, сондықтан ағаштың биіктігі логарифмдік болатынына кепілдік берілмейді. Тек екі талап орындалуы керек: жалпы қам тәртібі сақталуы тиіс. Кез келген операция (қосу, ең кішіні алу, біріктіру) екі скив-қамда арнайы скив-қам біріктіру арқылы жасалуы керек. Скив-қам – екі қамды біріктіргенде біріктіру жолындағы барлық түйіндерді шартсыз ауыстыру арқылы тепе-теңдікті сақтауға тырысатын сол жақты қамның өзін-өзі реттеу түрі. (Біріктіру операциясы мәндерді қосу және жою кезінде де қолданылады.) Құрылымдық шектеулердің болмауы скив-қамның тиімсіздігін көрсетуі мүмкін. Алайда, амортизациялық күрделілік талдауы, скив-қамдағы барлық операциялар O(log n) уақытында орындалатынын көрсетуге болады. Шындығында, алтын қатынасты φ деп белгілесек, нақты амортизацияланған күрделілік logφ n (шамамен 1.44 log2 n) болады.
The general heap order must be enforced
Every operation (add, remove min, merge) on two skew heaps must be done using a special skew heap merge. A skew heap is a self adjusting form of a leftist heap which attempts to maintain balance by unconditionally swapping all nodes in the merge path when merging two heaps. (The merge operation is also used when adding and removing values.) With no structural constraints, it may seem that a skew heap would be horribly inefficient. However, amortized complexity analysis can be used to demonstrate that all operations on a skew heap can be done in O(log n). In fact, with denoting the golden ratio, the exact amortized complexity is known to be logφ n (approximately 1.44 log2 n).
Қайталанбайтын бірігу
Сонымен қатар, рекурсияны қолданбайтын, көбірек сөздерді қажет ететін және бастапқыда сұрыптауды талап ететін тәсіл бар. Әрбір қанатын кесіп, әрбір үйіндіні кіші ағаштарға бөліңіз. (Түбір түйінен оң түйінді бөліп, оң баласын жеке кіші ағашқа айналдырыңыз.) Бұл нәтижесінде түбірі тек сол жақ балаға немесе баласы жоқ ағаштар жиынтығы пайда болады. Әрбір кіші ағаштың түбір түйінінің мәні бойынша кіші ағаштарды өсу ретімен сұрыптаңыз. Егер әлі де бірнеше кіші ағаштар болса, соңғы екеуін қайта-қайта біріктіріңіз (оңнан солға қарай). Егер екінші соңғы кіші ағаштың түбірі сол жақ балаға ие болса, оны оң жақ балаға ауыстырыңыз. Соңғы кіші ағаштың түбірін екінші кіші ағаштың сол жақ баласы ретінде қосыңыз.
Құндылықтарды қосу
Скив үйіндісіне мән қосу, бастапқы ағашпен бір түйінді ағашты біріктіруге ұқсас.
Құндылықтарды алып тастау
Қорымдағы бірінші мәнді жою тамырды жойып, оның баламашаларын біріктіру арқылы жасалуы мүмкін.