一、堆結構簡述
堆的底層是使用數組來實現的,但卻保持了二叉樹的特性。堆分為兩種,最大堆和最小堆,以最大堆為例,最大堆保持了根結點大於兩個左右兩個孩子,同時所有子樹一次類推。由於堆底層是數組結構,這裡從跟結點開始,按照層序依次走到最後一個結點,結點下標分貝為0~N-1。結構如下圖:
上圖中,紫色表示的是該元素在數組中的下標,可以看到,每個結點的值總是大於它的左右孩子,這裡並沒有規定左右孩子的大小關係,也沒有規定不是同一棵樹之間結點的大小關係。這就是最大堆。同時這裡可以注意到,如果是大堆,根節點一定是樹中最大的結點,同樣,如果是小堆,根節點一定是樹中最小的結點。
二、algorithm 中的堆算法
首先給出一個利用STL中堆算法的實例
#include#include void test() { int arr[] = {1,2,3,4,5,6,7}; vector vec(arr, arr+7); // 左開右閉類型 make_heap(vec.begin(), vec.end()); // 默認建大堆 pop_heap(v1.begin(), v1.end()); v1.pop_back(); sort_heap(vec.begin(), vec.end()); // 堆排序 for(size_t i = 0; i < vec.size(); i++) cout< 上面代碼,首先用一個數組構建了一個向量,之後對向量vec建堆,pop出調整之後的向量中第一個元素,並進行調整,然後進行堆排序,最後將結果打印出來,打印結果如下:
看完了heap算法的基本使用,再來了解一下STL中是如何提供這些算法接口的。
1、make_heap
前面提到過,堆分為大堆和小堆,我們建立堆的時候就需要確定,但剛剛例子中,我們並沒有去指定大小堆。STL中規定,沒有指定的話,默認大堆結構。從上面關於make_heap的兩套接口可以看到,第一種是默認的,沒有提供指定大小堆的接口,第二種這裡有實現。我們可通過仿函數的結構,實現這裡的傳參。
對剛剛給出的例子,我們現在可以解釋另外一個問題,為什麼我們要進行堆排序,首先要構建vector呢?因為堆的底層實現就是通過數組的形式,而vector是堆數組的高級封裝,這些庫中實現好的容器給出了很多實用的接口和迭代器,使用起來的確可以方便不少。make_heap給出的接口中,前兩個是任意類型的迭代器(當然,這裡也可以直接傳遞數組的指針),不論是make_heap還是其他三個函數,這裡的迭代器區間總是左閉右開的,這是個需要注意的地方。
接下來我們來介紹仿函數這裡的實現。還是上面的例子,如何讓上面剪子一個最小堆呢?
//仿函數結構:
struct Compare
{
bool operator()(int num1, int num2)
{
return num1 > num2;
}
};// 建堆時,參數傳遞改為
make_heap(vec.begin(), vec.end() , Compare()); // 建小堆上面寫的是num1 > num2,這樣建出來頂點是小堆。關於make_heap就說到這裡。
2、push_heap 與 pop_heap
push表示的是向vector中插入一個元素,但這裡它並不是直接插入元素,準確的說,它的功能只是做調整,在push_heap之前,首先需要調用vec.push_back(x),向vector尾部插入一個元素,然後在調用push_heap函數進行調整,使得整個樹重新滿足堆結構。
pop_heap與push_heap類似,同樣沒有直接改變vector中元素個數的能力。對於堆而言,pop要做的是將vector的第一個元素扔出去,為了不直接破壞樹的結構,這裡先調用pop_heap函數,將堆中的最大值或最小值放到vector的尾部,同時進行一次調整,使得堆結構依然成立,然後調用vec.pop+back()函數,將最後一個元素從vector中剔除。這就是插入和刪除的整個過程。
3、sort_heap
顧名思義,sort_heap就是進行堆排序的意思,對堆結構進行排序,得到的結果就是vector中的元素變得有序。這裡,構建大堆,排序結果是升序的,構建小堆,得到的排序結果是降序的。
上面就是關於堆排序的基本算法。
這裡有幾點需要注意的:
因為堆結構,是建立在vector上的結構,所以如果要進行堆排序,整個過程中至少一次建堆(make_heap)的過程。
當建堆完成之後,如果再向vector中插入元素,需要調用 push_heap(v1.begin(), v1.end()) 進行一次向上調整;如果從vector中Pop出一個元素,需要調用 pop_heap(v1.begin(), v1.end()) 進行一次向下調整。
如果沒有調整,當調用 sort_heap(v1.begin(), v1.end()) 函數的過程中,會出現由於堆不合法引起的斷言錯誤。
不可以讓vector多次尾插,之後再多次向上調整,會造成堆混亂,排序時也會出現斷言錯誤。多次插入或刪除之後,可以再次進行重新建堆,只不過消耗的時間代價會比較大。
三、堆結構實際應用
看一道試題:統計公司員工最喜歡吃的前K種水果
有過上面的基礎,我這裡直接給出demo
#include#include
閱讀更多 石頭大V 的文章