关注
可以使用数组来模拟堆,并且需要实现三个基本操作:插入元素、获取堆顶元素、删除堆顶元素。
1. 插入元素(push 操作)
将新元素插入数组的末尾。
然后将这个新元素向上调整,直到其满足堆的性质(即父节点的值大于等于当前节点的值)。
向上调整过程(上浮):
比较当前元素与其父节点的大小。如果当前元素大于其父节点,交换两者的位置。
重复此过程,直到当前元素不再大于其父节点,或者当前元素已经成为根节点。
2. 获取堆顶元素(top 操作)
直接返回数组的第一个元素(即根节点)。
如果堆为空,返回 "empty"。
3. 删除堆顶元素(pop 操作)
用数组的最后一个元素替换堆顶元素,然后移除最后一个元素。
将新的堆顶元素向下调整,直到其满足堆的性质(即当前节点的值大于等于其子节点的值)。
向下调整过程(下沉):
比较当前节点与其两个子节点的大小。
如果当前节点小于最大的子节点,交换它们的位置。
重复此过程,直到当前节点不再小于它的子节点,或者当前节点没有子节点。
点赞
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 面试问题记录 #
61190次浏览 883人参与
# 硬件人的简历怎么写 #
254542次浏览 2886人参与
# 京东TGT #
47721次浏览 174人参与
# 你遇到过哪些神仙同事 #
71974次浏览 643人参与
# 我的2024小目标 #
58311次浏览 392人参与
# 工作中,你有没有遇到非常爱骂人的领导? #
17229次浏览 128人参与
# 百度工作体验 #
204895次浏览 1907人参与
# 实习生应该准时下班吗 #
201715次浏览 1314人参与
# 上班到公司第一件事做什么? #
37951次浏览 347人参与
# 国企和大厂硬件兄弟怎么选? #
120184次浏览 1656人参与
# 工作一周年分享 #
19264次浏览 111人参与
# 没有合适的工作,你会先找个干着,还是考公考研 #
104481次浏览 1077人参与
# 面试吐槽bot #
14351次浏览 88人参与
# 互联网行业现在还值得去吗 #
6455次浏览 42人参与
# 面试经验谈 #
39260次浏览 512人参与
# 拼多多工作体验 #
16782次浏览 152人参与
# 入职第五天,你被拉进了几个工作群 #
18028次浏览 80人参与
# 假如我穿越到了妈妈的18岁 #
6395次浏览 43人参与
# 国企vs私企,你更想去? #
217690次浏览 2073人参与
# 你们的毕业论文什么进度了 #
999424次浏览 9398人参与
# 机械人,你的第一份感谢信是谁给的 #
26891次浏览 296人参与