Chinaunix首页 | 论坛 | 博客
  • 博客访问: 701368
  • 博文数量: 111
  • 博客积分: 2109
  • 博客等级: 上尉
  • 技术积分: 1124
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-25 12:11
个人简介

通信码农,Emacs爱好者,业余IOS程序员,更业余的PM

文章分类

全部博文(111)

文章存档

2018年(2)

2016年(2)

2015年(2)

2014年(13)

2013年(21)

2012年(71)

分类: C/C++

2012-08-26 16:12:36


点击(此处)折叠或打开


  1. /* coded by zzy 2012/03/19 */
  2. #include <iostream>
  3. using namespace::std;
  4. void AdjustDown(int* a,int k,int len)
  5. {
  6.     a[0] = a[k];
  7.     for(int i = 2 * k; i <= len; i *= 2)
  8.     {
  9. if(i < len && a[i] < a[i+1])
  10. i++;
  11.       if(a[0] > a[i])
  12.       break;
  13.   else
  14.   {
  15.           a[k] = a[i];
  16.             k = i;
  17.   }
  18.     }
  19.     a[k] = a[0];
  20. }

  1. void BulidMaxHeap(int* a,int len)
  2. {
  3.     for(int i = len/2; i > 0; i--)//从n/2反复调整堆
  4.     {
  5.     AdjustDown(a,i,len);
  6.     }
  7. }
  8.  
  9. int _tmain(int argc, _TCHAR* argv[])
  10. {
  11.     int a[8] = {0,2,4,6,7,8,9,4};
  12.     int len = 7;
  13.     int temp = 0;
  14.     BulidMaxHeap(a,7);
  15.     for(int i = 0;i < 8;i++)
  16.     {
  17.         cout << a[i];
  18.     }
  19.     cout << endl;
  20.     for(int i = 1; i <= len; i++)
  21.     {
  22. cout << a[1];
  23. a[1] = a[len-i+1];
  24. AdjustDown(a,1,len-i);
  25.  
  26.     }
  27.     //getchar();
  28.     return 0;
  29. }
京东补录的时候用的笔试题还是去年的。最后一道选出K个最大值。
我的想法是维护一个大顶堆来进行操作,结构忘记了AdjustDown的编写方法,随手写了两句话,结构拿冒泡实现的同学得到了面试的机会。补一下功课。
阅读(923) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~