Stanford Algorithms: Design and Analysis, Part 1[week 6]

#ifndef _HEAP_H_#define _HEAP_H_//MAX_HEAPvoid MAX_HEAPIFY(short *A,short i){short left=2*i,right=2*i+1,larger,tmp;if ((left<=A[0])&&(A[left]>A[i]))larger = left;elselarger = i;if ((right<=A[0])&&(A[right]>A[larger]))larger = right;if (larger != i){tmp = A[larger]; A[larger] = A[i]; A[i] = tmp;MAX_HEAPIFY(A,larger);}}short EXTRACT_MAX(short *A){ short max = A[1]; A[1] = A[A[0]–]; MAX_HEAPIFY(A,1); return max;}void HEAP_INCREASE_KEY(short *A,short i,short key){ short tmp; A[i] = key; while ((i>1)&&(A[i/2]<A[i])){tmp = A[i]; A[i] = A[i/2]; A[i/2] = tmp;i = i/2; }}void MAX_HEAP_INSERT(short *A,short key){ A[0]++; HEAP_INCREASE_KEY(A,A[0],key);}//MIN_HEAPvoid MIN_HEAPIFY(short *A,short i){short left=2*i,right=2*i+1,smaller,tmp;if ((left<=A[0])&&(A[left]<A[i]))smaller = left;elsesmaller = i;if ((right<=A[0])&&(A[right]<A[smaller]))smaller = right;if (smaller != i){tmp = A[smaller]; A[smaller] = A[i]; A[i] = tmp;MIN_HEAPIFY(A,smaller);}}short EXTRACT_MIN(short *A){ short min = A[1]; A[1] = A[A[0]–]; MIN_HEAPIFY(A,1); return min;}void HEAP_DECREASE_KEY(short *A,short i,short key){ short tmp; A[i] = key; while ((i>1)&&(A[i/2]>A[i])){tmp = A[i]; A[i] = A[i/2]; A[i/2] = tmp;i = i/2; }}void MIN_HEAP_INSERT(short *A,short key){ A[0]++; HEAP_DECREASE_KEY(A,A[0],key);}#endif#include<stdio.h>#include<stdlib.h>#include<ctype.h>#include "heap.h"const char INFILE[] = "Median.txt";#define MAX10000short A1[10001],A2[10001];short RETURN_MEDIAN(short *A1,short *A2,short x){ if (x<A2[1])MAX_HEAP_INSERT(A1,x); elseMIN_HEAP_INSERT(A2,x); if (A1[0]-A2[0]>1)MIN_HEAP_INSERT(A2,EXTRACT_MAX(A1)); if (A2[0]>A1[0])MAX_HEAP_INSERT(A1,EXTRACT_MIN(A2)); return A1[1];}void main(){ int m=0; A1[0] = 1; A1[1] = 0; A2[0] = 1; A2[1] = 20000; char line[10]; FILE *fp = fopen(INFILE,"r"); while (fgets(line,10,fp))m = (m + RETURN_MEDIAN(A1,A2,atoi(line))) % 10000; printf("%d\n",m);}

，使用双手的是劳工，使用双手和头脑的舵手，