Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Making Heaps Meldable

コードについての説明

元論文は "Melding priority queues" [Mendelson, Tarjan, Thorup, Zwick 2004].

時間計算量: insert, meld ならし $\O (1)$, find_min $\O (1)$, erase ならし $\O \left( pq(n) \alpha(n, n / pq(n)) \right)$
(元のヒープが insert, delete, find_min を $pq(n)\ (= \O (\log n))$ time で処理する場合)

コード

  1. // BaseHeap が与えられる non meldable heap に対応
  2. // multiset を non meldable ヒープとして使った場合について実装している
  3. template<typename _Key, class _Compare=less<_Key> > class BaseHeap {
  4. private:
  5.     multiset<_Key, _Compare> heap;
  6.  
  7. public:
  8.     BaseHeap(){}
  9.     bool empty() const {
  10.         return heap.empty();
  11.     }
  12.     void insert(const _Key& key){
  13.         heap.insert(key);
  14.     }
  15.     void erase(const _Key& key){
  16.         heap.erase(heap.find(key));
  17.     }
  18.     const _Key& find_min() const {
  19.         return *heap.begin();
  20.     }
  21. };
  22.  
  23. template<typename _Key, class _Compare=less<_Key> > class MeldableHeapNode {
  24. private:
  25.     BaseHeap<_Key, _Compare> bheap;
  26.     MeldableHeapNode *par;
  27.     unsigned int rank;
  28.  
  29. public:
  30.     MeldableHeapNode(const _Key& key) : par(this), rank(0u){
  31.         bheap.insert(key);
  32.     }
  33.     bool empty() const {
  34.         return bheap.empty();
  35.     }
  36.     MeldableHeapNode*& get_parent(){
  37.         return par;
  38.     }
  39.     MeldableHeapNode*& get_grandparent(){
  40.         return par->get_parent();
  41.     }
  42.     unsigned int& get_rank(){
  43.         return rank;
  44.     }
  45.     bool is_root() const {
  46.         return this == par;
  47.     }
  48.     void insert(const _Key& key){
  49.         bheap.insert(key);
  50.     }
  51.     void erase(const _Key& key){
  52.         bheap.erase(key);
  53.     }
  54.     const _Key& find_min() const {
  55.         return bheap.find_min();
  56.     }
  57. };
  58.  
  59. template<typename _Key, class _Compare=less<_Key> > class MeldableHeaps {
  60. private:
  61.     stack<MeldableHeapNode<_Key, _Compare>*> free_pointer;
  62.     void cut_path(MeldableHeapNode<_Key, _Compare> *cur_heap){
  63.         if(!cur_heap->is_root()){
  64.             cut_path(cur_heap->get_parent());
  65.             unhang(cur_heap, cur_heap->get_parent());
  66.         }
  67.     }
  68.     void compress_path(MeldableHeapNode<_Key, _Compare> *cur_heap){
  69.         if(!cur_heap->is_root()){
  70.             compress_path(cur_heap->get_parent());
  71.             hang(cur_heap, cur_heap->get_grandparent());
  72.         }
  73.     }
  74.     void hang(MeldableHeapNode<_Key, _Compare> *heap1,
  75.                                             MeldableHeapNode<_Key, _Compare> *heap2){
  76.         if(!heap1->empty()) heap2->insert(heap1->find_min());
  77.         heap1->get_parent() = heap2;
  78.     }
  79.     void unhang(MeldableHeapNode<_Key, _Compare> *heap1,
  80.                                             MeldableHeapNode<_Key, _Compare> *heap2){
  81.         heap2->erase(heap1->find_min());
  82.     }
  83.  
  84. public:
  85.     MeldableHeaps(){}
  86.     ~MeldableHeaps(){
  87.         while(!free_pointer.empty()){
  88.             MeldableHeapNode<_Key, _Compare> *heap = free_pointer.top();
  89.             free_pointer.pop();
  90.             delete heap;
  91.         }
  92.     }
  93.     MeldableHeapNode<_Key, _Compare> *make_heap(const _Key& key){
  94.         free_pointer.push(new MeldableHeapNode<_Key, _Compare>(key));
  95.         return free_pointer.top();
  96.     }
  97.     MeldableHeapNode<_Key, _Compare> *insert(MeldableHeapNode<_Key, _Compare> *heap,
  98.                                                 const _Key& key){
  99.         assert(heap->is_root());
  100.         MeldableHeapNode<_Key, _Compare> *return_heap = make_heap(key);
  101.         meld(heap, return_heap);
  102.         return return_heap;
  103.     }
  104.     void erase(MeldableHeapNode<_Key, _Compare> *key_heap, const _Key& key){
  105.         cut_path(key_heap);
  106.         key_heap->erase(key);
  107.         compress_path(key_heap);
  108.     }
  109.     const _Key& find_min(MeldableHeapNode<_Key, _Compare> *heap){
  110.         assert(heap->is_root() && !heap->empty());
  111.         return heap->find_min();
  112.     }
  113.     MeldableHeapNode<_Key, _Compare> *meld(MeldableHeapNode<_Key, _Compare> *heap1,
  114.                                             MeldableHeapNode<_Key, _Compare> *heap2){
  115.         assert(heap1->is_root() && heap2->is_root());
  116.         if(heap1->get_rank() < heap2->get_rank()) swap(heap1, heap2);
  117.         hang(heap2, heap1);
  118.         if(heap1->get_rank() == heap2->get_rank()) ++heap1->get_rank();
  119.         return heap1;
  120.     }
  121.     MeldableHeapNode<_Key, _Compare> *find_root(MeldableHeapNode<_Key, _Compare> *heap){
  122.         cut_path(heap);
  123.         compress_path(heap);
  124.     }
  125. };

verify 用の問題

AOJ : Minimum Spanning Tree 提出コード