T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks
//用习惯了STL_heap自己来写一个,类实现。

#include
<iostream>
#include
<string>
#include
<cmath>
#include
<algorithm>
using namespace std;

#define N 100

class my_heap{    
public:
    
int array[N];
    
int cnt;

    my_heap()
    
{
        
for(int i=0;i<N;i++)
            array[i]
=0;
        cnt
=0;
    }

    
void push(int num);
    
int pop();
}
;

void my_heap::push(int num)
{
    array[
++cnt]=num;
    
int i=cnt,j=i/2;
    
while(j>0)
    
{
        
if(array[i]>array[j])
            swap(array[i],array[j]);
        
else break;
        i
=j;j=i/2;
    }

}

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
int my_heap::pop()                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      
{
    
int num=array[1],maxc;
    swap(array[
1],array[cnt]);
    cnt
--;
    
int i=1,j=2*i;
    
while(j<=cnt)
    
{
        
if(j+1>cnt) maxc=j;
        
else maxc=array[j]>array[j+1]?j:j+1;
        
if(array[maxc]>array[i])
            swap(array[i],array[maxc]);
        
else break;
        i
=maxc;j=2*i;
    }

    
return num;
}
   
                                                                                              
int main()
{
    
int num;
    my_heap h;
    
while(scanf("%d",&num),num)
        h.push(num);
    
while(h.cnt)
        printf(
"%d ",h.pop());
    printf(
"\n");
    
for(int i=1;h.array[i]&&i<N;i++)
        printf(
"%d ",h.array[i]);
    printf(
"\n");
    
return 0;
}
测试数据及结果:
1 4 9 88 56 21 45 7 6 3 99 1452 122 34 2 0
1452 122 99 88 56 45 34 21 9 7 6 4 3 2 1
1 2 3 4 6 7 9 21 34 45 56 88 99 122 1452
Press any key to continue
posted on 2008-11-23 12:42 Torres 阅读(201) 评论(0)  编辑 收藏 引用 所属分类: Data Structures

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理