At 6:00 its said KlogN

But before popping the top elements we have to preprocess the heap by building the heap which itself will take NlogN?