1 // heap.cpp : 定义控制台应用程序的入口点。
2 //
3
4 #include "stdafx.h"
5 #include <iostream>
6 using namespace::std;
7 void AdjustDown(int* a,int k,int len)
8 {
9 a[0] = a[k];
10 for(int i = 2 * k; i <= len; i *= 2)
11 {
12 if(i < len && a[i] < a[i+1])
13 i++;
14 if(a[0] > a[i])
15 break;
16 else
17 {
18 a[k] = a[i];
19 k = i;
20 }
21 }
22 a[k] = a[0];
23 }
24
25 void BulidMaxHeap(int* a,int len)
26 {
27 for(int i = len/2; i > 0; i--)//从n/2反复调整堆
28 {
29 AdjustDown(a,i,len);
30 }
31 }
32
33 int _tmain(int argc, _TCHAR* argv[])
34 {
35 int a[8] = {0,2,4,6,7,8,9,4};
36 int len = 7;
37 int temp = 0;
38 BulidMaxHeap(a,7);
39 for(int i = 0;i < 8;i++)
40 {
41 cout << a[i];
42 }
43 cout << endl;
44 for(int i = 1; i <= len; i++)
45 {
46 cout << a[1];
47 a[1] = a[len-i+1];
48 AdjustDown(a,1,len-i);
49
50 }
51 getchar();
52 return 0;
53 }
54
京东补录的时候用的笔试题还是去年的。最后一道选出K个最大值。我的想法是维护一个大顶堆来
进行操作，结构忘记了AdjustDown的编写方法，随手写了两句话，结构拿冒泡实现的同学得到了面试的机会。补一下功课。