LeetCode——寻找数组中第K大的元素（堆排序（大顶堆））

题目描述

解题思路

显然直接调用API无法解决这个问题。因为此类问题通常不涉及对API的深入考察。显然之前曾用快速排序的方法解决了类似的问题。本次采用堆排序方法，并利用大顶堆结构来确定第K个最大元素。这类问题常被归类为典型的TOP K问题，在面试中常被作为考察重点。

1. 构建大顶堆

为什么需要建立大顶堆呢？这是因为大顶堆顶端的元素是数组中最大的那个元素。我们正式地利用这一点来解决这个问题。

生成最大堆的第一个步骤是从最后一个非终端节点开始，并持续延伸至根部。
对于二叉树结构而言，每个结点的左子结点编号为 2n+1。
相应的右子结点编号则为 2n+2。
每个结点对应的父结点编号则为 \lfloor (n−1)/\rfloor（向下取整）。
对于一棵树来说，在第 \lf�loor nums.length/2 \rfloor −1 层上可找到其最后一个非终端结点。

2. 将大顶堆下沉K-1次，得到的就是第K大的元素

如果我们旨在获取最大值，则当K减一等于零时无需执行下沉操作，在这种情况下大顶堆的堆顶即为最大值