In this HackerRank Starfleet problem solution, we have given the initial positions of the space-fighters, and their velocity, you are to answer queries of the following form:
YU YD T
where YU, YD is the bounds on the y-axis inside which YODA can block a frequency at time T. In the region described by the query, after a time of T seconds from the start, if Yoda can choose one frequency (F) he wishes to, what is the maximum number of communications he can block?
Problem solution in Python programming.
import bisect from collections import defaultdict N,Q,_ = map(int,input().split()) a = defaultdict(list) y = list() for _ in range( N ): _,y_,freq = map(int,input().split()) a[ freq ].append( y_ ) y.append( y_ ) a = { freq:sorted(y) for freq,y in a.items() if len(y) > 1 } y = sorted( y ) res = [] for _ in range( Q ): y_max, y_min, T = map(int,input().split()) lres = 0 index_start = bisect.bisect_left(y, y_min) if y[ index_start ] <= y_max: lres = 1 for freq in a: index_start = bisect.bisect_left( a[freq], y_min ) index_stop = bisect.bisect_right( a[freq], y_max ) lres = max( lres, index_stop - index_start ) res.append( lres ) print(*res, sep = 'n')
Problem solution in Java Programming.
import java.io.*; import java.nio.file.Files; import java.nio.file.Paths; import java.util.*; import java.util.stream.Collectors; // Library Query public class Solution { static class DEBUG { static public final boolean ON = false; static public void ASSERT( boolean ok, String msg ) { if (!ok) throw new RuntimeException(msg); } } static class Scanner { private final String data; private int curPos; private int len; private boolean hasData = true; Scanner(String dt) { data = dt; len = data.length(); } int getNextInt() { while (data.charAt(curPos) <= 32) curPos++; int res = 0; int k = 1; if (data.charAt(curPos)=='-') { curPos++; k = -1; } try { while (data.charAt(curPos) > 32) { res *= 10; res += data.charAt(curPos) - '0'; curPos++; } } catch (Exception ign) { int r = 0; } return res * k; } void nextLine() { while (data.charAt(curPos) < 32) curPos++; while (data.charAt(curPos) >= 32) { curPos++; } while (data.charAt(curPos) < 32) curPos++; } boolean atNewLine() { return data.charAt(curPos) < 32; } boolean hasNextLine() { return curPos + 3 < len; } } static class Fighter { final int y; final int f; Fighter(int y, int f) { this.y = y; this.f = f; } } static class FighterFreq { final int f; final int n; // number of fighters FighterFreq(int f, int n) { this.f = f; this.n = n; } } static class FighterFreqBucket { int ly; int ry; // not included // sorted dec by n final Map< Integer, FighterFreq > fighterFreqIndex; // key: Freq final List< FighterFreq > fighterFreqRatings; Map< Integer, List<Fighter> > sourceData; // need for leaves private FighterFreqBucket L; private FighterFreqBucket R; // R is not included // data expetced to be filtered for this Node, Key: Frequency FighterFreqBucket(int ly, int ry, Map< Integer, List<Fighter> > data, FighterFreqBucket parent ) { this.ly = ly; this.ry = ry; // Build own data fighterFreqIndex = new HashMap<>(); fighterFreqRatings = data.entrySet().stream().map(ent -> new FighterFreq( ent.getKey(), ent.getValue().size() ) ).collect( Collectors.toList() ); int sumn = 0; for (FighterFreq ff : fighterFreqRatings ) { fighterFreqIndex.put( ff.f, ff ); sumn += ff.n; } // sorting by numbers. First - biggest number fighterFreqRatings.sort( (ff1, ff2) -> { if (ff1.n == ff2.n) return parent==null ? 0 : -Integer.compare( parent.getN( ff1.f ), parent.getN( ff2.f ) ); else return -Integer.compare( ff1.n, ff2.n ); } ); if ( sumn > 15 && ry-ly > 1 ) { // has children (until one freq will be reached)... Map< Integer, List<Fighter> > LData = new HashMap<>(); Map< Integer, List<Fighter> > RData = new HashMap<>(); int cy = (ry+ly)/2; for ( Map.Entry< Integer, List<Fighter> > ent : data.entrySet() ) { int f = ent.getKey(); ArrayList<Fighter> LFs = new ArrayList<>(); ArrayList<Fighter> RFs = new ArrayList<>(); ent.getValue().forEach( fg -> { if (fg.y < cy) LFs.add(fg); else RFs.add(fg); } ); if (!LFs.isEmpty()) LData.put(f,LFs); if (!RFs.isEmpty()) RData.put(f,RFs); } L = new FighterFreqBucket(ly, cy, LData, this); R = new FighterFreqBucket(cy, ry, RData, this); sourceData = null; } else { L=R=null; sourceData = data; } } int getN(int f) { FighterFreq ff = fighterFreqIndex.get(f); if (ff==null) return 0; return ff.n; } void collectAllBuckets( int y1, int y2, List<FighterFreqBucket> result ) { if ( ly == y1 && ry==y2 ) { result.add(this); return; } if (L==null) { // No kids, and range doesn't match. // Creating a new one from the data Map< Integer, List<Fighter> > yyData = new HashMap<>(); for ( Map.Entry< Integer, List<Fighter> > ent : sourceData.entrySet() ) { int f = ent.getKey(); List<Fighter> ff = ent.getValue().stream().filter( fighter -> fighter.y>=y1 && fighter.y<y2 ).collect(Collectors.toList()); if (!ff.isEmpty()) yyData.put( f,ff ); } result.add( new FighterFreqBucket(y1, y2, yyData, this) ); return; } // Need delgate to the children int cy = (ly + ry)/2; if ( y1<cy ) L.collectAllBuckets( y1, Math.min(cy,y2), result ); if ( y2>cy ) { R.collectAllBuckets(Math.max(cy, y1), y2, result); } } int getDataSize() {return fighterFreqRatings.size();} FighterFreq getFF(int idx) { return idx>=fighterFreqRatings.size() ? null : fighterFreqRatings.get(idx); } int calcGain(int idx) { int sz = fighterFreqRatings.size(); if ( idx>=sz ) return 0; return fighterFreqRatings.get(idx).n - fighterFreqRatings.get(Math.min( sz-1,idx+5)).n; } } static class BucketInfo { final int idx; // bucket index int nmax = 0; int dataIdx = 0; int gain = 0; BucketInfo(int idx, int nmax, int gain) { this.idx = idx; this.nmax = nmax; this.gain = gain; } } public static int calcMaxN( List<FighterFreqBucket> buckets ) { HashSet<Integer> precessedFreqs = new HashSet<>(); int maxFreqs = buckets.stream().map( b-> b.getDataSize() ).max(Integer::compare).get(); int maxN = 0; /* int theorMax = 0; ArrayList<BucketInfo> weights = new ArrayList<>(); for (int t=0; t<buckets.size();t++) { FighterFreqBucket b = buckets.get(t); FighterFreq ff = b.getFF(0); int n = ff==null? 0 : ff.n; theorMax += n; weights.add( new BucketInfo(t, n, b.calcGain(0) ) ); } // if (DEBUG.ON) { // int totalItems = buckets.stream().mapToInt(b -> b.fighterFreqIndex.size()).sum(); // System.out.println("Total items = " + totalItems); // } weights.sort( (o1, o2) -> -Integer.compare(o1.gain, o2.gain) ); int iterations = 0; int maxIter = 0; while (maxN < theorMax ) { // Processing Max Fs first iterations++; BucketInfo bi = weights.get(0); FighterFreqBucket b = buckets.get(bi.idx); FighterFreq ff = b.getFF(bi.dataIdx++); if (ff==null) { theorMax -= bi.nmax; bi.nmax = 0; bi.gain = -1; } else { if (! precessedFreqs.contains(ff.f)) { precessedFreqs.add(ff.f); int ffN = buckets.stream().mapToInt(bucket -> bucket.getN(ff.f)).sum(); if (maxN < ffN) { maxN = ffN; maxIter = iterations; } } theorMax -= bi.nmax - ff.n; bi.nmax = ff.n; bi.gain = b.calcGain(bi.dataIdx); } if (weights.size()>1) { for (int t=1;t<weights.size();t++) { if ( weights.get(t-1).gain < weights.get(t).gain ) { BucketInfo sw = weights.get(t-1); weights.set(t-1, weights.get(t) ); weights.set(t, sw ); } else { break; } } } } if (DEBUG.ON) { if (maxIter>90) { int totalItems = buckets.stream().mapToInt(b -> b.fighterFreqIndex.size()).sum(); System.out.println("totalItems=" + totalItems + " Iterations= " + iterations + " maxIter=" + maxIter); } }*/ int iterations = 0; int maxIter = 0; for ( int i=0; i<maxFreqs && iterations<200; i++ ) { int theorMax = 0; for (int r=buckets.size()-1; r>=0; r-- ) { iterations++; FighterFreqBucket b = buckets.get(r); FighterFreq ff = b.getFF(i); if (ff==null) { buckets.remove(r); continue; } theorMax += ff.n; if (precessedFreqs.contains(ff.f)) { continue; } precessedFreqs.add(ff.f); int ffN = 0; for ( FighterFreqBucket bb : buckets ) ffN += bb.getN(ff.f); //buckets.stream().mapToInt( bucket -> bucket.getN(ff.f) ).sum(); if (maxN < ffN) { maxN = ffN; maxIter = iterations; } } if (maxN>=theorMax) // all tops are found break; } if (DEBUG.ON) { if (maxIter>200) System.out.println("iterations=" + iterations+ " maxIter="+maxIter + " maxFreqs="+maxFreqs); } return maxN; } public static void main(String[] args) { Scanner input = null; ArrayList<Integer> results = null; try { ByteArrayOutputStream result = new ByteArrayOutputStream(); byte[] buffer = new byte[10240]; int length; while ((length = System.in.read(buffer)) != -1) { result.write(buffer, 0, length); } input = new Scanner( result.toString("UTF-8") ); } catch (Exception ex) { ex.printStackTrace(); return; } long startT = System.currentTimeMillis(); int N = input.getNextInt(); // number of space fighters int Q = input.getNextInt(); input.getNextInt(); // Velocity - we don't care // Load fighters with Fs ArrayList<Fighter> fighters = new ArrayList<>(); int minY = 0; int maxY = 0; for (int n=0; n<N; n++) { input.getNextInt(); // x - don't care int y = input.getNextInt(); int f = input.getNextInt(); fighters.add( new Fighter(y,f) ); if (minY > y) minY = y; if (maxY < y) maxY = y; } TreeSet<Integer> singleFFs = new TreeSet<>(); // Let's build the index from the ships Map< Integer, List<Fighter> > data = fighters.stream().collect( Collectors.groupingBy( f -> f.f, Collectors.toList() )). entrySet().stream().filter( ent -> { if (ent.getValue().size()==1) { singleFFs.add( ent.getValue().get(0).y ); return false; } return true; } ).collect( Collectors.toMap(o -> o.getKey(), o->o.getValue()) ); FighterFreqBucket rootBucket = new FighterFreqBucket(minY, maxY+1, data, null ); ArrayList<Integer> res = new ArrayList<>(); long buildT = System.currentTimeMillis(); long buildBucketsT = 0; long calcTime = 0; // Processign Queries for (int q=0;q<Q;q++) { long t1 = System.currentTimeMillis(); int y2 = input.getNextInt(); int y1 = input.getNextInt(); input.getNextInt(); // T - don't care y1 = Math.max(y1, minY); y2 = Math.min(y2, maxY); // Calculatign the result List < FighterFreqBucket > buckets = new ArrayList<>(); rootBucket.collectAllBuckets(y1,y2+1, buckets ); long t2 = System.currentTimeMillis(); int ffn = calcMaxN( buckets); if (ffn==0) { // Might be one of singles... Integer lo = singleFFs.ceiling( y1 ); Integer hi = singleFFs.floor(y2); if (lo!=null && hi!=null && lo<=hi) ffn = 1; } if (results!=null) { if (results.get(res.size()).intValue() != ffn) throw new RuntimeException("Res wrong failure"); } long t3 = System.currentTimeMillis(); buildBucketsT+= t2-t1; calcTime += t3-t2; res.add(ffn); } long finishT = System.currentTimeMillis(); System.out.println("totalT="+(finishT-startT) + " buildT="+ (buildT-startT) + " procT="+ (finishT-buildT) + " buildBucketsT="+buildBucketsT+ " calcTime="+calcTime); try { FileWriter fw = new FileWriter(System.getenv("OUTPUT_PATH")); StringBuilder sb = new StringBuilder(); res.forEach(i -> sb.append(i).append("n")); fw.write(sb.toString()); fw.close(); } catch (Exception ex) { ex.printStackTrace(); } } }
Problem solution in C++ programming.
#include <algorithm> #include <iostream> #include <cstring> #include <cassert> #include <iomanip> #include <cstdio> #include <vector> #include <string> #include <stack> #include <cmath> #include <ctime> #include <queue> #include <list> #include <map> #include <set> #define For(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++) #define FOR(i,a) For(i,1,a) #define Ford(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--) #define Rep(i,a,b) for(register int (i)=(a);(i)<(b);(i)++) #define REP(i,a) Rep(i,0,a) #define type(x) __typeof(x.begin()) #define foreach(it,x) for(__typeof(x.begin()) it = x.begin() ; it!=x.end() ; it++ ) #define NEW(x,n) (x*)calloc(n,sizeof(x)) #define fill(x,y) memset(x,y,sizeof x) #define all(x) x.begin(),x.end() #define compress(x) {sort(all(x));(x).resize(unique(all(x))-(x).begin());} #define two(x) (1LL<<(x)) #define fi first #define se second #define gcd __gcd #define pb push_back #define mp make_pair #ifdef KAZAR #define eprintf(...) fprintf(stderr, __VA_ARGS__) #define dbg(x) cerr<<#x<<":"<<(x)<<endl #define dg(x) cerr<<#x<<":"<<(x)<<' ' #else #define eprintf(...) 0 #define dbg(x) 0 #define dg(x) 0 #endif using namespace std; typedef long long Lint; typedef long double ld; typedef pair<int,int> ii; typedef pair<int,ii> iii; typedef vector<int> vi; typedef vector<ii> vii; const int inf = 1e9+5143; const Lint Linf = 1e18+5413; const double eps = 1e-15; const double pi = acos(-1); template<class T> inline void umax(T &a,T b){if(a<b) a = b ; } template<class T> inline void umin(T &a,T b){if(a>b) a = b ; } template<class T> inline T abs(T a){return a>0 ? a : -a;} template<class T> inline T lcm(T a,T b){ return a/gcd(a,b)*b; } inline int read(){ int res = 0LL ;int neg ; while(1){ char ch = getchar(); if(ch>='0' && ch<='9' || ch=='-'){ if(ch=='-') neg = -1; else neg = 1 , res = ch-'0'; break; } } while(1){ char ch = getchar(); if(ch>='0' && ch<='9') res*=10 , res+=ch-'0'; else break; } return res*neg; } const int N = 492717; const int SQ = 300; ii a[N]; int f[N]; vi valsx , vals; vi occurance[N]; vii ask[N]; vi huges; int ans[N]; int q; vi here[N]; void get_damn_input(){ int n = read(); q = read(); read(); FOR(i,n){ read(); a[i].fi = read(); a[i].se = read(); valsx.pb(a[i].fi); } compress(valsx); FOR(i,n){ a[i].fi = lower_bound(all(valsx),a[i].fi) - valsx.begin() + 1; } sort(a + 1,a + 1 + n); FOR(i,n){ vals.pb(a[i].se); } compress(vals); FOR(i,n){ f[i] = lower_bound(all(vals),a[i].se) - vals.begin() + 1; assert(f[i] < N); occurance[f[i]].pb(a[i].fi); assert(a[i].fi < N); here[a[i].fi].pb(f[i]); } REP(i,N) compress(here[i]); REP(i,vals.size() + 5){ sort(all(occurance[i])); if(occurance[i].size() > SQ){ huges.pb(i); } } FOR(i,q){ int r = upper_bound(all(valsx),read()) - valsx.begin(); int l = lower_bound(all(valsx),read()) - valsx.begin() + 1; read(); eprintf("query %d , %dn",l,r); assert(r < N); ask[r].pb(ii(l,i)); } } int kd[N * 10]; void put(int k,int b,int e,int x,int val){ assert(k < N * 10); if(b > x || e < x) return; if(b == e){ assert(val > 0); umax(kd[k],val); return; } put(k + k,b,(b+e)/2,x,val); put(k + k + 1,(b+e)/2 + 1,e,x,val); kd[k] = max(kd[k + k],kd[k + k + 1]); } int get(int k,int b,int e,int x1,int x2){ assert(k < N * 10); if(b > x2 || e < x1) return 0; if(b >= x1 && e <= x2) return kd[k]; return max(get(k + k,b,(b+e)/2,x1,x2),get(k + k + 1,(b+e)/2+1,e,x1,x2)); } void insert(int idx,int where){ assert(idx < N); if(occurance[idx].size() > SQ) return; int cur = 0; Ford(i,occurance[idx].size() - 1,0){ if(occurance[idx][i] <= where){ put(1,1,N,occurance[idx][i],++cur); } } } int main(){ #ifdef KAZAR freopen("f.input","r",stdin); freopen("f.output","w",stdout); freopen("error","w",stderr); #endif get_damn_input(); REP(i,10){ eprintf("here %d: ",i); foreach(it,here[i]) eprintf("%d ",*it); eprintf("n"); } dbg(huges.size()); REP(i,N){ assert(i < N); foreach(it,here[i]){ insert(*it,i); eprintf("inserting i:%d f:%d then : %dn",i,*it,get(1,1,N,1,i)); } int r = i; foreach(it,ask[r]){ int l = it->fi; assert(l < N); assert(r < N); int res = get(1,1,N,l,r); foreach(huge,huges){ assert(*huge < N); umax(res,int(upper_bound(all(occurance[*huge]),r) - lower_bound(all(occurance[*huge]),l)) ); } ans[it->se] = res; } } FOR(i,q) printf("%dn",ans[i]); return 0; }
Problem solution in C programming.
#include <stdio.h> #include <stdlib.h> #include <math.h> typedef struct{ int u; int w; } node; void QQ(int x,int y); void add(int x); void removee(int x); void sort_a2(int*a,int*b,int size); void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size); void sort_a3(int*a,int*b,int*c,int size); void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size); void update( int i, int val ); int get_i(int*a,int num,int size); int med(int*a,int size); void heap_insert(node *heap,node *elem,int *size,int *heap_list); void heap_update(node *heap,node *elem,int *heap_list,int size); int a[50000],b[50000]={0},q[30000],q1[30000],q2[30000],y[50000],f[50000],idx[50000],ans[30000],heap_list[50000]={0},cl,cr,heap_size=0; node heap[50001]; int main(){ int NN,Q,V,x,i; scanf("%d%d%d",&NN,&Q,&V); for(i=0;i<NN;i++){ scanf("%d%d%d",&x,y+i,f+i); idx[i]=i; } for(i=0;i<Q;i++) scanf("%d%d%d",q2+i,q1+i,&x); sort_a2(y,f,NN); for(i=0;i<Q;i++){ q1[i]=get_i(y,q1[i],NN); q2[i]=get_i(y,q2[i]+1,NN); } sort_a2(f,idx,NN); for(i=x=0;i<NN;i++){ if(i && f[i]!=f[i-1]) x++; a[idx[i]]=x; } for(i=0,x=(int)sqrt(NN);i<Q;i++){ q[i]=q1[i]/x; y[i]=q2[i]; idx[i]=i; } sort_a3(q,y,idx,Q); for(i=cl=cr=0;i<Q;i++){ QQ(q1[idx[i]],q2[idx[i]]); ans[idx[i]]=heap[1].w; } for(i=0;i<Q;i++) printf("%dn",ans[i]); return 0; } void QQ(int x,int y){ while(cl<x) removee(cl++); while(cl>x) add(--cl); while(cr<y) add(cr++); while(cr>y) removee(--cr); return; } void add(int x){ b[a[x]]++; update(a[x],b[a[x]]); return; } void removee(int x){ b[a[x]]--; update(a[x],b[a[x]]); return; } void sort_a2(int*a,int*b,int size){ if (size < 2) return; int m = (size+1)/2,i; int*left_a,*left_b,*right_a,*right_b; left_a=(int*)malloc(m*sizeof(int)); right_a=(int*)malloc((size-m)*sizeof(int)); left_b=(int*)malloc(m*sizeof(int)); right_b=(int*)malloc((size-m)*sizeof(int)); for(i=0;i<m;i++){ left_a[i]=a[i]; left_b[i]=b[i]; } for(i=0;i<size-m;i++){ right_a[i]=a[i+m]; right_b[i]=b[i+m]; } sort_a2(left_a,left_b,m); sort_a2(right_a,right_b,size-m); merge2(a,left_a,right_a,b,left_b,right_b,m,size-m); free(left_a); free(right_a); free(left_b); free(right_b); return; } void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size){ int i = 0, j = 0; while (i < left_size|| j < right_size) { if (i == left_size) { a[i+j] = right_a[j]; b[i+j] = right_b[j]; j++; } else if (j == right_size) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; i++; } else if (left_a[i] <= right_a[j]) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; i++; } else { a[i+j] = right_a[j]; b[i+j] = right_b[j]; j++; } } return; } void sort_a3(int*a,int*b,int*c,int size){ if (size < 2) return; int m = (size+1)/2,i; int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c; left_a=(int*)malloc(m*sizeof(int)); right_a=(int*)malloc((size-m)*sizeof(int)); left_b=(int*)malloc(m*sizeof(int)); right_b=(int*)malloc((size-m)*sizeof(int)); left_c=(int*)malloc(m*sizeof(int)); right_c=(int*)malloc((size-m)*sizeof(int)); for(i=0;i<m;i++){ left_a[i]=a[i]; left_b[i]=b[i]; left_c[i]=c[i]; } for(i=0;i<size-m;i++){ right_a[i]=a[i+m]; right_b[i]=b[i+m]; right_c[i]=c[i+m]; } sort_a3(left_a,left_b,left_c,m); sort_a3(right_a,right_b,right_c,size-m); merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m); free(left_a); free(right_a); free(left_b); free(right_b); free(left_c); free(right_c); return; } void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size){ int i = 0, j = 0; while (i < left_size|| j < right_size) { if (i == left_size) { a[i+j] = right_a[j]; b[i+j] = right_b[j]; c[i+j] = right_c[j]; j++; } else if (j == right_size) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; c[i+j] = left_c[i]; i++; } else if (left_a[i] == right_a[j]) { if(left_b[i]<=right_b[j]){ a[i+j] = left_a[i]; b[i+j] = left_b[i]; c[i+j] = left_c[i]; i++; } else{ a[i+j] = right_a[j]; b[i+j] = right_b[j]; c[i+j] = right_c[j]; j++; } } else if (left_a[i] < right_a[j]) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; c[i+j] = left_c[i]; i++; } else { a[i+j] = right_a[j]; b[i+j] = right_b[j]; c[i+j] = right_c[j]; j++; } } return; } void update( int i, int val ){ node elem; elem.u=i; elem.w=val; if(!heap_list[i]) heap_insert(heap,&elem,&heap_size,heap_list); else heap_update(heap,&elem,heap_list,heap_size); return; } int get_i(int*a,int num,int size){ if(size==0) return 0; if(num>med(a,size)) return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1); else return get_i(a,num,(size-1)>>1); } int med(int*a,int size){ return a[(size-1)>>1]; } void heap_insert(node *heap,node *elem,int *size,int *heap_list){ (*size)++; int index=(*size); while(index>1 && elem->w>heap[index/2].w){ heap[index]=heap[index/2]; heap_list[heap[index].u]=index; index/=2; } heap[index]=(*elem); heap_list[elem->u]=index; return; } void heap_update(node *heap,node *elem,int *heap_list,int size){ int index=heap_list[elem->u]; while(index>1 && elem->w>heap[index/2].w){ heap[index]=heap[index/2]; heap_list[heap[index].u]=index; index/=2; } while(index*2<=size && elem->w<heap[index*2].w || index*2+1<=size && elem->w<heap[index*2+1].w){ if(index*2+1<=size) index=(heap[index*2].w<heap[index*2+1].w)?index*2+1:index*2; else index=index*2; heap[index/2]=heap[index]; heap_list[heap[index].u]=index/2; } heap[index]=(*elem); heap_list[elem->u]=index; return; }
There's something called explanation and it's missing here