Binærhaug: sift opp

En binærhaug er det samme objektet sett på to måter — som et tre der hver forelder er større enn barna, og som en flat liste der forelderen til celle i ligger på i minus en delt på to. Når vi setter inn nittitalls verdi nederst i lista, vandrer den oppover ved å bytte plass med forelderen sin så lenge den er større. Tre bytter senere står den på toppen. Hver innsetting koster orden log n fordi banen fra et blad til rota har høyden til treet — og treet har høyde log to av n.