03月21, 2019

【数据结构】堆

每个班主任应该都遇到过这个问题:从班里面中找出来成绩前十的同学,我们通常想到的就是把所有人的成绩排序一遍,然后取前十名,这个肯定是没有问题的。但是假如让你把全省的前十名取出来,莫非你要对全省的每个同学都要进行排序,那得多大代价。。。所以有一种数据结构专门用来解决这种前K大问题——堆

  1. 堆是一个二叉树
  2. 叶子节点只存在最下面两层。
  3. 从根节点到倒数第二层,是一个完全二叉树。
  4. 一个节点不可能只有右孩子。
  5. 一个节点的左孩子和右孩子都比这个节点大(或者小) 举个例子——大顶堆:

堆的操作

维护堆状态

建堆

取堆顶

新增数据

本文链接:http://www.yuqiaochuang.com/post/【数据结构】堆.html

-- EOF --

Comments

""