2019獨角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

二叉堆

堆有序：當(dāng)一棵二叉樹的每個結(jié)點都大于等于它的兩個子結(jié)點時，它被稱為堆有序。根結(jié)點是堆有序的二叉樹中的最大節(jié)點。

二叉堆：二叉堆是一組能夠用堆有序的完全二叉樹排序的元素，并在數(shù)組中按層級存儲（不使用數(shù)組的第一個位置）。

二叉堆可以使用數(shù)組或者二叉樹實現(xiàn)，在這里使用數(shù)組實現(xiàn)。在數(shù)組中，根結(jié)點放置在下標(biāo)為1的空間內(nèi)；下標(biāo)k的結(jié)點的父結(jié)點的下標(biāo)為?k?，它的兩個子結(jié)點的下標(biāo)為2k和2k+1.?

代碼實現(xiàn)：

構(gòu)造堆的過程中，肯定會用到比較方法和交換方法：

//比較方法 private boolean less(int i,int j) { return pq.[i].compareTo(pq[j])<0; } //交換方法 priivate void exch(int i,intj) { Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; }

在對堆進(jìn)行有序化的過程中會遇到兩種情況：

• 當(dāng)某個節(jié)點優(yōu)先級上升(或在堆底加入了一個新元素)時，我們需要由下至上恢復(fù)堆的順序；
• 當(dāng)某個節(jié)點優(yōu)先級下降(例如將根結(jié)點替換為一個較小節(jié)點)時，我們需要由上至下恢復(fù)堆的順序；

我們把由下至上恢復(fù)堆的順序稱為上浮，把由上至下恢復(fù)堆的順序叫下沉。

上浮操作：

private void swim(int k){while(k>1 && less(k/2,k){exch(k/2,k);k=k/2;} }

下沉操作：

private void sink(int k){while(2*k <= N){int j = 2*k;if(j<N && less(j,j+1)) j++; //保證j是k兩個子節(jié)點中的較小者if(!less(k,j)) break; //如果k大于j，結(jié)束exch(k,j);k = j;} }

通過使用上面的方法，我們就可以構(gòu)造出一個堆，堆的插入操作和刪除最大元素操作都可以在對數(shù)級別的時間內(nèi)完成。

• 插入元素：我們將新元素插入數(shù)組末尾，增加堆的大小并讓新元素上浮到正確位置；
• 刪除最大元素：我們從數(shù)組頂端刪去最大元素并將數(shù)組末尾元素置入頂端，下沉它到正確位置。

優(yōu)先權(quán)隊列

優(yōu)先權(quán)隊列的功能就是插入元素和刪除最大元素，所以我們完全可以基于堆來實現(xiàn)優(yōu)先權(quán)隊列。

明白堆和上面的代碼，優(yōu)先權(quán)隊列很容易實現(xiàn)，直接來看代碼：

public class MaxPQ<Key extends Comparable<Key>>{private Key[] pq; //基于堆private int N; //堆的大小public MaxPQ(int maxN){ pq = (Key[]) new Comparable[maxN+1]; }public void insert(Key v){pq[++] = v;swim(N); //恢復(fù)堆的有序性}public Key delMax(){public Key max = pq[1];exch(1,N--); //和最后一個節(jié)點交換pq[N-1] = null; //防止對象游離sink(1); //恢復(fù)堆的有序性return max; } //less()、exch()、swim()、sink()方法見上文 }

?

轉(zhuǎn)載于:https://my.oschina.net/HuoQibin/blog/1628924

總結(jié)

以上是生活随笔為你收集整理的二叉堆和优先权队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。