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

源码开发语言/平台
当前位置：首页 > 源码/资料 > 图形图像 > 3D图形编程 > 查看源码
Heap.cpp
资源名称：3dSimplifier.zip　[点击查看]
上传用户：lin85885
上传日期：2013-04-27
资源大小：796k
文件大小：2k
源码类别：

3D图形编程

开发平台：

Visual C++

Heap.cpp：源码内容
  1. #include "StdAfx.h"
  2. #include <iostream.h>
  3. #include "Heap.h"
  5. void Heap::swap(int i,int j)
  6. {
  7.     heap_node tmp = ref(i);
  9.     ref(i) = ref(j);
  10.     ref(j) = tmp;
  12.     ref(i).obj->setHeapPos(i);
  13.     ref(j).obj->setHeapPos(j);
  14. }
  16. void Heap::upheap(int i)
  17. {
  18.     if( i==0 ) return;
  20.     if( ref(i).import > ref(parent(i)).import ) {
  21.         swap(i,parent(i));
  22.         upheap(parent(i));
  23.     }
  24. }
  26. void Heap::downheap(int i)
  27. {
  28.     if (i>=size) return;        // perhaps just extracted the last
  30.     int largest = i,
  31.         l = left(i),
  32.         r = right(i);
  34.     if( l<size && ref(l).import > ref(largest).import ) largest = l;
  35.     if( r<size && ref(r).import > ref(largest).import ) largest = r;
  37.     if( largest != i ) {
  38.         swap(i,largest);
  39.         downheap(largest);
  40.     }
  41. }
  43. void Heap::insert(Heapable *t,float v)
  44. {
  45.     if( size == maxLength() )
  46.     {
  47. cerr << "NOTE: Growing heap from " << size << " to " << 2*size << endl;
  48. resize(2*size);
  49.     }
  51.     int i = size++;
  53.     ref(i).obj = t;
  54.     ref(i).import = v;
  56.     ref(i).obj->setHeapPos(i);
  58.     upheap(i);
  59. }
  61. void Heap::update(Heapable *t,float v)
  62. {
  63.     int i = t->getHeapPos();
  65.     if( i >= size )
  66.     {
  67. cerr << "WARNING: Attempting to update past end of heap!" << endl;
  68. return;
  69.     }
  70.     else if( i == NOT_IN_HEAP )
  71.     {
  72. cerr << "WARNING: Attempting to update object not in heap!" << endl;
  73. return;
  74.     }
  76.     float old=ref(i).import;
  77.     ref(i).import = v;
  79.     if( v<old )
  80.         downheap(i);
  81.     else
  82.         upheap(i);
  83. }
  85. heap_node *Heap::extract()
  86. {
  87.     if( size<1 ) return 0;
  89.     swap(0,size-1);
  90.     size--;
  92.     downheap(0);
  94.     ref(size).obj->notInHeap();
  96.     return &ref(size);
  97. }
  99. heap_node *Heap::kill(int i)
  100. {
  101.     if( i>=size )
  102. cerr << "WARNING: Attempt to delete invalid heap node." << endl;
  104.     swap(i, size-1);
  105.     size--;
  106.     ref(size).obj->notInHeap();
  108.     if( ref(i).import < ref(size).import )
  109. downheap(i);
  110.     else
  111. upheap(i);
  114.     return &ref(size);
  115. }