五分钟玩转面试考点-数据结构-最大堆与最小堆(TOP N问题)
发布网友
发布时间：2023-02-02 05:41
共1个回答
热心网友
时间：2024-12-02 18:19
咳咳：俗话说： 脱离业务的技术，就是耍流氓。那么我就要提出这篇文章的灵魂一问了，请听题：
这个时候，感觉就是M个数中选择N个数 ，就是TOP N问题呀，是不是脑海中不由自主的蹦出了排序算法啦~
哈哈，咱就按照这个思路走。然后， 表面不慌，假装思索中ing，其实内心再想：排序算法是啥呀？
冒泡排序，核心思想：相邻比较。 每次将最大的浮出水面。
快速排序，核心思想：分治法+挖坑填数。 每次选择一基数，排序完成左边比基数小，右边比基数大。一直切分（ 分治 ），直至选出无序的最大的N个整数。
堆排序（出场自带猪脚光环~），可以创建一个N大小的最小堆 。然后balabala。
我就拿（内心PS：读书人的事情，怎么能说偷呢？）一下图吧，放在这里这里让大家容易理解~~
给定一个列表array=[16,7,3,20,17,8]，对其进行堆排序。
首先根据该数组元素构建一个完全二叉树，得到
然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：
第一步：找到最后一个组（非叶节点）， 左节点8 pk 擂主3 ，左孩子8胜利！然后3和8互相调换位置。 败者3 没有子节点，结束比赛。
从右到左。组内pk， 左子树20 pk 右子树17 左子树20胜利，获得挑战擂主7的机会。 左子树20 pk 擂主7 左子树20胜利，20和7交换位置。 败者7 没有子节点，结束比赛。
从下到上， 左子树20 PK 右子树8 ，左子树20胜利。获得挑战擂主16的机会。 左子树20 pk 擂主16 左子树胜利，交换位置。
此时 败者16 含有孩子节点，将被挑战。
组内挑战开始： 左子树7 和 右子树17 组内pk，右子树17胜利。获取挑战擂主16的机会。 右子树17 和 擂主16 pk，右子树17胜利，交换位置。 败者16 无孩子节点，结束比赛。
这样就得到了初始堆。
哈哈，相信到这里，基本懂得同学还是懂，不懂得还是一脸XX。这是哪？我在干什么？你是谁？
1.找到最后一个非叶节点，从右到左，从下到上，遍历所有 非叶节点 ；
2.若是父节点小于最大的子节点 ，那么交换父子节点的位置，但是要注意，交换之后对其他节点的影响。
我们的目标是：
( 没有蛀牙.... )根节点一定是树中最大的值。同时，父节点大于子节点。
切回到我们的问题。此时，你应该基本知道了堆的概念，为什么不选最大堆呢？因为咱们选最小堆就是采用末位淘汰制。将堆中最小元素剔除。
每次最小堆调整后，总会将整个堆中最小的元素放在根节点上，然后我们分别取出 [N-1,M] 中的元素，若大于堆顶，则替换。然后（ 随着堆的蠕动，你可以动态想想这个画面~~ ）再次将最小元素选出放于堆顶。直至堆里保存的都是最大的元素。
还是上面的数组，证据在上面，咱们就开始分析啦：
咱们从i=5，最后一个元素array[5]开始说起：
父节点：(i-1)/2=2，他的父节点就是i=2，array[2]也就是3。
子节点： 2i+1=11，等等兄得，你越界了...你根本没有孩子节点...(名侦探小胖)
于是我就大胆推测一下，最后一个非子节点就是array[2]。
反向推理一下：i=2时，左孩子：2i+1=5，右孩子：2i+2=6，但是最大下标是5，那么只有一个孩子节点array[5]也就是8。
那倒数第二个下标非叶节点的下标是啥？
博主内心独白：emmm我也不知道....继续套公式，看看有啥规律不。
数组倒数第二个下标数是i=4，(i-1)/2=1，那么下标array[1]就是第2个父节点。
数组倒数第三个下标数是i=3，(i-1)/2=1，也是下标array[1]。
那倒数第一个下标非叶节点的下标是啥？
数组倒数第四个下标数是i=2，(i-1)/2=1，那么下标array[0]就是第3个父节点。
数组倒数第三个下标数是i=1，(i-1)/2=1，也是下标array[0]。
此时还有吗？
数组倒数第五个下标数是i=0，(i-1)/2=-1，也是下标array[-1]。
也就是根节点没有父节点了....
等等，我好像发现啥规律了...
父节点是array[2]=3 array[1]=7 array[0]=16。
array=[16,7,3,20,17,8]
现在要开始 XX联盟S17 的比赛，比赛组根据玩家投票新采用了一种新的比赛规则，规则如下：
横向：每个新晋擂主可以参与更高一级的比赛，直至选出冠军。登顶大根堆顶峰；
纵向：每个下台擂主要被更低一级的选手挑战，需要证明自己实力，也可能被一撸到底；
简言之：能者上，弱者下
每一小组选出最强者，参与擂主pk，胜利者获取下一次挑战机会；失败者要被挑战，直至完成一场胜利，或者排名倒数。
而后，开始了激烈的小组比赛，擂主先把收拾自己的东西，因为他也不知道自己是一败涂地还是保持原位！心里有些忐忑~
215. 数组中的第K个最大元素
兜兜转转，从第一篇博客到2021.08.22已经过去了2年半多了。今天又回到这个题目。带来一种最小堆更加简洁的实现。即依赖JDK API来实现最小堆，只需要使得最小堆维护top n个元素即可。
