Пример пирамидальной сортировки на Си

 Пирамидальная сортировка.

 Два потомка у узла.

 /***
 Пирамидальная сортировка
 Пирамида - 2 потомка у узла имеют
 значение меньше чем у него. Таким
 образом, гарантированно можно извлечь
 наибольший элемент, затем пирамиду надо
 перебалансировать. Время - O(N*log2 N)


***/


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LEFT(i)  ((i<<1)+1)  //i*2 + 1
#define RIGHT(i) ((i<<1)+2)
#define SWAP(v,a,b)  {int tmp=v[a];v[a]=v[b];v[b]=tmp;}

void heapify(int v[], int i, int N){
 while(1){
  int left=LEFT(i), right=RIGHT(i), largest=i;
  if(left<N && v[left]>v[i]) largest=left;
  if(right<N && v[right]>v[largest])largest=right;
  if(largest!=i){
    SWAP(v,i,largest);
    i = largest;
  }else
    return;
 }
}
int pop(int v[],int N){
  if(N<=0)
    return -1;
  int top = v[0];
  v[0] = v[N-1];
  heapify(v,0,N-1);
  return top;
}
void heapSort(int v[],int N){
  int i = (N-2)/2;
  while(i>=0){
    heapify(v,i--,N);
  }
}

void heapSort1(int v[],int N){
  int i,index,parent;
  for(i = 0; i < N;i++){
    index=i;
    while(index!=0){
      parent = (index-1)/2;
      if(v[index]<=v[parent])
        break;
      SWAP(v,index,parent);
      index=parent;
    }
  }
}

#define N 10
int main(){
 int v[N];
 int j;
 
 srand(time(0));
 for(j=0;j<N;j++)
  v[j] = rand()%20;

 heapSort1(v,N);
 for(j = N; j > 0; j--)
   printf("%d, ", pop(v,j));
 printf("\n");

 return 0;
}
------------------------------------

 

4 потомка у узла.

/***
 Пирамидальная сортировка
 Пирамида - 4 потомка у узла имеют
 значение меньше чем у него. Таким
 образом, гарантированно можно извлечь
 наибольший элемент, затем пирамиду надо
 перебалансировать. Время - O(N*log4 N)


***/


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NEXT1(i) ((i<<2)+1)  //i*4 + 1
#define NEXT2(i) ((i<<2)+2)
#define NEXT3(i) ((i<<2)+3)
#define NEXT4(i) ((i<<2)+4)

#define SWAP(v,a,b)  {int tmp=v[a];v[a]=v[b];v[b]=tmp;}

void heapify(int v[], int i, int N){
 while(1){
  int n1=NEXT1(i),
      n2=NEXT2(i),
      n3=NEXT3(i),
      n4=NEXT4(i),
      largest=i;
  if(n1<N && v[n1]>v[largest])largest=n1;
  if(n2<N && v[n2]>v[largest])largest=n2;
  if(n3<N && v[n3]>v[largest])largest=n3;
  if(n4<N && v[n4]>v[largest])largest=n4;
 
  if(largest!=i){
    SWAP(v,i,largest);
    i = largest;
  }else
    return;
 }
}
int pop(int v[],int N){
  if(N<=0)
    return -1;
  int top = v[0];
  v[0] = v[N-1];
  heapify(v,0,N-1);
  return top;
}
void heapSort(int v[],int N){
  int i = (N-2)/4;
  while(i>=0){
    heapify(v,i--,N);
  }
}


void heapSort1(int v[],int N){
  int i,index,parent;
  for(i = 0; i < N;i++){
    index=i;
    while(index!=0){
      parent = (index-1)>>2; //    /4
      if(v[index]<=v[parent])
        break;
      SWAP(v,index,parent);
      index=parent;
    }
  }
}

#define N 10
int main(){
 int v[N];
 int j;
 
 srand(time(0));
 for(j=0;j<N;j++)
  v[j] = rand()%20;

 heapSort1(v,N);
 for(j = N; j > 0; j--)
   printf("%d, ", pop(v,j));
 printf("\n");

 return 0;
}