【學習筆記】不會吧不會吧，不會有人還在手寫堆吧

2020 年 10 月 17 日
筆記
奇技淫巧, 學習筆記, 數據結構

今天小編在水昨天考試題題解的時候，突然發現了 STL 自帶的手寫堆函數，本來以為優先隊列已經夠了，但是沒想到這些函數居然折磨好用，下面快和小編一起來看一看吧～

前言

這些函數位於 <functional> 頭文件中，不過當然 <bits/stdc++.h> 也是沒問題的。

除了普通的數組，結構體建堆也是沒有問題的，但需要重載運算符。

以下的數組均以 q[0] 儲存堆大小。

建堆

函數原型： make_heap(_RAIter,_RAIter,_Compare)

該函數用於把一個可迭代容器變成一個滿足堆性質的序列，默認是大頂堆。時間複雜度為從下向上建堆的 \(O(n)\)。

它有三個參數，前兩個是容器的開始元素迭代器和結束元素迭代器（同樣是左閉右開）。第三個參數用於生成小根或大根堆，分別是 greater<>() 和 less()<>，默認是大根堆。

注意，如果使用了第三個參數，以下其他所有函數都需要使用同樣的參數。

for(int i=1;i<=5;i++)
    q[++q[0]]=i;
make_heap(q+1,q+q[0]+1);
for(int i=1;i<=5;i++)
    printf("%d ",q[i]);

OUTPUT:
5 4 3 1 2

刪除

函數原型：pop_heap(_RAIter,_RAIter,_Compare)

參數意義同上。該函數用於將堆的第一個元素與最後一個元素交換位置，然後針對前 \(n-1\) 個元素調用 make_heap() 函數，看似好像比較慢，但實際上最壞的時間複雜度約是 \(O(2\log n)\)。

注意本函數只是將元素交換位置，所以真正刪除需要 q[0]--，vector 的話就是 pop_back()。

for(int i=1;i<=5;i++)
    printf("%d ",q[i]);
puts("");
pop_heap(q+1,q+q[0]+1);
for(int i=1;i<=5;i++)
    printf("%d ",q[i]);
puts("");

OUTPUT:
5 4 3 1 2
4 2 3 1 5

插入

函數原型：push_heap(_RAIter,_RAIter,_Compare)

參數意義同上。用於把數據插入到堆中。時間複雜度最壞 \(O(\log n)\)

在使用改函數之前，請確保要插入的數據被加入到容器末尾，如 vector 就是 push_back()。

for(int i=1;i<=5;i++){
    q[++q[0]]=i;
    push_heap(q+1,q+q[0]+1);
}
for(int i=1;i<=5;i++)
    printf("%d ",q[i]);

OUTPUT:
5 4 2 1 3

當然，先 make_heap 之後再 push_heap 也是可以的，這裡不再贅述。

堆排序

函數原型：sort_heap(_RAIter,_RAIter,_Compare)

參數意義同上。此函數會將滿足堆性質的序列依據大根堆或小根堆排序，排序後，序列將失去堆的性質。時間複雜度 \(O(n\log n)\)。

注意大根堆將變成一個遞增序列，小根堆將變成一個遞減序列。

請確保在排序前序列滿足堆的性質，否則會報錯。

不過這個用的應該不多，不如直接 sort 呢。

for(int i=1;i<=5;i++)
    q[++q[0]]=i;
make_heap(q+1,q+q[0]+1);
for(int i=1;i<=5;i++)
    printf("%d ",q[i]);
puts("");
sort_heap(q+1,q+q[0]+1);
for(int i=1;i<=5;i++)
    printf("%d ",q[i]);
puts("");

OUTPUT:
5 4 3 1 2
1 2 3 4 5

我還是想用優先隊列哭哭

這兩個代碼分別用優先隊列和這些函數插入和刪除 \(10^6\) 個元素。

優先隊列：

priority_queue<int> q;
for(int i=1;i<=1e6;i++)
    q.push(i);
for(int i=1;i<=1e6;i++)
    q.pop();

數組：

for(int i=1;i<=1e6;i++){
    q[++q[0]]=i;
    push_heap(q+1,q+q[0]+1);
}
for(int i=1;i<=1e6;i++){
    pop_heap(q+1,q+q[0]+1);
    q[0]--;
}

大家都能看出來區別。

所以，在沒有增加太多代碼量的同時，我們做到了手寫堆的效果，小編不禁直呼爺愛了。

總結

所以，如果有優先隊列卡常卡不過去的情況下還不想手寫堆，可以試試這些函數。

當然，在開啟 O2 優化的情況下，兩者的差距還是不大的，畢竟理論時間複雜度是一樣的。

最後來個封裝好 push 和 pop 的「手寫「大根堆：

#include <functional>
struct PRIORITY_QUEUE{
    int q[maxn];
    inline void Push(int x){
        q[q[0]++]=x;
        push_heap(q+1,q+q[0]+1);
    }
    inline void Pop(int x){
        pop_heap(q+1,q+q[0]+1);
        q[0]--;
    }
    inline int Size(){
        return q[0];
    }
    inline bool Empty(){
        return !q[0];
    }
}q;

Tags: 奇技淫巧學習筆記數據結構