中位数

  往一个集合中求出中位数

 

  N为奇数则  middle = a[N/2]也就是第N/2+1大的数

  N为偶数则  middle = (a[N/2]+a[N/2-1])/2 也就是第N/2-1,N/2大的数

  当然我这里用到的算法是二叉堆,如果各位有其它的好算法的话,不放分享下:

 

  堆得大小为a[N/2]，遍历完后,deletemin一次就是a[N/2],偶数就遍历两次

我下面的代码还不是完整,上面的思路是对的..有事就不能写了

 

 

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

#define MAX 21

typedef struct heap
{
   int capicity;
   int size;
   int* num;
  }HEAP;

void print_array(HEAP* H)
{
  int i = 0;
  for(;i<H->size;i++)
   printf("%d\t",H->num[i+1]);
   
  printf("\n");
}
  
HEAP* init_heap()
{
  HEAP* H = (HEAP*)malloc(sizeof(H));
  H->capicity = MAX;
  H->size = 0;
  H->num = (int*)malloc(MAX*sizeof(int*));
  return H;
 }

int insert_heap(int val,HEAP* H)
{
   int i;
   if(H->size == H->capicity)
    {
      printf("heap is full\n");
      return -1;
     }
   for(i=++H->size;i/2>0&&H->num[i/2]>val;i/=2)
     H->num[i] = H->num[i/2];
     
   H->num[i] = val;
   return 0;
 }
 
int delete_min(HEAP* H)
{
    int min = H->num[1];
    int last = H->num[H->size--];
    int child;
    int i;
    if(H->size==1)
       return min;
       
    for(i=1;i<=H->size/2;i=child)
    {
      child = i*2;
      if(child!=H->size && H->num[child+1]<H->num[child])
        child++;
      
      if(last>=H->num[child])
         H->num[i] = H->num[child];
      else
         break;
     }
     H->num[i] = last;
     
     return min;
}

int get_middle(HEAP* H)
{
  int i = 0;
  int val = 0;
  int j = 0;
  int middle = 0;
  int a[MAX-1];
  srand((unsigned)time(NULL));
  for(i=0;i<MAX;i++)
   {
      val = rand()%100+1;
      insert_heap(val,H);
    }
   
   print_array(H);
   printf("Begin delete\n");
      for(j=0;j<MAX;j++)
       {
         a[j] = delete_min(H);
         printf("%d\t",a[j]);
        }
      
      if(j%2==1)
        middle = a[j/2];
      else
        middle = a[j/2]+a[j/2-1];
         
      printf("\n and the middle is %d\n",middle);
}

int main(int argc, char *argv[])
{
  HEAP* H = init_heap();
  get_middle(H);
  system("PAUSE");    
  return 0;
}