Пирамидті іріктеу. (2 сағат)

Пирамидті сұрыптау Дж. Уильямс ғалымымен 1964 жылы ұсынылды. Бұл алгоритм массивтің кез келген элементтерін сұрыптауға арналған; оған қажетті қосымша жады көлемі берілген деректерге тәуелді емес. Алгоритмнің жұмыс істеу уақыты–орташа жағдайда, және ең жаман жағдайда және ең үздік жағдайда бірдей болады.

Берілген дәрісте бұл алгоритмнің базалық нұсқасы қарастырылатын болады, бұл алгоритмның жылдамдығы жоғары емес. Жылдамдықтары жоғарырақ алгоритмдердің нұсқаларын сәз Интернетте «Heap sort modification» типті сұраныс арқылы таба аласыз.

Пирамида hL…hR кілттерінің тізілімі болып анықталады, сонда

hi<=h2i и hi<=h2i+l, для i=L,…, R/2.

Басқа сөзбен айтсақ, пирамиданы 3 қасиеті бар, биіктігі h, екілік ағаш деп анықтауға болады :

• әр соңғы шыңның биіктігі h немесе h‑1;

•әр h биіктігі бар соңғы шың кез-келген h‑1 биіктігі бар соңғы шыңның сол жағында орналасады;

• кез-келген шыңның мәні оның артынан келе жатқан шыңның мәнінен артық болады.

Алгоритмнің идеясын жазбалайық.

• 
  Пирамида — екілік ағаш, мұнда әр элементтің мәні астында тұрған элементтің мәнінен үлкен немесе оған тең болады.
  
• 
  Ағашты кез келген элементтермен толықтырып, оны пирамидаға айналдырып жеңіл түрде сұрыптауға болады.
  
• 
  Пирамиданың ең үлкен мәні пирамиданың ең жоғары сатысынды тұрады.
  
• 
  Шыңдағы, яғни, ең улкен элементті, алып тастаймызда нәтижеде шығатын массивтың ең соңына қоямыз.
  
• 
  Шыңдағы элементтің орнына ең төменгі сатыдағы элементті қоямыз.
  
• 
  Пирамиданы қалыптастырамыз (жаңадан сұрыптаймыз).
  
• 
  Қалған элементтердің ішіндегі ең үлкен элементті тағыда пирамиданың шыңына қоямыз. Тағыда оны алыпт тастаймызда массивтің соңғы элементтің алдынғы позициясына қоямыз
  
• 
  Пирамида қосымша орын алусыз бастапқы массивте сақталады. Пирамидының көлемі кішірее бере, ол массивтің кішірек бөлігіне ие бола береді, ал нәтиже пирамидадан бос қалған орындарға массивтың аяғынан бастап жазыла береді.