«Կույտային դասակարգում»–ի խմբագրումների տարբերություն

Content deleted Content added
չ փոխարինվեց: ն : → ն։ oգտվելով ԱՎԲ
չ Բոտ: կոսմետիկ փոփոխություններ
Տող 1.
[[պատկերՊատկեր:Sorting heapsort anim.gif|right|Անիմացված ալգորիթմի գծապատկեր]]
'''Կույտային դասակարգումը''' առաջարկվել է Ջ.Ուիլիամսի կողմից 1964 թվականին։ Կույտային դասակարգումը (անգլերեն Heapsort) դասակարգման ալգորիթմ է, որը աշխատում է վատ, միջին և լավ դեպքերում (այսինքն երաշխավորված է) Θ(n log n) օպերացիաների համար n հատ էլեմենտ տեսակավորելիս։ Ծառայող հիշողության օգտագործվող քանակը կախված չէ զանգվածի չափերից (այսինքն՝ O(1))։
Կարող է դիտվել որպես պղպջակային դասակարգման կատարելագործում, որում տարրը լողում է (min-heap), սուզվում (max-heap) բազմազան ուղիներով։
Տող 7.
# Ամեն ճյուղ ունի կամ d, կամ (d − 1) երկարություն, որտեղ d՝ ծառի առավելագույն երկարությունն է։
# Ցանկացած գագաթի արժեք մեծ է իր հաջորդից։
Դասակարգվող ծառի համար հարմար տվյալների կառուցվածքը այնպիսի Array զանգված է, որտեղ Array[1] արմատային տարր է, իսկ Array[i]-ի հաջորդողները Array[2i] և Array[2i+1]-ն են։
Դասակարգման ալգորիթմը բաղկացած է 2 հիմնական քայլերից։
 
Տող 20.
Այդ քայլը պահանջում է <math>O(n)</math> օպերացիաներ։
 
2. Արմատից պետք է ջնջել տարրերը մեկը մյուսի հետևից և վերակառուցել ծառը։ Այսինքն առաջին քայլում տեղափոխում ենք Array[1] ի Array[n]՝ ձևավորելով Array[1], Array[2], … , Array[n-1] դասակարգվող ծառը. Որից հետո վերադասավորում ենք Array[1] и Array[n-1], ձևավորում Array[1], Array[2], … , Array[n-2] դասակարգվող ծառում։.Պրոցեսը շարունակվում է այնքան ժամանակ մինչև դասակարգվող ծառում չի մնա ոչ մի տարր։ Այդ դեպքում Array[1], Array[2], … , Array[n] կարգավորող հաջորդականություն է։.
Այս քայլը պահանջում է O(nlogn) օպերացիաներ։
 
== Առավելությունները և թերությունները ==
 
Առավելություն.