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

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

数值算法/人工智能

开发平台：

MultiPlatform

_b_heap.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _b_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/b_heap.h>
  15. b_heap::b_heap(int a, int b) : T(a,b)
  16. { if (b<a) error_handler(1,"constructor: illegal sizen");
  17.   low = a;
  18.   high = b;
  19.   min = high+1;
  20.   max = low-1;
  21.   int i;
  22.   for(i=a;i<=b;i++) T[i] = new list<b_heap_item>;
  23. }
  25. void b_heap::clear()
  26. { int i;
  27.   for (i=low;i<=high;i++) T[i]->clear();
  28.   min = high+1;
  29.   max = low-1;
  30. } 
  32. b_heap_item b_heap::insert(int key, GenPtr info) 
  33. { if (key<low || key>high) 
  34.   error_handler(1,string("insert: illegal key %dn",key));
  35.   if (key<min) min = key;
  36.   if (key>max) max = key;
  37.   b_heap_item it = new  b_heap_node(key,info);
  38.   it->loc = T[key]->append(it); 
  39.   return it;
  40. }
  42. b_heap_item b_heap::find_min()
  43. { if (min>high) return 0;
  44.   return T[min]->head();
  45. }
  47. b_heap_item b_heap::find_max()
  48. { if (max<low) return 0;
  49.   return T[max]->head();
  50. }
  52. GenPtr b_heap::del_min()
  53. { if (min>high) 
  54.        error_handler(1,"b_heap del_min: heap is empty");
  55.   b_heap_item p = T[min]->pop();
  56.   GenPtr res = p->info;
  57.   delete p;
  58.   while ((min <= high) && (T[min]->empty())) min++;
  59.   if (min>high) max = low-1;
  60.   return res;
  61. }
  63. GenPtr b_heap::del_max()
  64. { if (max<0) error_handler(1,"b_heap del_max: heap is empty");
  65.   b_heap_item p = T[max]->pop();
  66.   GenPtr res = p->info;
  67.   delete p;
  68.   while ((max>=low) && (T[max]->empty())) max--;
  69.   if (max<low) min = high+1;
  70.   return res;
  71. }
  73. b_heap_item b_heap::decrease_key(b_heap_item it, int k)
  74. { if (it==0) error_handler(1,"decrease_key: item = niln");
  75.   if (k<low || k>high) error_handler(1,"decrease_key: illegal keyn");
  76.   if (it->loc==0) error_handler(1,"decrease_key: item not foundn");
  77.   T[it->key]->del(it->loc);
  78.   while ((max >= low) && (T[max]->empty())) max--;
  79.   it->key = k;
  80.   it->loc = T[k]->append(it); 
  81.   if (k<min) min = k;
  82.   return it;
  83. }
  85. b_heap_item b_heap::increase_key(b_heap_item it, int k)
  86. { if (it==0) error_handler(1,"increase_key: item = niln");
  87.   if (k<low || k>high) error_handler(1,"increase_key:illegal keyn");
  88.   if (it->loc==0) error_handler(1,"increase_key: item not foundn");
  89.   T[it->key]->del(it->loc);
  90.   while ((min <= high) && (T[min]->empty())) min++;
  91.   it->key = k;
  92.   it->loc = T[k]->append(it); 
  93.   if (k>max) max = k;
  94.   return it;
  95. }
  98. void b_heap::delete_item(b_heap_item it) 
  99. { if (it==0) error_handler(1,"delete_item: item = niln");
  100.   if (it->loc==0) error_handler(1,"delete_item: item not foundn");
  101.   T[it->key]->del(it->loc); 
  102.   while ((min <= high) && (T[min]->empty())) min++;
  103.   while ((max >= low) && (T[max]->empty())) max--;
  104.   delete it;
  105. }
  107. void b_heap::print()
  108. { for (int i=low;i<=high;i++) 
  109.   { cout << i << ": ";
  110.     T[i]->print();
  111.     cout << "n";
  112.    }
  113.  }