LeetCode215之数组中的第K个最大元素（相关话题：堆排序,快速排序,减治法）

题目描述：

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

解法1：堆排序

解题思路

堆排序比较基本过程：把非叶子节点A下的子节点(A1,A2)的最大值(设为A1)和A比较。A1大于A的话,A1和A互换，否则不互换。在执行的过程中较小的值被逐层下移，下面对对堆排序过程的描述。