Swap(pi, gtci)

pi = gtci

# heapify

for i in range((sl/2)-1, -1, -1):

Sift(i, sl)

# sort

for i in range(sl-1, 0, -1):

Swap(i, 0)

Sift(0, i)

static void HeapSort(int[] a)

{

Int i;

Int temp;

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

{

SiftDown(a, i, a.Length);

}

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

{

temp = a[0];

a[0] = a[i];

a[i] = temp;

SiftDown(a, 0, i - 1);

}

}

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

{

bool done = false;

Int maxChild;

Int temp;

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

{

if (i * 2 == j)

maxChild = i * 2;

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

maxChild = i * 2;

Else

maxChild = i * 2 + 1;

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

{

temp = a[i];

a[i] = a[maxChild];

a[maxChild] = temp;

i = maxChild;

}

Else

{

done = true;

}

}

}

Идея ал­го­рит­ма

Для то­го, что­бы про­яс­нить всё даль­ней­шее из­ло­же­ние, в двух сло­вах опи­шу идею ал­го­рит­ма.

Пи­ра­ми­да — дво­ич­ное де­ре­во, в ко­то­ром зна­че­ние каж­до­го эле­мен­та боль­ше ли­бо рав­но зна­че­ний до­чер­них эле­мен­тов.

За­пол­нив де­ре­во эле­мен­та­ми в про­из­воль­ном по­ряд­ке, мож­но лег­ко его от­сор­ти­ро­вать (лег­че, чем ис­ход­ный спи­сок эле­мен­тов), пре­вра­тив в пи­ра­ми­ду.

Са­мый боль­шой эле­мент пи­ра­ми­ды на­хо­дит­ся в её вер­ши­не.

От­де­ля­ем вер­шин­ный эле­мент, и за­пи­сы­ва­ем его в ко­нец ре­зуль­ти­рую­ще­го мас­си­ва.

На ме­сто вер­шин­но­го эле­мен­та за­пи­сы­ва­ем эле­мент из са­мо­го ниж­не­го уров­ня де­ре­ва.

Вос­ста­нав­ли­ва­ем (пе­ре­сор­ти­ро­вы­ва­ем) пи­ра­ми­ду.

Са­мый боль­шой эле­мент из остав­ших­ся сно­ва в вер­ши­не. Сно­ва от­де­ля­ем его и за­пи­сы­ва­ем его в ка­че­стве пред­по­след­не­го эле­мен­та ре­зуль­та­та, и так да­лее...

Весь фо­кус ал­го­рит­ма в том, что пи­ра­ми­да без до­пол­ни­тель­ных за­трат хра­нит­ся пря­мо в ис­ход­ном мас­си­ве. По ме­ре то­го, как раз­мер пи­ра­ми­ды умень­ша­ет­ся, она за­ни­ма­ет всё мень­шую часть мас­си­ва, а ре­зуль­тат сор­ти­ров­ки за­пи­сы­ва­ет­ся на­чи­ная с кон­ца мас­си­ва на осво­бо­див­шие­ся от пи­ра­ми­ды ме­ста.

Ещё од­но объ­яс­не­ние идеи ал­го­рит­ма мо­же­те посмот­реть в этом ком­мен­та­рии.

Дво­ич­ное де­ре­во

Дво­ич­ное де­ре­во — ст­рук­ту­ра дан­ных, в ко­то­рой каж­дый эле­мент име­ет ле­во­го и/или пра­во­го по­том­ка, ли­бо во­об­ще не име­ет по­том­ков. В по­след­нем слу­чае эле­мент на­зы­ва­ет­ся ли­сто­вым.

Ес­ли эле­мент A име­ет по­том­ка B, то эле­мент A на­зы­ва­ет­ся ро­ди­те­лем эле­мен­та B. В дво­ич­ном де­ре­ве су­ще­ству­ет един­ствен­ный эле­мент, ко­то­рый не име­ет ро­ди­те­лей; та­кой эле­мент на­зы­ва­ет­ся кор­не­вым.