Пирамидалы сұрыптау алгоритмі (Heap_sort) және оның ерекшеліктері

Сұрыптау (Сортировка; sorting) - массив элементтерін белгілі бір заңдылықпен орындарын ауыстырып реттеупроцессін айтамыз. Мысалы, сандар массивін өсуі, кемуі бойынша сұрыптау, жолдар массивін алфавит бойынша сұрыптау және тағы басқа. Сұрыптау мақсаты - көптеген сұрыпталған обьектінің ішінен белгілі бір элементті іздеуді оңайлату. Ақпараттық жүйелерде мәліметтерді сұрыптаудың маңызы өте зор.

Пирамидалық сұрыптау алгоритмі таңдаумен сұрыптау алгоритмі классына жатады. Бірақ бұл алгоритмнің өзінің ерекше қасиеті бар. Біріншіден, бастапқы массив бинарлы ағашпен беріледі. Бұл бинарлы ағаш құрылысы жағынан ерекшеленіп келеді, ондай ағаштарды толықтау ағаштар деп атайды.

Реттеу процессі екі этаптан тұрады. Бірінші этапта пирпмида тәріздес ағаш түзіледі. 1-этаптың нәтижесі келесі қасиетге ие пирамида болады: ағаш түбірінен қорытынды төбеге шығатын кез-келген жолында түйіндер кемімелі, дәлелдеп айтқанда өспелі емес ретпен орналасады; пирамида ағаштың жоғарыдан төменге, сол жақтан оңға қарай түзіледі. 2-этапта құрылған ағаш-пирамидасында түйінд/іне бекітілген.

Массив элементтеріне түпкілікті реттеуге пайдаланылады. Бұл этапта пирамиданың элементтерін реттеу бағыты пирамиданың оң жағынан солға қарай, төменнен жоғарыға қарай қажет болған жағдайда алмастырылады. Екінші этап бірінші фазадан тұрады. Бірінші фазада массивтің реттелмеген бөлігіндегі ағымдық максималды элемент (бұл фазада оның пирамиданың төбесінде орналасқанын ұмытпау керек) пирамиданың төменгі оң бұрышында орналасқан элементпен алмастырылады. Сөйтіп ағымдық максималды элемент реттелген массивте өзінің орнын табады. Осыдан кейін бұл максималды элемент те, оның орны да реттеуге қарастырылмайды. 2-этаптың 1-фазасының нәтижесінде пирамиданың төбесінде, яғни ағаштың түбірінде, оның құрылысының бұзылуына кездесеміз. Сондықтан 2-фазада өзгенген пирамиданың құрылысы қайтадан құралады.

static void HeapSort(int [] a)

{

int i;

int temp;

for (i = a.Length / 2 - 1; i >= 0; i--)

{

shiftDown(a, i, a.Length);

}

for (i = a.Length - 1; i >= 1; i--)

{

temp = a[0];

a[0] = a[i];

a[i] = temp;

shiftDown(a, 0, i);

}

}

static void shiftDown(int [] a, int i, int j)

{

bool done = false;

int maxChild;

int temp;

while ((i * 2 + 1 < j) && (!done))

{

if (i * 2 + 1 == j - 1)

maxChild = i * 2 + 1;

else if (a[i * 2 + 1] > a[i * 2 + 2])

maxChild = i * 2 + 1;

Else

maxChild = i * 2 + 2;

if (a[i] < a[maxChild])

{

temp = a[i];

a[i] = a[maxChild];

a[maxChild] = temp;

i = maxChild;

}

Else

{

done = true;

}

}

}