开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_k_heap.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：4k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

_k_heap.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _k_heap.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #include <LEDA/impl/k_heap.h>
  16. #define KEY(i)   (HEAP[i]->key)
  17. #define INF(i)   (HEAP[i]->inf)
  20. k_heap::k_heap(int n, int k)  
  21. { if (n<=0) error_handler(1,string("k_heap constructor: illegal size = %d",n));
  22.   K = k;
  23.   HEAP = new k_heap_item[n+2];
  24.   for(int i = 0; i <= n; i++) HEAP[i] = nil;
  25.   count = 0; 
  26.   max_size = n;
  27. }
  29. k_heap::k_heap(const k_heap& H)
  30. { K = H.K;
  31.   max_size = H.max_size;
  32.   count = H.count; 
  33.   HEAP = new k_heap_item[max_size+2];
  34.   for(int i = 1; i <= count; i++) 
  35.   { HEAP[i] = new k_heap_elem(H.HEAP[i]->key, H.HEAP[i]->inf,i);
  36.     H.copy_key(HEAP[i]->key);
  37.     H.copy_inf(HEAP[i]->inf);
  38.   }
  39. }
  41. k_heap& k_heap::operator=(const k_heap& H)
  42. { clear();
  43.   delete HEAP;
  44.   K = H.K;
  45.   max_size = H.max_size;
  46.   count = H.count; 
  47.   HEAP = new k_heap_item[max_size+2];
  48.   for(int i = 1; i <= count; i++) 
  49.   { HEAP[i] = new k_heap_elem(H.HEAP[i]->key, H.HEAP[i]->inf,i);
  50.     copy_key(HEAP[i]->key);
  51.     copy_inf(HEAP[i]->inf);
  52.   }
  53.   return *this;
  54. }
  56. k_heap::~k_heap()  
  57. { clear();
  58.   delete HEAP; 
  59. }
  61. void k_heap::clear()
  62. { for(int i=1; i <= count; i++) 
  63.   { clear_key(KEY(i));
  64.     clear_inf(INF(i));
  65.     delete HEAP[i];
  66.    }
  67.   count = 0;
  68. }
  71. void k_heap::rise(int pos, k_heap_item it)
  72. { 
  73.   HEAP[0] = it;  // use "it" as stopper
  75.   register int         pi = pos/K;        // parent index
  76.   register k_heap_item p  = HEAP[pi];     // parent node
  79.   if (int_type())
  80.      while(p->key > it->key)
  81.      { HEAP[pos] = p;
  82.        p->index = pos;
  83.        pos = pi;
  84.        pi /= K;
  85.        p = HEAP[pi];
  86.       }
  87.   else
  88.      while (cmp(p->key,it->key) > 0)
  89.      { HEAP[pos] = p;
  90.        p->index = pos;
  91.        pos = pi;
  92.        pi /= K;
  93.        p = HEAP[pi];
  94.       }
  96.   HEAP[pos] = it;
  97.   it->index = pos;
  98. }
  101. void k_heap::sink(int pos, k_heap_item it)
  102. { 
  103.   register int ci = K*pos;    // child index
  104.   register k_heap_item p;     // child node
  107.   HEAP[count+1] = HEAP[count];   // stopper
  109.   if (int_type())
  110.      while (ci <= count)
  111.      { 
  112.        p = HEAP[ci];
  114.        int r = Min(count+1,ci+K);
  116.        for (int j=ci+1;j<r;j++)
  117.            if (cmp(KEY(j),p->key)<0 ) 
  118.             { ci = j;
  119.               p = HEAP[j];
  120.              }
  122.        if (it->key > p->key) 
  123.        { HEAP[pos] = p;
  124.          p->index = pos;
  125.          pos = ci;
  126.          ci *= K;
  127.         }
  128.        else  break;
  129.       }
  130.   else
  131.      while (ci <= count)
  132.      { 
  133.        p = HEAP[ci];
  135.        int r = Min(count+1,ci+K);
  137.        for (int j=ci+1;j<r;j++)
  138.            if (cmp(KEY(j),p->key)<0 ) 
  139.             { ci = j;
  140.               p = HEAP[j];
  141.              }
  142.        
  143.        if (cmp(it->key,p->key)>0) 
  144.        { HEAP[pos] = p;
  145.          p->index = pos;
  146.          pos = ci;
  147.          ci *= K;
  148.         }
  149.         else  break;
  150.       }
  152.   HEAP[pos] =it;
  153.   it->index = pos;
  154. }
  159. void k_heap::decrease_key(k_heap_item it, GenPtr k)
  160. {
  161. //if (cmp(it->key,k)<0) error_handler(1,"k-heap:key too large in decrease_key");
  162.   clear_key(it->key);
  163.   copy_key(k);
  164.   it->key = k;
  165.   rise(it->index, it);
  166. }
  170. k_heap_item k_heap::insert(GenPtr k, GenPtr i) 
  171. {
  172.   if (count == max_size) error_handler(1,"k_heap: overflow");
  173.   count++;
  174.   copy_key(k);
  175.   copy_inf(i);
  176.   k_heap_item it = new k_heap_elem(k,i,count);
  177.   rise(count,it);
  179.   return it;
  180. }
  185. void k_heap::del_item(k_heap_item it)
  186. { k_heap_item p = HEAP[count];
  188.   HEAP[count] = nil;
  190.   count--;
  192.   if (it != p)
  193.   { if (cmp(p->key,it->key) > 0)
  194.        sink(it->index, p);
  195.     else
  196.        rise(it->index, p);
  197.    }
  199.   clear_key(it->key);
  200.   clear_inf(it->inf);
  202.   delete it;
  205. }
  207. void k_heap::change_inf(k_heap_item it, GenPtr i) 
  208. { clear_inf(it->inf);
  209.   copy_inf(i);
  210.   it->inf = i; 
  211.  }
  213. void k_heap::print()
  214. { 
  215.   cout << "count = " << count << endl;
  216.   for(int i=1;i<=count;i++) 
  217.   { print_key(KEY(i));
  218.     //cout << "-";
  219.     //print_inf(INF(i));
  220.     cout << "  ";
  221.    }
  222.   newline;
  223. }