poj 2388 Heap Sort Heap Median

Description

Input

Output

Sample Input

5
2
4
1
3
5

Sample Output

3

Hint

A standard method to build a heap:

//1. 利用宏定义swap
//2. max_heapify(largest,heap,len);开始忘了递归了，自底向上地递归 
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int N,milk[1000001],size;
void max_heapify(int i,int heap[],int len){//数组从0开始 
    int l,r,largest;
    l=2*i+1;   r=2*i+2;
    if( l<len && heap[l]>heap[i] )
        largest=l;
    else
        largest=i;
        
    if( r<len && heap[r]>heap[largest] )
        largest=r;

    if(largest!=i){
        swap( heap[largest],heap[i] );
		max_heapify(largest,heap,len);
    }
}

int main(){
    int i,j;
    scanf("%d",&size);
    for(i=0;i<=size/2;i++){
        scanf("%d",&milk[i]);
    }

	for(i=(size/2+1)/2-1;i>=0;i--)
        max_heapify(i,milk,size/2+1);
        
    for(i=size/2+1;i<size;i++){
        scanf("%d",&milk[i]);
        if(milk[i]<milk[0]){
             swap( milk[i],milk[0] );
             max_heapify(0,milk,size/2+1);             
        }
    }
    printf("%d\n",milk[0]);
    
    
    //system("pause");
    return 0; 
}

poj 2388 Heap Sort Heap Median

原文：http://blog.csdn.net/taoqick/article/details/19207667