堆的兩種操作所花的時間都和樹的深度成正比.因此,如果一共有n個元素,那么每個操作可以在O(logn)時間內完成.

堆的實現

1.左兒子的編號是自己的編號*2+1

2.右兒子的編號是自己的編號*2+1

?

push和pop的實現:

1 int heap[MAX],sz=0; 2 3 void push(int x) 4 { 5 //自己節點的編號 6 int i=sz++; 7 8 while(i>0){ 9 //父親節點的編號 10 int p=(i-1)/2; 11 12 //如果已經沒有大小顛倒則退出 13 if(heap[p]<=x) break; 14 15 //把父親節點的數值放下來,而把自己提上去 16 heap[i]=heap[p]; 17 i=p; 18 } 19 } 20 21 int pop() 22 { 23 //最小值 24 int ret=heap[0]; 25 26 //要提到根的數值 27 int x=heap[--sz]; 28 29 //從根開始向下交換 30 int i=0; 31 while(i*2+1<sz){ 32 //比較兒子的值 33 int a=i*2+1,n=i*2+2; 34 if(b<sz && heap[b]<heap[a]) a=b; 35 36 //如果已經沒有大小顛倒則退出 37 if(heap[a]>=x) 38 break; 39 40 //把兒子的數組提上來 41 heap[i]=heap[a]; 42 i=a; 43 } 44 heap[i]=x; 45 return ret; 46 }

?

編程語言的標準庫:

實際上,大部分情況并不需要自己實現堆.在許多編程語言的標準中,都包含了優先隊列的高效實現.例如在c++中,STL里的priority_queue就是其中之一.不過需要注意的是,priority_queue與上面講的優先隊列有所不同,取出數值得到的是最大值.

?

1 #include <queue> 2 #include <cstdio> 3 using namespace std; 4 5 int main() 6 { 7 //聲明 8 priority_queue<int> p; 9 10 //插入元素 11 p.push(3); 12 p.push(5); 13 p.push(1); 14 15 //不斷循環直到空為止 16 while(!p.empty()){ 17 //獲取并刪除最大值 18 printf("%d\n",p.top()); 19 p.pop(); 20 } 21 return 0; 22 }

?

轉載于:https://www.cnblogs.com/wangmengmeng/p/5244460.html

總結

以上是生活随笔為你收集整理的堆的操作的复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。