優(yōu)先級隊列用堆實現(xiàn)，只是需要構建初始堆，這個時間復雜度是 O(n) 插入和刪除只是 修改了堆頂和堆底，不需要所有的都排序，只是需要再次調整好堆，因此時間復雜度都 是 O(log2n). 假如有 N 個節(jié)點，那么高度為 H=logN，最后一層每個父節(jié)點最多只需要下調 1 次，倒 數(shù)第二層最多只需要下調 2 次，頂點最多需要下調 H 次，而最后一層父節(jié)點共有 2^(H- 1) 個,倒數(shù)第二層公有 2^(H-2),頂點只有 1(2^0)個，所以總共的時間復雜度為 s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0 將 H 代入后 s= 2N - 2 - log2(N)，近似的時間復雜度就是 O(