Algoritme Prim

Dengan struktur data binary heap sederhana, algoritme Prim dapat ditunjukkan berjalan dalam waktu O("E"log "V"), di mana E adalah jumlah cabang dan V adalah jumlah node. Dengan Fibonacci heap, hal ini dapat ditekan menjadi O("E" + "V"log "V"), yang jauh lebih cepat bila grafnya cukup padat sehingga "E" adalah formula_1("V"log "V").