Կույտային դասակարգում

Կույտային դասակարգումը առաջարկվել է Ջ. Ուիլիամսի կողմից 1964 թվականին։ Կույտային դասակարգումը (անգլ.՝ Heapsort) դասակարգման ալգորիթմ է, որն աշխատում է վատ, միջին և լավ դեպքերում (այսինքն երաշխավորված է) Θ(n log n) օպերացիաների համար n հատ էլեմենտ տեսակավորելիս։ Ծառայող հիշողության օգտագործվող քանակը կախված չէ զանգվածի չափերից (այսինքն՝ O(1))։
Կարող է դիտվել որպես պղպջակային դասակարգման կատարելագործում, որում տարրը լողում է (min-heap), սուզվում (max-heap) բազմազան ուղիներով։


== Ալգորիթմ ==
Կույտային դասակարգումը օգտագործում է դասակարգող ծառը։ Դա այն բինար ծառն է, որը կատարում է հետևյալ պայմանները.

Ամեն ճյուղ ունի կամ d, կամ (d − 1) երկարություն, որտեղ d՝ ծառի առավելագույն երկարությունն է։
Ցանկացած գագաթի արժեք մեծ է իր հաջորդից։Դասակարգվող ծառի համար հարմար տվյալների կառուցվածքը այնպիսի Array զանգված է, որտեղ Array[1] արմատային տարր է, իսկ Array[i]-ի հաջորդողները Array[2i] և Array[2i+1]-ն են։
Դասակարգման ալգորիթմը բաղկացած է 2 հիմնական քայլերից։
1. Դասավորում ենք զանգվածի տարրերը դասակարգվող ծառի տեսքով։

  
    
      
        A
        r
        r
        a
        y
        [
        i
        ]
        ≥
        A
        r
        r
        a
        y
        [
        2
        i
        ]
      
    
    {\displaystyle Array[i]\geq Array[2i]}
  

  
    
      
        A
        r
        r
        a
        y
        [
        i
        ]
        ≥
        A
        r
        r
        a
        y
        [
        2
        i
        +
        1
        ]
      
    
    {\displaystyle Array[i]\geq Array[2i+1]}
  
երբ 
  
    
      
        1
        ≤
        i
        <
        n
        
          /
        
        2
      
    
    {\displaystyle 1\leq i<n/2}
  .
Այդ քայլը պահանջում է 
  
    
      
        O
        (
        n
        )
      
    
    {\displaystyle O(n)}
   օպերացիաներ։
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) օպերացիաներ։


== Առավելությունները և թերությունները ==
Առավելություն.

ունի ապացուցված գնահատական վատ դեպքի համար 
  
    
      
        O
        (
        n
        log
        ⁡
        n
        )
      
    
    {\displaystyle O(n\log n)}
  .
պահանջում է ընդամենը O(1) լրացուցիչ հիշողություն (եթե ծառը կազմակերպենք այնպես, ինչպես վերևում է ցույց տրված)։Թերություններ.

դժվար է իրականացվում,
անկայուն է ՝կայունության ապահովման համար պետք է ընդլայնել բանալին,
գրեթե տեսակավորված զանգվածում աշխատում է այնքան ժամանակ, որքան քաոսային տվյալների վրա,
ընտրությունը ստիպված պետք է անել քաոսային ձևով զանգվածի ամբողջ երկարությամբ, այդ իսկ պատճառով ալգորիթմը վատ է զուգորդվում քեշավորված և ներմղված հիշողության հետ։O(n) հիշողության ծախսումը միաձուլման դասակարգման միջոցով ավելի արագ է (
  
    
      
        O
        (
        n
        ⋅
        log
        ⁡
        n
        )
      
    
    {\displaystyle O(n\cdot \log n)}
  )փոքր հաստատունով և հակված չէ անհաջող տվյալների պատճառով դեգրադացման։
Ալգորիթմի դժվարության պատճառով շահումը լինում է միայն մեծատառ n-ով։ Ոչ մեծատառ n-ի համար ավելի արագ է Շելլայի տեսակավորումը։]].


== Գրականություն ==
Ананий В. Левитин Глава 6. Метод преобразования: Пирамиды и пирамидальная сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 275-284. — ISBN 5-8459-0987-2
Կաղապար:Книга:CLRS


== Հղումներ ==
Пирамидальная сортировка Archived 2009-03-15 at the Wayback Machine. — подробное описание с иллюстрациями и примером реализации на C++. Приведён вывод оценок скорости работы алгоритма и измерение времени работы на реальной вычислительной системе.
Сортировка с помощью кучи (пирамидальная сортировка) Archived 2009-09-26 at the Wayback Machine. — доходчивое описание с иллюстрациями и примером реализации на Pascal.