每个班主任应该都遇到过这个问题:从班里面中找出来成绩前十的同学,我们通常想到的就是把所有人的成绩排序一遍,然后取前十名,这个肯定是没有问题的。但是假如让你把全省的前十名取出来,莫非你要对全省的每个同学都要进行排序,那得多大代价。。。所以有一种数据结构专门用来解决这种前K大问题——堆
- 堆是一个二叉树
- 叶子节点只存在最下面两层。
- 从根节点到倒数第二层,是一个完全二叉树。
- 一个节点不可能只有右孩子。
- 一个节点的左孩子和右孩子都比这个节点大(或者小)
举个例子——大顶堆:
堆的操作
维护堆状态
建堆
取堆顶
新增数据
Comments
""