大家好，欢迎来到IT知识分享网。
堆是每个双亲节点都大于（小于）子节点的特殊完全二叉树。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
大顶堆与小顶堆
堆的性质
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
堆的存储方式
从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储.
堆的操作和实现
堆化
在插入或删除操作后需要进行调整，让其重新满足堆的特性，这个调整的过程叫做堆化（heapify）。
上浮：当前元素不断向上和父节点比较大小
- 大顶堆：当前元素比父节点大，交换，让大的节点上去
- 小顶堆：当前元素比父节点小，交换，让小的节点上去
下沉：当前元素不断向下和两个孩子节点比较大小
- 大顶堆：当前元素与子节点中较大的比，比子节点小交换，让小的节点下去
- 小顶堆：当前元素与子节点中较小的比，比子节点大交换，让大的节点下去
插入
从下往上的堆化，在堆的尾部插入，满足完全二叉树条件，再进行堆化。
删除
把最后一个元素移到根节点的位置，满足完全二叉树的条件，再进行堆化
堆的应用
优先队列
堆是实现优先级队列最直接、最高效的方法。一般队列出队顺序只取决于入队顺序，而优先级队列的出队顺序总是按照元素自身的优先级。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素
堆排序
实现堆排序可分解为两个步骤，建堆和排序
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/177901.html
