寻找数组中的第K大元素

一、简述
　　使用数据结构堆&＃xff0c;实现查找数组中的第K大元素。流程如下&＃xff1a;数组内容堆化&＃xff08;因为是查找第K大&＃xff0c;所以使用大根堆&＃xff09;、依次取出并删除堆的根节点、将剩余元素堆化、取到第K个即为目标元素。
二、代码实现

#include
#include using namespace std;int findKth(vector<int> a, int n, int K) {int heapSize &＃61; n;vector<int> aa(a);aa.insert(aa.begin(),0);/*for将数组元素初始化为大根堆*/for(int root &＃61; heapSize / 2; root >&＃61; 1; root--){int rootElement &＃61; aa[root];int child &＃61; root * 2;while(child <&＃61; heapSize){if((child < heapSize) && (aa[child] < aa[child &＃43; 1])){child&＃43;&＃43;;}if(rootElement >&＃61; aa[child]){break;}else{aa[child / 2] &＃61; aa[child];child *&＃61; 2;}}aa[child / 2] &＃61; rootElement;}int result &＃61; 0;for(int i &＃61; 0; i < K; i&＃43;&＃43;){result &＃61; aa[1]; //取出根节点元素/*while将剩余元素堆化*/int lastElement &＃61; aa[heapSize --];int curNode &＃61; 1, childNode &＃61; 2;while(childNode <&＃61; heapSize){if((childNode < heapSize) && (aa[childNode] < aa[childNode &＃43; 1])){childNode &＃43;&＃43;;}if(lastElement >&＃61; aa[childNode]){break;}else{aa[childNode / 2] &＃61; aa[childNode];curNode &＃61; childNode;childNode *&＃61; 2;}}aa[curNode] &＃61; lastElement;}return result;
}int main()
{vector<int> primes {352, 564,453,2,1,34,5,6,7,8,7,5,67,76,56,45,25,2,2,5,4};int result &＃61; findKth(primes, (int)primes.size(), 8);cout << "result &＃61; " << result << endl;return 0;
}

三、运行结果

result &＃61; 34