oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

HEAP

Posted on 2006-09-08 23:25 oyjpart 阅读(758) 评论(3)  编辑 收藏 引用

 

// 说实话 我还是挺喜欢HEAP这个数据结构的 写个类的HEAP吧 呵呵
// by Optimistic
// 本程序是大根堆的操作集合 以及堆排序 优先级队列的堆实现
#include  < string .h >
#include 
< iostream >
using   namespace  std;

template 
< typename T >
class  MaxHeap                 // 大根堆 (本程序使用下标与结点名相同的格式)
{
public :
 MaxHeap(
int  MaxHeapSize  =   10 );
 
~ MaxHeap() {delete [] heap;}
 
int  Size() { return  heapSize;}
 MaxHeap
< T >&  Insert( const  T &  x);
 MaxHeap
< T >&  Delete(T &  x);
 
void  MakeHeap(T  *  a,  int  size,  int  ArraySize);
 T Max()
 
{
  
if (heapsize  >   0 )      // 判溢出
   return  heap[ 1 ];
 }

private :
 T
*  heap;
 
int  heapSize;
 
int  MaxSize; 
}
;

template 
< typename T >
MaxHeap
< T > ::MaxHeap( int  MaxHeapSize)         
{
 MaxSize 
=  MaxHeapSize;
 heap 
=   new  T[MaxSize + 1 ];
 heapSize 
=   0 ;
}


template 
< typename T >
MaxHeap
< T >&  MaxHeap < T > ::Insert( const  T &  x)  // 堆的插入 由叶结点向上找位置 在sort中是不需要插入的
{
 
if (heapSize  <  MaxSize)    
 
{
  heapSize
++ ;
  
int  i  =  heapSize, ic  =  i / 2 ;
  
while (ic  >=   1 )
  
{
   
if (x  <=  heap[ic])  break ;
   heap[i] 
=  heap[ic];
   i 
=  ic;
   ic 
=  i  /   2 ;
  }

  heap[i] 
=  x;
 }

 
return   * this ;
}


template 
< typename T >
MaxHeap
< T >&  MaxHeap < T > ::Delete(T &  x)        // 堆的删除 即根结点的删除 从上到下
{
 
// 在操作上相当与对最后一个结点从上到下的插入
  if (heapSize  >   0 )
 
{
  x 
=  heap[ 1 ];
  T y 
=  heap[heapSize -- ];
  
int  i  =   1 , ic  =   2 ;               // i记录当前查询结点 ic记录其子结点
   while (ic  <=  heapSize)               
  
{
   
if (ic + 1   <=  heapSize  &&  heap[ic]  <  heap[ic + 1 ]) ic ++ ;
   
if (y  >=  heap[ic])  break ;
   heap[i] 
=  heap[ic];
   i 
=  ic;
   ic 
=   2 * i;
  }

  heap[i] 
=  y;
 }

 
return   * this ;
}


template 
< typename T >
void  MaxHeap < T > ::MakeHeap(T  *  a,  int  size,  int  ArraySize)  // 建堆:把数组堆化并处理成大根堆
{
 
// 堆化
 delete [] heap;
 heap 
=   new  T[size + 1 ];
 memcpy(heap, a, (size
+ 1 ) * sizeof (T));       // 此处不要忘记乘sizeof(T)
 heapSize  =  size;
 MaxSize 
=  ArraySize;
 
// 处理堆
  int  i  =  heapSize / 2 ;
 
for (; i  >=   1 ; i -- )                     // 从小到上依次调整
  {
  T y 
=  heap[i];
  
int  ic  =   2 * i;
  
while (ic  <=  heapSize) 
  
{
   
if (ic + 1   <=  heapSize  &&  heap[ic + 1 >  heap[ic]) ic ++ ;
   
if (y  >=  heap[ic])  break ;
   heap[ic
/ 2 =  heap[ic];
   ic 
=   2 * ic;
  }

  heap[ic
/ 2 =  y;
 }

}


template 
< typename T >
void  HeapSort(T  *  a,  int  n)
{
 MaxHeap
< T >  H( 0 );
 H.MakeHeap(a, n, n);
 T x;
 
for ( int  i  =  n; i  >=   1 ; i -- )
 
{
  H.Delete(x);
  a[i] 
=  x;
 }

}


int  main()
{
//  freopen("heap.in", "r", stdin);
  int  size, i,  *  a;
 printf(
" Please input the size of array:\n " );
 scanf(
" %d " & size);
 a 
=   new   int [size + 1 ];
 printf(
" Please input the array to be sorted:\n " );
 
for (i = 1 ; i <= size; i ++ )
  scanf(
" %d " & a[i]);
 HeapSort(a, size);
 
for (i = 1 ; i <= size; i ++ )
  printf(
" %4d " , a[i]);
 printf(
" \n " );
 system(
" Pause " );

 
return   0 ;
}


Feedback

# re: HEAP  回复  更多评论   

2006-09-15 17:26 by
heap, 好想学, 不知道我为什么没讲heap的书...-_-

# re: HEAP  回复  更多评论   

2006-09-15 23:53 by Optimistic
第一次遇到HEAP的时候好喜欢啊 呵呵 真是一个好东东!

# re: HEAP  回复  更多评论   

2006-10-25 22:40 by Asp
不知道以后数据结构会不会讲……

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理