百度面试题：找出第k大的数字所在的位置

描述：

　　写一段程序，找出数组中第k大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。

示例代码：[利用大顶堆排序，找到数组中第K大的数]

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 // 描述：
 5 // 写一段程序，找出数组中第k大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。
 6 // 第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。
 7 /////////////////////////////////////////////////
 8 
 9 typedef struct Node
10 {
11     int data;
12     int place;
13 }Node;
14 
15 void createNode(Node n[],int a[],int size)
16 {
17     for(int i=0;i<size;i++)
18     {
19         n[i].data = a[i];
20         n[i].place = i+1;
21     }
22 }
23 void HeapAdjust(Node a[],int i,int size)
24 {
25     int lchild = i*2;
26     int rchild = i*2+1;
27     int max = i;
28     if(i<=size/2)
29     {
30         if(a[max].data <a[lchild].data && lchild<=size)
31             max = lchild;
32         if(a[max].data <a[rchild].data && rchild<=size)
33             max = rchild;
34         if(max!=i)
35         {
36             swap(a[i],a[max]);
37             HeapAdjust(a,max,size);
38         }
39     }
40     
41 }
42 void NodeHeapSort(Node a[],int size,int k)
43 {
44     // 建堆
45     int i=0;
46     for(i=size/2;i>=0;--i)
47         HeapAdjust(a,i,size);
48 
49     // 调整
50     int j=1;
51     for(i=size;i>=0;--i,++j)
52     {
53         swap(a[0],a[i]);
54         if(j==k)
55         {
56             cout << a[i].place <<endl; break;
57         }
58         HeapAdjust(a,0,i-1);
59     }
60 }
61 int main()
62 {
63     int a[] = {2,4,3,4,7};
64     Node b[5];
65     createNode(b,a,5);
66     int k ;
67     cout << "请输入k值：";cin>>k;
68     NodeHeapSort(b,5,k); 
69     return 0;
70 }