文章目录
-
- 堆的相关概念
- Java中的堆
-
-
- offer方法
- poll方法
-
- 手写堆需要实现哪些方法
堆的相关概念
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
- 堆中某个结点的值总是不大于或不小于其父结点的值；
- 堆总是一棵完全二叉树。
将根结点最大的堆叫做最大堆或大java基础知识堆栈根堆，根结点最小的堆叫做最小堆或小根堆。
举例说明：
小根堆可以看到堆顶元素是最小的，每颗子树的根节点都是该树所有元素中最小的。
大根堆和小根堆相反，堆顶是最大的。
堆只是保证了堆顶的原始是整个堆中最大的或最小的，并不能保证层序遍历得到的序列是有序的。
Java中的堆
offer方法
java的优先队列底层也是数组，每次调用offer()方法插入一个元素之后，要对堆进行重新调整，关键函数是：
讯享网
如果没有指定comparator，会继续调用：
可以看到添加一个元素实际上是向上调整堆的一个过程。
poll方法
讯享网
手写堆需要实现哪些方法
已知堆支持操作：
- 获取堆顶元素
- 向堆中添加元素
- 删除堆顶元素
堆中插入元素之后，在对应的位置需要up。
堆中删除元素之后需要down。
任意位置修改后需要down和up一遍。
堆排序O(nlogn)：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/9510.html