2.5 k个最大的数

 1 #include <string.h>
 2 #include <stdio.h>
 3 
 4 
 5 void Swap(int * a, int i, int j)
 6 {
 7     int temp = a[i];
 8     a[i] = a[j];
 9     a[j] = temp;
10 }
11 
12 void Heapify(int * a, int start, int end)
13 {
14     int index;
15     if (2 * start + 2 <= end) {
16         index = a[2 * start + 1] < a[2 * start + 2] ? (2 * start + 1) : (2 * start + 2);
17         if (a[index] < a[start]) {
18             Swap(a, index, start);
19             Heapify(a, index, end);
20         }
21     } else if (2 * start + 1 == end) {
22         if (a[2 * start + 1] < a[start]) {
23             Swap(a, 2 * start + 1, start);
24         }
25     }
26 }
27 
28 template <int MAX = 3>
29 class KBigHeap {
30 private:
31     int data[MAX];
32     int cur;
33 public:
34     KBigHeap():cur(0)
35     {}
36     void Insert(int n)
37     {
38         if (cur < MAX) {
39             data[cur++] = n;
40         } else {
41          if (cur == MAX) { // 前面的刚刚满，要构造堆
42                 int i;
43                 for (i = (MAX - 1) / 2; i >= 0; --i) {
44                     Heapify(data, i, MAX - 1);
45                 }
46                 ++cur;
47             }
48             if (n > data[0]) {
49                 data[0] = n;
50                 Heapify(data, 0, MAX - 1);
51             }
52         }
53     }
54     
55     void Handle(int * a, int n)
56     {
57         int i;
58         for (i = 0; i < n; ++i) {
59             Insert(a[i]);
60         }
61     }
62 
63     void Print() const
64     {
65         int i;
66         for (i = 0; i < MAX; ++i) {
67             printf("%3d", data[i]);
68         }
69         printf("\n");
70     }
71 
72 };
73 
74 
75 int main()
76 {
77     int a[10] = {1, 9, 8, 7, 3, 5, 6, 2, 0, 4};
78     KBigHeap<5> k;
79     k.Handle(a, 10);
80 
81     k.Print();
82 
83     return 0;
84 }